Geodesic
On the complexity of testing elite primes
Journal of integer sequences, Tome 14 (2011) no. 1.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: 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.
Classification : 11A07, 11L40
Keywords: elite prime testing, character sum 
@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},
     publisher = {mathdoc},
     volume = {14},
     number = {1},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JIS_2011__14_1_a5/}
}
TY  - JOUR
AU  - Křížek, Michal
AU  - Luca, Florian
AU  - Shparlinski, Igor E.
AU  - Somer, Lawrence
TI  - On the complexity of testing elite primes
JO  - Journal of integer sequences
PY  - 2011
VL  - 14
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JIS_2011__14_1_a5/
LA  - en
ID  - JIS_2011__14_1_a5
ER  - 
%0 Journal Article
%A Křížek, Michal
%A Luca, Florian
%A Shparlinski, Igor E.
%A Somer, Lawrence
%T On the complexity of testing elite primes
%J Journal of integer sequences
%D 2011
%V 14
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JIS_2011__14_1_a5/
%G en
%F 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/