The Miller-Rabin Primality Test

Matt George

Fractional CTO · Founder of Injuria.ai

•22 min read•

The Miller-Rabin primality test is a probabilistic algorithm used to determine whether a given integer is prime or composite.[24] It belongs to the broader class of randomized algorithms known as Monte Carlo algorithms, which are computational procedures that rely on random sampling to produce a result that has a bounded probability of being incorrect. In the context of primality testing, the Miller-Rabin algorithm identifies composite numbers with absolute mathematical certainty, but it can only declare a number to be a probable prime if it passes specific algebraic criteria. By repeating the algorithm with different random inputs, the probability of a false positive (identifying a composite number as prime) can be reduced to an arbitrarily small value. This test is a foundational component of modern computational number theory and cryptography, providing the speed and reliability required to generate the large prime numbers used in public-key cryptosystems. Handbook of Applied Cryptography[1]

Unlike deterministic algorithms that provide an unconditional mathematical proof of primality, probabilistic tests like Miller-Rabin prioritize computational efficiency. Generating keys for cryptographic protocols requires testing hundreds or thousands of large candidate numbers until a prime is found. Deterministic tests are generally too slow for this purpose when dealing with numbers that are hundreds or thousands of bits long. The Miller-Rabin test offers an optimal balance, executing in polynomial time while allowing the user to bound the error probability well below the likelihood of a hardware failure. Prime Numbers: A Computational Perspective[2]

The algorithm relies on two fundamental properties of prime numbers: Fermat's Little Theorem and the algebraic behavior of square roots of unity modulo a prime.[25] By combining these mathematical principles, the test successfully filters out almost all composite numbers, including the deceptive Carmichael numbers that defeat simpler primality tests. Today, it is the standard algorithm used in nearly all software libraries and security protocols that require prime number generation. Applied Cryptography[3]

Mathematical Foundations and Problem Definition

The primary problem the Miller-Rabin test solves is the efficient identification of prime numbers for use in computer science. The simplest method of primality testing is trial division, which involves dividing the candidate number $n$ by every integer up to its square root. While perfectly accurate, trial division has an exponential time complexity relative to the number of digits in $n$. For a cryptographic key of 2048 bits, trial division would require more operations than there are atoms in the observable universe, rendering it useless for modern applications. The Art of Computer Programming, Volume 2: Seminumerical Algorithms[4]

To achieve better performance, mathematicians turned to properties that hold true for all prime numbers. The most famous of these is Fermat's Little Theorem. The theorem states that if $p$ is a prime number and $a$ is an integer not divisible by $p$, then $a^{p-1} \equiv 1 \pmod p$. If a number $n$ does not satisfy this congruence for some base $a$, then $n$ is guaranteed to be composite. This forms the basis of the Fermat primality test, which simply selects a random base $a$ and checks if the congruence holds. Handbook of Applied Cryptography[1][25]

However, the Fermat primality test has a fatal mathematical flaw. There exist composite numbers that satisfy Fermat's congruence for all bases $a$ that are coprime to $n$. These numbers are known as Carmichael numbers. The structural definition of these numbers was formalized by Alwin Korselt in 1899. Korselt's criterion states that a positive integer $n$ is a Carmichael number if and only if $n$ is composite, square-free, and for all prime divisors $p$ of $n$, the value $p - 1$ divides $n - 1$. Prime Numbers: A Computational Perspective[2]

The smallest Carmichael number is 561. Its prime factorization is $3 \times 11 \times 17$. It is square-free because no prime factor is repeated. Applying Korselt's criterion, we see that $3 - 1 = 2$, which divides 560; $11 - 1 = 10$, which divides 560; and $17 - 1 = 16$, which also divides 560. Because Carmichael numbers pass the Fermat test for almost all bases, the Fermat test cannot reliably identify them as composite. In 1994, mathematicians proved that there are infinitely many Carmichael numbers, meaning a more robust test was required. There are infinitely many Carmichael numbers

The Miller-Rabin test overcomes this limitation by incorporating a second mathematical property regarding the square roots of unity. In modular arithmetic, if $p$ is an odd prime, the equation $x^2 \equiv 1 \pmod p$ has exactly two solutions: $x \equiv 1 \pmod p$ and $x \equiv -1 \pmod p$. These are known as the trivial square roots of 1. This is because $x^2 - 1 = (x - 1)(x + 1) \equiv 0 \pmod p$. Since $p$ is prime, it must divide either $(x - 1)$ or $(x + 1)$. Handbook of Applied Cryptography[1]

