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 F_m = 2^(2^m) + 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 = 2^Sh + 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 F_S 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:

1. 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.
2. Determine the latest possible Fermat period start S.
3. Inside of a For/Next loop from 0 to S, compute the Fermat residues modulo p up to F_S and save those residues in an array. If a period is completed (if a residue repeats) prior to F_S being reached, then flag that condition and exit the loop.
4. Calculate the Jacobi symbol of the last residue r, which will either correspond to F_S (if the loop in step 3 was completed to S) or will correspond to the term at the end of a period, F_e where e = s + L – 1 (if the loop in step 3 was exited early).
5. 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.
6. 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.
7. 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 r_e+1 = r_s 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 F_S from step 4, then p can be neither elite nor anti-elite, so exit and go on to the next candidate.
8. Find the index of the first repeating residue r_s 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 F_e from step 4, then p can be neither elite nor anti-elite, so exit and go on to the next candidate.
9. 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.

 

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.