This is a program to search for Wieferich primes and (since these are very rare) primes with small Fermat quotients. Fermat's Little Theorem states that if p is a prime number then ap-1 ≡ 1 (mod p) for every number a which is not divisible by p. A Wieferich prime is an odd prime p such that 2p-1 ≡ 1 (mod p2). There are only two known Wieferich primes (1093 and 3511) but it is conjectured that there are infinitely many.
The third Wieferich prime (assuming that it exists) is a very elusive beast. There have been many exhaustive searches, see this old status report. Dominic Klyve, a fellow Dartmouth graduate student, pressured me into joining the effort. While this has very little practical or theoretical value, I found the challenge interesting and I wrote WPSE.
The current version of WPSE can compute the Fermat quotient of a 60 bit prime in about 1μs on a 2GHz Opteron processor. Combined with a fast memoryless sieve, we can compute the Fermat quotients of all primes in a range of length 3×1010 in about one cpu hour. Dominic and I are currently running WPSE on parts of the Green Grid and Discovery research clusters at Dartmouth College. We plan to reach 6.7×1015 by Summer 2007 at which point we will announce the results. We have not yet found the elusive third Wieferich prime, but we have gathered substantial data on small Fermat quotients and the search continues...
The source code for WPSE is available under the terms of the GNU General Public License. (Download wpse.tar.bz2 )
Written using the GMP library, this program enumerates Proth primes of the special form 2n - 2m + 1 where m < n ≤ 2m. I was interested in these primes for two reasons:
Unfortunately, I have yet to find a practical use of this. Still, I have taken the time to generate a table of the first few such primes just in case.
The table of all 13357 primes p = 2n - 2m + 1 with m < n ≤ 2m &le 10000 is here. This is a plain text file each line of which consists of three tab separated (decimal) numbers, the first is m, the second is n and the third is the smallest quadratic nonresidue modulo p, i.e. a number a such that a(p-1)/2 ≡ -1 (mod p).
The reason for the third number in the list is the surprising fact that a necessary and sufficient condition for the number p = 2n - 2m + 1 with m < n ≤ 2m to be prime is that there is a number a such that a(p-1)/2 ≡ -1 (mod p). For general numbers, this is a necessary, but not sufficient, condition for primality. Since it is sufficient for numbers of this specific form, the third number constitutes a certificate of primality for the number p = 2n - 2m + 1.
At this point you may have a rough idea on how to go about enumerating special Proth primes. There are a few more cool tricks that can be found by reading the source code for my program (f3tp.tar.bz2) which is released under the terms of the GNU General Public License. You are therefore free to use and modify the program as you wish, but be aware that the program is unmaintained and poorly documented. Comments and bug reports are always welcome.