If $n$ is an odd composite number, the situation changes due to the Chinese Remainder Theorem. Suppose $n = p \cdot q$, where $p$ and $q$ are distinct odd primes. The congruence $x^2 \equiv 1 \pmod p$ has two solutions, and $x^2 \equiv 1 \pmod q$ has two solutions. By the Chinese Remainder Theorem, the combined system modulo $n$ has $2 \times 2 = 4$ solutions. Two of these are the trivial solutions $1$ and $-1$. The other two are non-trivial square roots of unity. More generally, if a composite number $n$ has $k$ distinct odd prime factors, the equation $x^2 \equiv 1 \pmod n$ has $2^k$ solutions, of which $2^k - 2$ are non-trivial. The Miller-Rabin algorithm searches for these non-trivial square roots. If it finds a number $x$ such that $x^2 \equiv 1 \pmod n$ but $x$ is neither $1$ nor $-1$, it has definitively proven that the number $n$ is composite. Prime Numbers: A Computational Perspective[2]

The Mechanism of the Test

The Miller-Rabin test operates by factoring out powers of 2 from the even number $n - 1$. Let $n > 2$ be an odd integer to be tested for primality. Because $n$ is odd, $n - 1$ is even. We can write $n - 1$ in the form $2^s \cdot d$, where $s$ is a positive integer and $d$ is an odd integer. This factorization is achieved by repeatedly dividing $n - 1$ by 2 until the result is odd. Handbook of Applied Cryptography[1]

The algorithm then selects a random integer $a$, called the base, in the range $2 \le a \le n - 2$. It computes the value $x = a^d \pmod n$. If $x \equiv 1 \pmod n$ or $x \equiv -1 \pmod n$, the number $n$ passes the test for this base and is declared a probable prime.

If $x$ is neither 1 nor $-1$, the algorithm repeatedly squares $x$ modulo $n$. It computes $x^2 \pmod n$, $x^4 \pmod n$, up to $x^{2^{s-1} \cdot d} \pmod n$. During this sequence of squarings, if the value ever becomes $-1 \pmod n$, the number $n$ passes the test and is a probable prime. If the sequence reaches 1 without the preceding value being $-1$, the algorithm has found a non-trivial square root of 1, and $n$ is definitely composite. If the sequence finishes $s - 1$ squarings without ever reaching $-1$, $n$ is also composite by Fermat's Little Theorem, because $a^{n-1} \not\equiv 1 \pmod n$. Probabilistic algorithm for testing primality[5]

A composite number that passes the test for a specific base $a$ is called a strong pseudoprime to the base $a$. To reduce the chance of encountering a strong pseudoprime, the algorithm is repeated $k$ times with $k$ independently chosen random bases.[26]

The following pseudocode demonstrates the exact mechanism:

Input: n > 3, an odd integer to be tested for primality
Input: k, the number of rounds of testing to perform

Write n - 1 as 2^s * d with d odd by factoring powers of 2 from n - 1

Loop k times:
    Pick a random integer a in the range [2, n - 2]
    x = a^d mod n
    
    If x == 1 or x == n - 1:
        Continue to next loop iteration
        
    For r = 1 to s - 1:
        x = x^2 mod n
        If x == n - 1:
            Break out of inner loop and continue to next loop iteration
            
    Return "Composite"
    
Return "Probably Prime"

To illustrate how the test catches Carmichael numbers, consider $n = 561$. We write $561 - 1 = 560 = 16 \times 35$, so $s = 4$ and $d = 35$. If we choose the base $a = 2$, we first compute $2^{35} \pmod{561}$, which is 263. We then square this value repeatedly. The first squaring yields $263^2 \pmod{561} = 166$. The second squaring yields $166^2 \pmod{561} = 67$. The third squaring yields $67^2 \pmod{561} = 1$. The sequence of values is 263, 166, 67, 1. Because the value 67 squared is 1 modulo 561, but 67 is neither 1 nor 560 (which is $-1 \pmod{561}$), 67 is a non-trivial square root of 1. The test correctly identifies 561 as composite, succeeding where the Fermat test fails. The pseudoprimes to 25.10^9[6]

