Primality Test: Miller-Rabin Method | Baeldung on Computer Science

1. Introduction

We studied in a previous tutorial the general laws and computational complexity of cryptographic algorithms. Many of these algorithms rely on the generation and manipulation of very large primes. The reasonable assurance of their primality becomes, therefore, an essential aspect.

The most immediate verification of primality is the trial division. This consists of an attempt to divide $n$ successively by every integer $a \geq2$ . However, it requires an exponential and not a polynomial time.

In this tutorial, we’ll study one of the methods used to verify if $n$ is prime without resorting to factorization: the Miller-Rabin method. We’ll introduce this method as a way of reducing the error rate of a simpler procedure: the pseudoprimality test.

2. Pseudoprimality

Congruence modulo $n$ is a congruence relation, meaning that it’s an equivalence relation that is compatible with the operations of addition, subtraction, and multiplication. We write:

$a\equiv b\pmod n$

The parentheses mean that $\pmod n$ applies to the entire equation, not just to the right-hand side (here $b$ ).

It is said that $n$ is a pseudoprime of base- $a$ if $n$ is composite and occurs:

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

This definition allows us to arrive at some fundamental conclusions:

If $n$ is prime, then it is pseudoprime for any $a$ not null.
If an ${a$ can be found such that $n$ does not satisfy the definition of pseudoprimality, then $n$ is certainly composite.
Surprisingly, the inverse is (almost) valid, and constitutes an almost perfect primality check. The procedure consists of verifying the pseudoprimal condition for $a = 2$ . If it is false, then $n$ is composite with absolute certainty, otherwise, it is (hoped) that $n$ is prime. More correctly, in this case, what is known is that $n$ is either prime or base-2 pseudoprime.

The following pseudocode implements the primality test defined in the last point, for $n> 2$ :

algorithm Pseudoprime(n):
    // INPUT
    //    n = the number to test for pseudoprimality
    // OUTPUT
    //    COMPOSITE if n is definitely composite
    //    PRIME if n is probably prime

    if 2^(n-1) mod n != 1:
        return COMPOSITE
    else:
        return PRIME

The PSEUDOPRIME function produces errors when $n$ is prime but is also base-2 pseudoprime. If it is composite, it always gives a correct result. The following section shows how we can reduce this error rate.

3. Miller-Rabin Primality Test

The Miller-Rabin test implements two modifications to the PSEUDOPRIME function. The first one is to choose several randomly selected values rather than using a single base value. The second modification lies in an important number theory theorem, which demonstrates the following:

Given two numbers $p$ and $e$ , where $p$ is an odd prime number and $e \geq1$ , then the equation:

$x ^ {2} \equiv1 \pmod {p ^ {e}}$

has only the solutions $x = 1$ and $x = -1$ .

A corollary of this theorem states that if there exists a non-trivial square root of $1 \pmod n$ , that is:

$x ^ {2} \equiv1 \pmod n$

then $n$ is composite.

On the basis of this corollary, the Miller-Rabin test calculates each modular exponentiation and checks if there’s a non-trivial square root of ${1 \pmod n}$ . In this case, the test ends with the COMPOSITE result.

The Miller-Rabin test is a probabilistic search for proof that ${n}$ is composite.

3.1. The Concept of Witness

For each $a \in [1: n-1], \, n> 2$ it is possible to realize the control we used in the PSEUDOPRIME procedure with $a = 2$ :

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

However, it is more efficient to introduce the concept of witness:

$a$ is said to be a witness that $n$ is composite if it is possible to use $a$ to prove that $n$ is composite.

The concept of witness is not a simple implementation question. It is fundamental from a theoretical point of view and supposes a stronger condition than the pseudoprimality test.

3.2. Miller-Rabin in Action

We’ll leave out the technical details of building this procedure. Suppose we have a WITNESS (a, n) function. If this function returns TRUE, then $a$ is a witness that $n$ is composite with absolute certainty.

In pseudocode, we give the Miller-Rabin procedure, where $s$ is the number of base values to test randomly chosen from $\mathbb {Z} _ {n} ^ {+}$ :

algorithm MillerRabinTest(n, s):
    // INPUT
    //    n = the number to test for primality
    //    s = the number of base values to test
    // OUTPUT
    //    COMPOSITE = certainty that n is composite
    //    PRIME = almost surely that n is prime

    for j <- 1 to s:
        a <- RANDOM(1, n-1)

        if WITNESS(a, n):
            return COMPOSITE  // certainty
        else:
            return PRIME  // almost surely

The conclusion that one of the $a$ leads to the fact that $n$ is composite is always a correct result.

Suppose that no witness to the fact that $n$ is composite can be found in $s$ proofs. In this case, the MILLER-RABIN function assumes that this happens because there’re no witnesses to find and therefore $n$ is prime.

If $s$ is large enough, the primality conclusion of the MILLER-RABIN function is very likely to be correct. However, there’s a small chance that the procedure will give a false positive if the choice of the $a$ base is unfortunate, that is, that some witness exists even if none have been found.

For a number of $b$ bits, the MILLER-RABIN function requires $\mathcal {O} (sb)$ arithmetic operations and $\mathcal {O} (sb ^ {3})$ bit operations.

3.3. Miller-Rabin Test Error

There’re two reasons why the Miller-Rabin test is preferable to the pseudoprimality test:

In the pseudoprimality test the possibility of error depends on the number $n$ . In the Miller-Rabin test, there’re no good or bad inputs, and the error depends on how big $s$ is and how lucky we’re in choosing the $s$ base numbers $a$ .
Since the concept of witness is a stronger condition than the pseudoprimality test, the number of errors is lower.

Theory justifies the second point by the following theorem:

If $n$ is a composite odd number, then the number of witnesses that $n$ is composite is at least $\frac {n-1} {2}$ .

This result ensures the improbability of not finding witnesses if $n$ is composite.

A precise estimate of the error rate of the Miller-Rabin test is provided by the following theorem:

For any odd integer $n> 2$ and a positive integer $s$ , the probability that the Miller-Rabin test gives an error is at most $2 ^ {- s}$ .

The proof of this result is immediate if we analyze the pseudocode above. If $n$ is composite, each execution of the loop between lines 2 and 9 has at least $\frac {1} {2}$ probability of discovering a witness. For $s$ iterations, the total probability is therefore $\left (\frac {1} {2} \right) ^ {s} = 2 ^ {- s}$ .

An $s = 50$ is sufficient for virtually every conceivable application, but for some uses, it can be much lower. For example, if we want to find large primes by applying the Miller-Rabin test to randomly chosen large integers, then it can be shown that the generation of a false positive is unlikely with only $s = 3$ . For non-randomly numbers, the probability of error increases.

4. Conclusion

In this tutorial, we made a brief excursion on the principles of some primality tests.

Given the non-polynomiality of the test by trial division, alternative procedures are necessary, of which the simplest is the pseudoprimality test. While quite effective, it produces an error rate that may be unacceptable for many applications.

This leads to more elaborate methods, such as the Miller-Rabin test.

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex

Full Archive

About Baeldung