On the complexity of testing elite primes

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

On the complexity of testing elite primes

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

^*Corresponding author for this work

School of Computing

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

Aigner has defined elite primes as primes p such that all but finitely many of Fermat numbers F(n) = 2²ⁿ + 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.

Original language	English
Pages (from-to)	1-5
Number of pages	5
Journal	Journal of Integer Sequences
Volume	14
Issue number	1
Publication status	Published - 2011

Cite this

@article{c66bb00619014084bd76c0dd08e04b4e,

title = "On the complexity of testing elite primes",

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{\"u}ller and Reinhart in 2008. The same bound O(p3/4) also holds for testing anti-elite primes.",

author = "Michal K{\v r}{\'i}{\v z}ek and Florian Luca and Shparlinski, \{Igor E.\} and Lawrence Somer",

year = "2011",

language = "English",

volume = "14",

pages = "1--5",

journal = "Journal of Integer Sequences",

issn = "1530-7638",

publisher = "University of Waterloo",

number = "1",

}

TY - JOUR

T1 - On the complexity of testing elite primes

AU - Křížek, Michal

AU - Luca, Florian

AU - Shparlinski, Igor E.

AU - Somer, Lawrence

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/78751486841

M3 - Article

AN - SCOPUS:78751486841

SN - 1530-7638

VL - 14

SP - 1

EP - 5

JO - Journal of Integer Sequences

JF - Journal of Integer Sequences

IS - 1

ER -

On the complexity of testing elite primes

Abstract

Other files and links

Fingerprint

Cite this