Conversely, consider a true prime number, such as $n = 37$. We write $37 - 1 = 36 = 4 \times 9$, so $s = 2$ and $d = 9$. If we choose the base $a = 2$, we first compute $2^9 \pmod{37}$. Since $2^5 = 32 \equiv -5 \pmod{37}$, we can calculate $2^9 = 512$. Dividing 512 by 37 gives a quotient of 13 and a remainder of 31, so $x = 31$. Since 31 is neither 1 nor 36, we enter the squaring loop. We compute $31^2 = 961$. Dividing 961 by 37 gives a quotient of 25 and a remainder of 36. Since $36 \equiv -1 \pmod{37}$, the inner loop condition is met. The algorithm breaks out of the inner loop and correctly declares 37 a probable prime. Prime Numbers: A Computational Perspective[2]

Computational Complexity

The Miller-Rabin test is highly efficient, which is the primary reason for its widespread adoption. The computational complexity is determined by the modular exponentiation step and the subsequent squarings. The Art of Computer Programming, Volume 2: Seminumerical Algorithms[4]

For a given base $a$, computing $a^d \pmod n$ requires $O(\log d)$ modular multiplications using algorithms like binary exponentiation (also known as square-and-multiply). The subsequent loop performs at most $s - 1$ modular squarings. Since $d \cdot 2^s = n - 1$, the total number of modular multiplications per round is strictly bounded by $O(\log n)$. Handbook of Applied Cryptography[1]

The time required for a single modular multiplication depends on the multiplication algorithm used. Using standard grade-school multiplication, multiplying two numbers of size $n$ takes $O(\log^2 n)$ bit operations. Therefore, a single round of the Miller-Rabin test takes $O(\log^3 n)$ time. If the algorithm is run for $k$ rounds, the total time complexity is $O(k \log^3 n)$. Prime Numbers: A Computational Perspective[2]

In practical software implementations, the modular reduction step is heavily optimized using Montgomery reduction. Introduced by Peter L. Montgomery in 1985, this technique transforms the numbers into a special representation called Montgomery form. In this form, the expensive division operations normally required for modular reduction are replaced by simple bitwise shifts and additions. While converting to and from Montgomery form carries a small overhead, the savings during the hundreds of squarings and multiplications in the Miller-Rabin inner loop result in massive performance gains. Modular Multiplication Without Trial Division[7]

When implemented with fast multiplication algorithms designed for massive integers, the theoretical time complexity improves further. The Schönhage-Strassen algorithm, which uses the Fast Fourier Transform (FFT), reduces the time per multiplication to $O(\log n \log \log n \log \log \log n)$. In 2019, David Harvey and Joris van der Hoeven published an algorithm that achieves $O(\log n \log \log n)$ multiplication time. Using these advanced techniques, the overall time complexity of the Miller-Rabin test drops to approximately $\tilde{O}(k \log^2 n)$, where the tilde notation hides logarithmic factors. PRIMES is in P[8]

The space complexity of the algorithm is $O(\log n)$, as it only needs to store a few large integers (such as $n$, $a$, $x$, and $d$) in memory at any given time. This minimal memory footprint makes it suitable for embedded devices, smart cards, and hardware security modules. Applied Cryptography[3]

Error Probability and Accuracy

Because the Miller-Rabin test is probabilistic, it carries a risk of returning a false positive. A false positive occurs when a composite number is incorrectly identified as a probable prime. The accuracy of the test is defined by the probability of this event occurring. Probabilistic algorithm for testing primality[5]

In 1980, Michael Rabin proved a strict mathematical bound on this error. He demonstrated that the bases $a$ that falsely declare a composite number $n$ to be a probable prime form a subset of the multiplicative group of integers modulo $n$, denoted as $(\mathbb{Z}/n\mathbb{Z})^$. Rabin proved that this subset is contained within a proper subgroup of $(\mathbb{Z}/n\mathbb{Z})^$. By Lagrange's theorem, the order of a subgroup must divide the order of the full group. Rabin showed that the index of this subgroup is at least 4, meaning the subgroup contains at most one quarter of the elements of the full group. Therefore, for any odd composite number $n$, at most $1/4$ of the bases in the range $1 \le a \le n - 1$ will falsely identify $n$ as a strong probable prime. Probabilistic algorithm for testing primality[5]

If $k$ bases are chosen uniformly at random, the probability that a composite number passes all $k$ rounds is strictly less than $4^{-k}$. This is a worst-case bound, meaning it holds true even for the most deceptive composite numbers constructed specifically to fool the test.

