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

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*) = 2^{2n}
+ 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 *t*_{p}
and the number of arithmetic operations modulo *p* to test *p*
for being elite are also bounded by *p*. We show that *t*_{p} =
O(*p*^{3/4}), in particular improving the estimate
*t*_{p} ≤
(*p*+1)/4 of Müller and Reinhart in 2008.
The same bound O(*p*^{3/4}) also holds for testing
anti-elite primes.

(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