Recent developments in primality testing

DOI10.1007/BF03022861zbMath0476.10004WikidataQ129920587 ScholiaQ129920587MaRDI QIDQ1160213

Carl B. Pomerance

Publication date: 1981

Published in: The Mathematical Intelligencer (Search for Journal in Brave)

zbMATH Keywords

polynomial time algorithmprimality testingprobabilistic criteriapower reciprocitystrong pseudoprime

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to number theory (11-02) Factorization; primality (11A51) Power residues, reciprocity (11A15) Primality (11Y11)

Related Items

Even faster integer multiplication, Zassenhaus conjecture on torsion units holds for \(\mathrm{PSL}(2,p)\) with \(p\) a Fermat or Mersenne prime, The influence of computers in the development of number theory, Primality testing, Sequences of numbers generated by addition in formal groups and new primality and factorization tests, On the Stability of m-Sequences, The RSA Cryptography Processor, Number theory and the real world, Factoring on a computer, An Overview of Factoring, Carmichael's ``Empirical Theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the exact number of primes less than a given limit
• Probabilistic algorithm for testing primality
• A new lower bound for the pseudoprime counting function
• Riemann's hypothesis and tests for primality
• Miller's primality test
• Cryptology: The mathematics of secure communication
• Some probabilistic remarks on Fermat's last theorem
• Approximate formulas for some functions of prime numbers
• The least quadratic non residue
• The 25th and 26th Mersenne Primes
• The Pseudoprimes to 25 ⋅10 9
• Asymptotically Fast Factorization of Integers
• A Method of Factoring and the Factorization of F 7
• New Primality Criteria and Factorizations of 2 m ± 1
• Every Prime Has a Succinct Certificate
• Some Algorithms for Prime Testing Using Generalized Lehmer Function
• A Fast Monte-Carlo Test for Primality
• A method for obtaining digital signatures and public-key cryptosystems
• Some Observations on Primality Testing
• A note on monte carlo primality tests and algorithmic information theory
• On the Distribution of Pseudoprimes
• The 24th Mersenne Prime
• Three New Mersenne Primes and a Statistical Theory
• On Almost Primes