In practice, the error probability is significantly lower than $4^{-k}$. The $4^{-k}$ bound assumes an adversary has chosen a specific composite number designed to maximize the number of false bases. When generating cryptographic keys, numbers are chosen at random rather than adversarially. In 1993, Ivan Damgård, Peter Landrock, and Carl Pomerance published a detailed analysis of the average-case error estimates for the Miller-Rabin test. They proved that for randomly generated integers of sufficient size, the fraction of bases that act as "strong liars" (bases that falsely report primality) is astronomically smaller than $1/4$. For example, their paper demonstrated that testing a random 1024-bit integer with just six rounds of Miller-Rabin yields an error probability of less than $2^{-100}$. This average-case analysis is what allows modern cryptographic libraries to use relatively small values of $k$ while maintaining absolute security. Average case error estimates for the strong probable prime test[9]

Discovery and Historical Context

The algorithm was developed in two distinct phases by two different computer scientists. The deterministic foundation was laid by Gary Miller in 1976, and the probabilistic modification was introduced by Michael Rabin in 1980. Riemann's Hypothesis and Tests for Primality[10][27]

Gary Miller, working at the University of California, Berkeley, published his paper "Riemann's Hypothesis and Tests for Primality" in 1976. Miller formulated a deterministic primality test based on the Extended Riemann Hypothesis (ERH). The ERH is a profound and unproven conjecture in analytic number theory concerning the zeros of Dirichlet L-functions. Miller proved that if the ERH is true, the multiplicative group modulo $n$ is generated by small primes. Specifically, he showed that if $n$ is composite, there must exist a base $a$ less than or equal to $O(\log^2 n)$ that proves $n$ is composite. By testing all bases up to this logarithmic bound, Miller created a deterministic polynomial-time primality test, conditional entirely on the truth of the ERH. Riemann's Hypothesis and Tests for Primality[10]

Because the ERH remains unproven, Miller's test could not be used as an unconditional proof of primality. In 1980, Michael Rabin, working at the Hebrew University of Jerusalem and the Massachusetts Institute of Technology, published "Probabilistic algorithm for testing primality". Rabin realized that instead of testing all bases up to a specific bound, one could simply choose bases uniformly at random. Rabin proved the $1/4$ error bound, demonstrating that the algorithm succeeds with overwhelming probability regardless of whether the ERH is true. This transformed Miller's conditional deterministic algorithm into an unconditional Monte Carlo probabilistic algorithm. Probabilistic algorithm for testing primality[5]

The immediate predecessor to the Miller-Rabin test was the Solovay-Strassen primality test, published in 1977 by Robert Solovay and Volker Strassen.[28] The Solovay-Strassen test also relies on random bases but uses the Jacobi symbol and Euler's criterion instead of square roots of unity. While historically significant as one of the first randomized algorithms, the Solovay-Strassen test has a worst-case error bound of $1/2$ per round and requires calculating the Jacobi symbol, which is computationally heavier. The Miller-Rabin test quickly superseded Solovay-Strassen due to its tighter $1/4$ error bound and faster execution time. A fast Monte-Carlo test for primality[11]

Deterministic Variants and Base Selection

While the Miller-Rabin test is probabilistic for arbitrarily large numbers, it can be made deterministic for numbers up to a specific size by testing a fixed, precomputed set of bases. If a composite number is smaller than a certain threshold, researchers have exhaustively verified that it will be exposed by at least one base in a specific set. On strong pseudoprimes to several bases

In 1980, Carl Pomerance, John Selfridge, and Samuel Wagstaff published a comprehensive study of strong pseudoprimes. The bases 2, 3, 5, and 7 are only sufficient up to $3,215,031,751$ (or $3.2 \times 10^9$); the $25 \times 10^9$ bound was the search limit of their study. Any number below this threshold that passes the Miller-Rabin test for these four bases is mathematically guaranteed to be prime. The pseudoprimes to 25.10^9[6]

As computing power increased, researchers expanded these bounds through massive computational searches. In 1993, Gerhard Jaeschke showed that testing the bases 2, 3, 5, 7, 11, 13, and 17 is sufficient to deterministically test all numbers up to $341 \times 10^{12}$. On strong pseudoprimes to several bases

In 2015, Jonathan Sorenson and Jonathan Webster extended this work significantly. They demonstrated that testing the first twelve prime bases (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37) deterministically identifies all primes up to $3186 \times 10^{20}$ (or $3.186 \times 10^{23}$). Strong Pseudoprimes to Twelve Prime Bases[12]

