Elite and Anti-Elite Prime Search Methodology
Dennis R. Martin
DP Technology Corp., Camarillo, CA
dennis.martin@dptechnology.com
A prime number p is elite if only finitely many Fermat numbers Fm = 2^(2m)
+ 1 are quadratic residues of p,
while p is anti-elite if only finitely many Fermat numbers are quadratic
non-residues of p. Both elite and
anti-elite primes are being searched for simultaneously in this study using a
method based on articles by Chaumont and Müller [1] and
Müller [2].
Instead of checking whether a
certain congruence is solvable or not for each Fermat residue within the Fermat
period L (as given by expression (4)
in reference [1] or expression (22) in reference [2]), however, the Jacobi symbols of the Fermat residues are
utilized. The algorithm for computing the Jacobi symbol was taken from Caldwell [3].
An important result from Aigner [4] is that for any prime number written in the form p = 2Sh
+ 1 with h 1 and odd such
that S is a maximum, the S-th term is the latest possible Fermat
period start. While the actual period start s
could be earlier (s S), the Fermat residue FS must eventually repeat.
Aigner also proved in [4] that prime numbers of the form p = 120k + r with k a natural number and r a member of {11, 13, 19, 23, 31, 47,
59, 61, 71, 79, 91, 109, 119} cannot be elite. Chaumont and Müller in [2] made an analogous proof that prime numbers of the form p = 240k + r with k a natural number and r a member of {7, 23, 43, 47, 67, 83,
103, 107, 127, 143, 163, 167, 187, 203, 223, 227} cannot be anti-elite.
Those results combine to lead to
the following algorithm to check the eliteness or anti-eliteness of a candidate
prime p:
- Compute the residue of p mod 240. If (p mod
240) is a member of {23, 47, 143, 167}, then p can be neither elite nor anti-elite, so exit and go on to
the next candidate.
- Determine the latest possible Fermat period start S.
- Inside of a For/Next loop from 0 to S, compute the Fermat residues
modulo p up to FS and save those
residues in an array. If a period is completed (if a residue repeats)
prior to FS being
reached, then flag that condition and exit the loop.
- Calculate the Jacobi symbol of the last residue r, which will either correspond to FS (if the loop in step
3 was completed to S) or will
correspond to the term at the end of a period, Fe where e
= s + L – 1 (if the loop in step 3 was exited early).
- If the Jacobi symbol in step 4 is -1, then r is a quadratic non-residue, which
means p could not be anti-elite.
So check if the (p mod 240)
value from step 1 is a member of {11, 13, 19, 23, 31, 47, 59, 61, 71, 79,
91, 109, 119, 131, 133, 139, 143, 151, 167, 179, 181, 191, 199, 211, 229,
239}, because then p cannot be
elite either, so exit and go on to the next candidate.
- If the Jacobi symbol in step 4 is 1, then r is a quadratic residue, which
means p could not be elite. So
check if the (p mod 240) value
from step 1 is a member of {7, 23, 43, 47, 67, 83, 103, 107, 127, 143, 163,
167, 187, 203, 223, 227}, because then p
cannot be anti-elite either, so exit and go on to the next candidate.
- If the loop in step 3 was not exited early (i.e. a
Fermat period has not yet been completed) then setup a Do/Until Loop to
loop until a period does complete (i.e. until we find a residue re+1 = rs that is already a
member of the array saved in step 3). For each residue inside this loop
calculate its Jacobi symbol. If the Jacobi symbol of any Fermat residue does
not match the Jacobi symbol corresponding to FS from step 4, then p can be neither elite nor anti-elite, so exit and go on to
the next candidate.
- Find the index of the first repeating residue rs inside the array from
step 3 and setup another For/Next loop to go from that index to the end of
the array. For each residue inside this loop calculate its Jacobi symbol.
Once again if the Jacobi symbol of any Fermat residue does not match the
Jacobi symbol corresponding to Fe
from step 4, then p can be
neither elite nor anti-elite, so exit and go on to the next candidate.
- If the Jacobi symbols from the loops in steps 7 and 8
are all identical, then p is
elite if those Jacobi symbols are -1 and p is anti-elite if they are all +1. The Fermat period L is the number of Fermat residues
looped through in steps 7 and 8 combined.
The results of this currently
ongoing search are given on the Elite Prime Search
and Anti-Elite Prime Search pages [8, 9]. As of February 12, 2009, this
search is complete up to 1E14. There are 29 elite primes less than 1E14 and 113
anti-elite primes less than 1E14.
The elite and anti-elite primes
appear as sequences A102742 and A128852 in
Sloane’s Online Encyclopedia of Integer Sequences (OEIS) [6].
References
[1] Alain Chaumont and Tom Mueller, All
Elite Primes Up to 250 Billion, J. Integer Sequences, Vol. 9 (2006),
Article 06.3.8.
[2] Tom Mueller, On
Anti-Elite Prime Numbers, J. Integer Sequences, Vol. 10 (2007), Article
07.9.4.
[3] Chris Caldwell, The Prime Pages: Jacobi symbol.
[4] Alexander Aigner; Üeber Primzahlen,
nach denen (fast) alle Fermatzahlen quadratische Nichtreste sind. Monatsh.
Math. 101 (1986), pp. 85-93.
[5] Wilfrid Keller, Fermat factoring status.
Copyright © 2008-2009 by Dennis R. Martin, ALL RIGHTS
RESERVED.
No part of this document may be reproduced, retransmitted, or
redistributed by any means, without providing a proper reference crediting
Dennis R. Martin.