Note from OEIS Editor: This is a cached copy of Dennis R. Martin's "Elite and Anti-Elite Prime Search Methodology", obtained from Internet Archive with URL http://web.archive.org/web/20131208101916/http://primenace.com/papers/math/EliteAndAntiEliteSearchMethodology.htm, and stored with permission of the author at OEIS. The name of this document should stay as a102742_1.html so that the links from other two cached documents will work as expected.


 

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:

  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 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.
  4. 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).
  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 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.
  8. 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.
  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.

 

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.

 

[6] N. J. A. Sloane, Online Encyclopedia of Integer Sequences (OEIS), electronically published at: https://oeis.org/.

 

[7] M. K�ek, F. Luca, L. Somer, On the convergence of series of reciprocals of primes related to the Fermat numbers. J. Number Theory 97 (2002), 95�112.

 

[8] Dennis R. Martin, Elite Prime Search.

 

[9] Dennis R. Martin, Anti-Elite Prime Search.

 

 

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.