Live briefing
Everything about Primality test
Algorithm for determining whether a number is prime
A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy. Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might more accurately be called compositeness tests instead of primality tests. Wikipedia →
🧠Start here: a 6-step reading path
- Read the overview: Primality testA 5-minute orientation
- Skim a recent paper: On the Eight Levels theorem and applications towards Lucas-Lehmer primality test for Mersenne primes, IInfluential work since 2022
- Pick up a classic book: Structure and Interpretation of Computer Programs (SICP)The most-reprinted book on the subject
- Read the landmark paper: A Fast Monte-Carlo Test for PrimalityCited 392 times
- Go sideways: Miller–Rabin primality testA closely related topic
- Go sideways: AKS primality testA closely related topic
đź“– Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
A Fast Monte-Carlo Test for Primality
Implementation of a new primality test
On Lucas's Test for the Primality of Mersenne's Numbers
Erratum: A Fast Monte-Carlo Test for Primality
Miller's primality test
Verification of the Miller–Rabin probabilistic primality test
On Primality Tests
Rabin-Miller primality test: composite numbers which pass it
🆕 Influential since 2022
On the Eight Levels theorem and applications towards Lucas-Lehmer primality test for Mersenne primes, I
On a Combined Primality Test
On a Modification of The Lucas Primality Test
An Intelligent Choice of Witnesses in the Miller–Rabin Primality Test. Reinforcement Learning Approach
Comparing and Reviewing Modern Primality Tests
đź“š Books worth reading
Structure and Interpretation of Computer Programs (SICP)Harold Abelson, Gerald Jay Sussman · 1985
Clean CodeRobert C. Martin · 2008
Introduction to automata theory, languages, and computationJohn E. Hopcroft, Jeffrey D. Ullman · 1979
Data structures and algorithm analysis in CMark Allen Weiss · 1993
An introduction to mathematical cryptographyJeffrey Hoffstein · 2008
Data structures & algorithm analysis in JavaMark Allen Weiss · 1999
McDougal Littell literatureJanet Allen, Janet Allen · 2008
Computer algorithmsEllis Horowitz · 1997
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
đź”— Related topics
- Miller–Rabin primality test The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number…
- AKS primality test The Agrawal–Kayal–Saxena primality test (also known as the AKS primality test and the cyclotomic AKS test) is a deterministic primality-proving algorithm…
- Fermat primality test The Fermat primality test is a probabilistic test to determine whether a number is a probable prime. Fermat's little theorem states that if p is prime…
- Solovay–Strassen primality test The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen in 1977, is a probabilistic primality test to determine if a number…
- Euler–Jacobi pseudoprime In number theory, an odd integer n is called an Euler–Jacobi probable prime (or, more commonly, an Euler probable prime) to base a, if a and n are coprime…
- Lucas–Lehmer primality test In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1878 and subsequentl…
- Probable prime In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied…
- Fermat pseudoprime In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem. Fermat's little theorem…