Primality testing with Gaussian periods

DOI10.4171/JEMS/861zbMath1429.11221WikidataQ128620669 ScholiaQ128620669MaRDI QIDQ1737980

Hendrik W. jun. Lenstra, Carl B. Pomerance

Publication date: 24 April 2019

Published in: Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)

zbMATH Keywords

primality testingconstructing finite fieldscontinuous Frobenius problemperiod systempseudo field

Mathematics Subject Classification ID

Primes in congruence classes (11N13) Primality (11Y11) Inverse problems of additive number theory, including sumsets (11P70)

Related Items

On a modification of the Lucas primality test, On some algebraic ways to calculate zeros of the Riemann zeta function, Algorithms for the Multiplication Table Problem, A logarithmic improvement in the Bombieri-Vinogradov theorem, The minimal polynomial of \(2 \cos(\pi /q)\) and Dickson polynomials, There are infinitely many Perrin pseudoprimes, On some subgroups of the multiplicative group of finite rings, A framework for deterministic primality proving using elliptic curves with complex multiplication, Two algorithms to find primes in patterns, On Toric Orbits in the Affine Sieve, A variant of the Bombieri-Vinogradov theorem with explicit constants and applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• When the sieve works
• Kloosterman sums and Fourier coefficients of cusp forms
• PRIMES is in P
• Fast computation of special resultants
• Detecting perfect powers by factoring into coprimes
• Proving primality in essentially quartic random time
• The large sieve
• Fast Multiple-Precision Evaluation of Elementary Functions
• Sharpening ``Primes is in P for a large family of numbers
• THE CONTINUOUS POSTAGE STAMP PROBLEM
• Fast construction of irreducible polynomials over finite fields
• On the difference between consecutive primes