On the complexity of testing elite primes

Michal Křížek*, Florian Luca, Igor E. Shparlinski, Lawrence Somer

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)1-5
Number of pages5
JournalJournal of Integer Sequences
Volume14
Issue number1
Publication statusPublished - 2011

Fingerprint

Dive into the research topics of 'On the complexity of testing elite primes'. Together they form a unique fingerprint.

Cite this