These deterministic bounds are heavily utilized in computer science, particularly in software engineering and database management. A standard 64-bit unsigned integer has a maximum value of approximately $18.4 \times 10^{18}$. Because this maximum value is well below the bounds established by Sorenson and Webster, any 64-bit integer can be deterministically proven prime or composite by running the Miller-Rabin test with the first twelve prime bases. This provides a fast, mathematically rigorous primality proof for all numbers that fit within standard 64-bit hardware registers, without relying on probabilistic assumptions or unproven hypotheses. Prime Numbers: A Computational Perspective[2]

The Baillie-PSW Primality Test

A major variant of the Miller-Rabin test is its inclusion in the Baillie-PSW primality test. Invented in 1980 by Robert Baillie, Carl Pomerance, John Selfridge, and Samuel Wagstaff, this algorithm combines a single round of the Miller-Rabin test (using base 2) with a Lucas probable prime test. Lucas Pseudoprimes[13]

The Lucas probable prime test evaluates the candidate number $n$ against a Lucas sequence, which is a sequence of integers defined by a linear recurrence relation with parameters $P$ and $Q$. The test checks properties analogous to Fermat's Little Theorem but operating within a quadratic extension ring rather than the standard integers modulo $n$. The algorithm relies on calculating the Jacobi symbol to select the appropriate parameters for the sequence. Handbook of Applied Cryptography[1]

The rationale behind the Baillie-PSW test is that the composite numbers that pass the Miller-Rabin test (strong pseudoprimes) and the composite numbers that pass the Lucas test (Lucas pseudoprimes) belong to fundamentally different mathematical distributions. Pomerance offered a heuristic argument suggesting that there are no composite numbers that pass both tests simultaneously. The Miller-Rabin test exposes composites based on the structure of the multiplicative group, while the Lucas test exposes composites based on the structure of the quadratic extension. On the distribution of pseudoprimes

To date, no composite number has ever been found that passes the Baillie-PSW test. While it remains mathematically unproven whether such a number exists, the test is considered exceptionally reliable. It is the default primality testing algorithm in many computer algebra systems and programming languages because it provides a higher degree of confidence than multiple random rounds of Miller-Rabin alone, often with less computational overhead. Lucas Pseudoprimes[13]

Real-World Applications and Standards

The Miller-Rabin test is heavily integrated into global technology infrastructure, primarily through its role in public-key cryptography. Cryptosystems such as RSA, Diffie-Hellman key exchange, and the Digital Signature Algorithm (DSA) require the generation of large prime numbers (often 2048 or 4096 bits in length) to construct secure keys. A method for obtaining digital signatures and public-key cryptosystems[14]

The National Institute of Standards and Technology (NIST) mandates the use of the Miller-Rabin test in its cryptographic standards. FIPS 186-5, the latest revision of the Digital Signature Standard published in 2023, specifies that prime parameters must be generated using probabilistic primality tests. The standard explicitly lists the Miller-Rabin test and provides tables detailing the exact number of rounds required to achieve an acceptable error probability (typically less than $2^{-100}$ or $2^{-112}$ depending on the key size). FIPS PUB 186-5: Digital Signature Standard (DSS)[15] Similarly, NIST Special Publication 800-56A requires the test for generating domain parameters for elliptic curve cryptography and finite field cryptography. NIST Special Publication 800-56A Revision 3[16]

Software implementations of the algorithm are ubiquitous. The OpenSSL cryptography library, which secures a vast portion of the internet through the TLS protocol, implements the test in its BN_is_prime_ex function. OpenSSL optimizes the process by first performing trial division against a list of small primes to quickly eliminate obvious composites, followed by multiple rounds of the Miller-Rabin test utilizing Montgomery reduction. OpenSSL Documentation: BN_is_prime_ex[17] The TLS 1.3 specification relies on these underlying library implementations to establish secure connections. RFC 8446: The Transport Layer Security (TLS) Protocol Version 1.3[18] The Secure Shell (SSH) protocol also relies on the algorithm for generating Diffie-Hellman groups. RFC 4253: The Secure Shell (SSH) Transport Layer Protocol[19]

The GNU Multiple Precision Arithmetic Library (GMP), a core component of many Linux systems and mathematical software packages, provides the mpz_probab_prime_p function. GMP uses a highly optimized approach: it performs trial division, followed by one round of the Baillie-PSW test, and then executes additional rounds of the Miller-Rabin test based on the user's requested certainty level. GNU Multiple Precision Arithmetic Library Manual: Number Theoretic Functions

