On the complexity of testing elite primes
Journal of integer sequences, Tome 14 (2011) no. 1
Aigner has defined elite primes as primes $p$ such that all but finitely many of Fermat numbers $F(n) = 2^{2^{n}} + 1, n = 0,1,2,\dots $, 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} \le (p+1)/4$ of Müller and Reinhart in 2008. The same bound $O(p^{3/4})$ also holds for testing anti-elite primes.
@article{JIS_2011__14_1_a5,
author = {K\v{r}{\'\i}\v{z}ek, Michal and Luca, Florian and Shparlinski, Igor E. and Somer, Lawrence},
title = {On the complexity of testing elite primes},
journal = {Journal of integer sequences},
year = {2011},
volume = {14},
number = {1},
zbl = {1226.11013},
language = {en},
url = {http://geodesic.mathdoc.fr/item/JIS_2011__14_1_a5/}
}
Křížek, Michal; Luca, Florian; Shparlinski, Igor E.; Somer, Lawrence. On the complexity of testing elite primes. Journal of integer sequences, Tome 14 (2011) no. 1. http://geodesic.mathdoc.fr/item/JIS_2011__14_1_a5/