Probabilistic Primality

Deterministic and Probabilistic Testing

A primality test determines whether an integer is prime.

Some algorithms provide absolute certainty. These are deterministic primality tests.

Other algorithms allow a small probability of error. These are probabilistic primality tests.

In practice, probabilistic methods are often much faster and simpler. For cryptographic applications, an error probability smaller than hardware failure rates is usually acceptable.

Modern computational number theory therefore relies heavily on probabilistic primality testing.

Fermat’s Little Theorem

The simplest probabilistic idea comes from Fermat’s little theorem.

If $p$ is prime and

(a,p)=1,

then

a^{p-1}\equiv1\pmod p.

Thus, given an integer $n$ , one may choose a random base $a$ and test whether

a^{n-1}\equiv1\pmod n.

If the congruence fails, then $n$ is certainly composite.

If the congruence holds, then $n$ is called a probable prime to base $a$ .

This test is fast because modular exponentiation can be performed efficiently using repeated squaring.

Pseudoprimes

A composite number satisfying

a^{n-1}\equiv1\pmod n

is called a pseudoprime to base $a$ .

For example,

341=11\cdot31

satisfies

2^{340}\equiv1\pmod{341}.

Thus the Fermat test incorrectly labels $341$ as a probable prime to base $2$ .

Pseudoprimes show that Fermat testing alone is insufficient.

Carmichael Numbers

Some composite numbers fool the Fermat test for every base relatively prime to the number.

These are Carmichael numbers.

An integer $n$ is Carmichael if

a^{n-1}\equiv1\pmod n

for all

(a,n)=1.

The smallest example is

561=3\cdot11\cdot17.

Carmichael numbers are rare but infinite in number.

Their existence demonstrates that probabilistic primality testing requires stronger criteria than simple Fermat congruences.

Miller-Rabin Testing

The Miller-Rabin test refines Fermat’s theorem using additional group structure.

Suppose $n$ is odd and write

n-1=2^sd,

where $d$ is odd.

If $n$ is prime, then for every base $a$ ,

either

a^d\equiv1\pmod n,

or some term in the sequence

a^d, \quad a^{2d}, \quad a^{4d}, \ldots, \quad a^{2^{s-1}d}

is congruent to

-1\pmod n.

If neither condition holds, then $n$ is composite.

Witnesses and Liars

A base $a$ proving compositeness is called a witness.

A base causing the test to incorrectly report probable primality is called a liar.

A remarkable theorem states that if $n$ is composite, then at least three-quarters of possible bases are witnesses.

Therefore a random base detects compositeness with high probability.

After $k$ independent rounds, the probability of failure is at most

4^{-k}.

This decreases exponentially.

Why Miller-Rabin Works Well

The Miller-Rabin test combines:

fast modular arithmetic,
strong algebraic constraints,
exponentially small error probability.

In practice, a handful of random bases gives overwhelming confidence.

For many practical ranges, fixed carefully chosen bases even produce deterministic correctness.

Thus Miller-Rabin is one of the most widely used primality tests in real systems.

Solovay-Strassen Testing

Another probabilistic test uses Euler’s criterion and quadratic residues.

If $p$ is prime, then

a^{(p-1)/2} \equiv \left(\frac{a}{p}\right) \pmod p,

where

\left(\frac{a}{p}\right)

is the Legendre symbol.

The Solovay-Strassen test checks analogous congruences modulo $n$ .

Composite numbers violating the relation are detected immediately.

Although historically important, Solovay-Strassen is usually slower and less preferred than Miller-Rabin.

Error Probability

Probabilistic primality tests are examples of Monte Carlo algorithms.

They may produce incorrect answers, but the error probability can be made arbitrarily small.

Suppose Miller-Rabin is repeated $20$ times independently. Then the probability of mistakenly accepting a composite number is at most

4^{-20}.

This is astronomically small.

In practice, hardware errors or implementation bugs are usually far more likely than a Miller-Rabin failure with standard parameters.

Random Prime Generation

Cryptographic systems require large primes.

Probabilistic primality testing makes prime generation efficient.

The standard process is:

choose a random odd integer,
eliminate small prime divisors,
apply probabilistic primality tests,
repeat if composite.

The prime number theorem implies that primes occur frequently enough that this process succeeds quickly.

Thus probabilistic primality testing enables practical large-scale cryptography.

Probable Primes

A number passing strong probabilistic tests is often called a probable prime.

Cryptographic systems routinely use probable primes rather than formally proved primes.

This is acceptable because the probability of error is negligible.

In contrast, some mathematical applications require absolute certainty. In such cases one uses deterministic primality proofs.

Deterministic Polynomial-Time Testing

The AKS algorithm proved that primality testing belongs to polynomial time deterministically.

This was a major theoretical breakthrough.

However, AKS is usually slower in practice than probabilistic methods such as Miller-Rabin.

Thus computational practice and complexity theory diverge:

deterministic polynomial time is theoretically important,
probabilistic testing remains practically dominant.

Heuristic Models

Probabilistic primality testing reflects a broader theme in number theory: arithmetic often behaves statistically.

Primes themselves are deterministic objects, but probabilistic models accurately describe many aspects of their distribution and computational behavior.

This interaction between exact structure and probabilistic reasoning is one of the defining features of modern computational number theory.

Cryptographic Significance

Probabilistic primality testing is foundational in public-key cryptography.

Applications include:

System	Use of Probable Primes
RSA	Generating secret primes
Diffie-Hellman	Prime moduli
DSA	Prime subgroup orders
Elliptic curves	Prime-order groups

Without fast probabilistic testing, practical cryptographic key generation would be far slower.

Las Vegas Versus Monte Carlo

Probabilistic algorithms are often classified into two types.

A Monte Carlo algorithm may return an incorrect answer with small probability.

A Las Vegas algorithm always returns the correct answer but has random running time.

Miller-Rabin is Monte Carlo because it may incorrectly declare a composite number probably prime.

This distinction is important in computational complexity theory.

Conceptual Importance

Probabilistic primality testing transformed computational number theory.

It showed that randomness can produce algorithms that are:

extremely fast,
mathematically rigorous,
practically reliable.

The subject illustrates how deterministic arithmetic structures can be studied effectively through probability and randomization.

Modern cryptographic infrastructure depends fundamentally on this probabilistic viewpoint.