Journal of Integer Sequences, Vol. 14 (2011), Article 11.1.2

On the Complexity of Testing Elite Primes


Michal Křížek
Institute of Mathematics
Academy of Sciences
Žitná 25
CZ -- 115 67, Praha 1
Czech Republic

Florian Luca
Instituto de Matemáticas
Universidad Nacional Autonoma de México
C.P. 58089, Morelia, Michoacán
México

Igor E. Shparlinski
Department of Computing
Macquarie University
Sydney, NSW 2109
Australia

Lawrence Somer
Department of Mathematics
Catholic University of America
Washington, DC 20064
USA

Abstract:

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.


Full version:  pdf,    dvi,    ps,    latex    


(Concerned with sequences A102742 A128852 .)


Received October 12 2010; revised version received December 20 2010. Published in Journal of Integer Sequences, January 4 2011.


Return to Journal of Integer Sequences home page