In high-level programming languages, the test is exposed through standard libraries. Java's java.math.BigInteger class includes the isProbablePrime(int certainty) method, which relies on the Miller-Rabin test and, in certain specific code paths, the Lucas probable prime test (the Lucas-Lehmer test is specifically for Mersenne primes). Java Platform, Standard Edition 17 API Specification: Class BigInteger[20] Python's scientific computing library, SymPy, uses deterministic Miller-Rabin bounds for numbers up to $2^{64}$ and probabilistic Miller-Rabin combined with Lucas tests for larger integers in its sympy.ntheory.isprime function. SymPy Documentation: Number Theory[21] The Internet Engineering Task Force (IETF) also references the algorithm in RFC 3447 for RSA cryptography specifications. RFC 3447: Public-Key Cryptography Standards (PKCS) #1[22]

Significance and Tradeoffs

The Miller-Rabin test occupies a specific and highly practical niche in computational mathematics. Its primary advantage is speed. The $O(k \log^3 n)$ time complexity allows it to evaluate numbers with thousands of digits in a fraction of a second on modern hardware. This speed is essential for systems that must generate cryptographic keys on demand, such as secure web servers, virtual private networks, or encrypted messaging applications. Applied Cryptography[3]

However, the algorithm has distinct tradeoffs when compared to other primality testing methods. Because it is a probable prime test, it does not produce a mathematical certificate of primality. If a number passes the test, there is no independently verifiable proof that the number is prime; one must trust that the algorithm was executed correctly and that the random number generator used to select the bases was not compromised. Rabin-Miller primality test: composite numbers which pass it

For applications requiring absolute mathematical certainty, deterministic algorithms are necessary. In 2002, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena published the AKS primality test, proving that primality testing can be solved deterministically in polynomial time without relying on unproven hypotheses like the ERH. While the AKS test is a monumental theoretical achievement that solved a decades-old open problem in computer science, the original 2002 paper established a time complexity of $\tilde{O}(\log^{12} n)$ (the $\tilde{O}(\log^6 n)$ bound was a later improvement), which makes it far too slow for practical use in cryptography. PRIMES is in P[8]

Another alternative is Elliptic Curve Primality Proving (ECPP). ECPP is a deterministic algorithm that generates a mathematically verifiable certificate of primality. It is faster than AKS in practice, running in heuristically polynomial time, but it is still significantly slower and vastly more complex to implement than the Miller-Rabin test. ECPP is typically reserved for mathematical research, such as proving the primality of record-breaking numbers, rather than everyday cryptographic key generation. Elliptic curves and primality proving[23]

The Miller-Rabin test remains the practical standard because the theoretical risk of a false positive can be managed easily. By simply increasing the number of testing rounds $k$, the error probability can be driven below the probability of a cosmic ray altering a bit in the computer's physical memory. For engineering and cryptographic purposes, this level of certainty is functionally equivalent to a deterministic proof, allowing systems to operate securely and efficiently.

Sources (28)
  1. Handbook of Applied Cryptography
  2. Prime Numbers: A Computational Perspective
  3. Applied Cryptography
  4. www-cs-faculty.stanford.edu: The Art of Computer Programming, Volume 2: Seminumerical Alg
  5. Probabilistic algorithm for testing primality
  6. The pseudoprimes to 25.10^9
  7. Modular Multiplication Without Trial Division
  8. PRIMES is in P
  9. Average case error estimates for the strong probable prime test
  10. Riemann's Hypothesis and Tests for Primality
  11. A fast Monte-Carlo test for primality
  12. Strong Pseudoprimes to Twelve Prime Bases
  13. Lucas Pseudoprimes
  14. A method for obtaining digital signatures and public-key cryptosystems
  15. FIPS PUB 186-5: Digital Signature Standard (DSS)
  16. NIST Special Publication 800-56A Revision 3
  17. OpenSSL Documentation: BN_is_prime_ex
  18. IETF
  19. IETF
  20. Java Platform, Standard Edition 17 API Specification: Class BigInteger
  21. SymPy Documentation: Number Theory
  22. IETF
  23. Elliptic curves and primality proving
  24. Richard E. Smith, Authentication (Addison-Wesley Professional, 2002)
  25. Henk C.A. van Tilborg, Sushil Jajodia, Encyclopedia of Cryptography and Security (Springer Science & Business Media, 2011)
  26. Mor Harchol-Balter, Introduction to Probability for Computing (Cambridge University Press, 2023)
  27. Olaf Manz, Encrypt, Sign, Attack (Springer Nature, 2022)
  28. Evangelos Kranakis, Primality and Cryptography (Wiley, 1991)

Recommended reading