Aigner has defined elite primes as primes p such that all but finitely many of Fermat numbers F(n) = 22n + 1, n = 0, 1, 2..., are quadratic nonresidues modulo p. Since the sequence of Fermat numbers is eventually periodic modulo any p with at most p distinct elements in the image, both the period length tp and the number of arithmetic operations modulo p to test p for being elite are also bounded by p. We show that tp = O(p3/4), in particular improving the estimate tp ≤ (p+1)/4 of Müller and Reinhart in 2008. The same bound O(p3/4) also holds for testing anti-elite primes.
|Number of pages||5|
|Journal||Journal of Integer Sequences|
|Publication status||Published - 2011|