Primality Testing - Miller Rabin Algorithm

For many cryptographic algorithms, it is necessary to select one or more very large prime numbers at random.Thus, we are faced with the task of determining whether a given large number is prime.There is no simple yet efficient means of accomplishing this task.

In this section, we present one attractive and popular algorithm.You may be surprised to learn that this algorithm yields a number that is not necessarily a prime. However, the algorithm can yield a number that is almost certainly a prime.

Miller-Rabin Algorithm

The algorithm due to Miller and Rabin  is typically used to test a large number for primality. Before explaining the algorithm, we need some background.

First, any positive odd integer $n \ge 3$ can be expressed as

$$n-1=2^k.q \quad \text{with} \: k \gt 0, q \: odd$$

To see this, note that $n-1$ is an even integer. Then, divide $(n-1)$ by 2 until the result is an odd number $q$ , for a total of $k$ divisions. If  $n$ is expressed as a binary number, then the result is achieved by shifting the number to the right until the rightmost digit is a 1, for a total of $k$ shifts.We now develop two properties of prime numbers that we will need.

Properties:

The first property is stated as follows:If $p$ is prime and $a$ is a positive integer less than $p$. then $a^2 \pmod{p}=1$, if and only if either $a \pmod{p}=1$ or $a \pmod{p}=-1$.

The second property is stated as follows: Let $p$ be a prime number greater than 2.We can then write $p-1=2^k.q$, with $k >0$ $q$ odd. Let $a$ be any integer in the range $1 \lt a \lt p$.Then one of the two following conditions is true.

1.$a^q$ is congruent to 1 modulo $p$.  or equivalently,$a^q \equiv 1 \pmod{p}$

2. One of the numbers $a^q,a^{2q},a^{4q},\ldots,a^{2^{k-1}q}$ is congruent to -1 modulo $p$.That is, there is some number $j$ in the range $(1 \le j \le k)$ such that $ a^{2^{j-1}q} \equiv -1 \pmod{p}$.

Proof:

Fermat’s theorem  states that $a^{n-1} \equiv 1 \pmod{n}$ if $n$  is prime. We have $p-1=2^k.q$. Thus, we know that $a^{p-1} \pmod{p}=a^{2^k.q} \pmod{p}=1$.Thus, if we look at the sequence of numbers

$$a^q \pmod{p},a^{2q} \pmod{p},\ldots,a^{2^kq} \pmod{p}$$

We know that the last number in the list has value 1. Further, each number in the list is the square of the previous number. Therefore, one of the following possibilities must be true.

1. The first number on the list, and therefore all subsequent numbers on the list, equals 1.

2. Some number on the list does not equal 1, but its square mod does equal 1. By virtue of the first property of prime numbers defined above, we know that the only number that satisfies this condition is $p-1$(-1). So, in this case, the list contains an element equal to $p-1$.

This completes the proof.

Algorithm

We can use the preceding property to devise a test for primality.The procedure TEST takes a candidate integer $n$ as input and returns the result composite if $n$ is definitely not a prime, and the result inconclusive if $n$ may or may not be a prime.

TEST ($n$ )

1. Find integers $k$ , $q$ , with $k \gt 0$, $q$, odd, so that $n-1=2^k.q$

2. Select a random integer $a$;$1 < a < n-1$

3. if  $a^q \pmod{n}=1$ then return(" inconclusive ");

4. for $j=0$ to $k-1$ do

5. if $a^{2^jq}\pmod{n}=n-1$ then return( inconclusive );

6. return("composite");

Example:

REPEATED USE OF THE MILLER-RABIN ALGORITHM How can we use the Miller-Rabin algorithm to determine with a high degree of confidence whether or not an integer is prime? It can be shown that given an odd number that is not prime and a randomly chosen integer $a$, with $1 \lt a \lt n-1$, the probability that TEST will return inconclusive (i.e., fail to detect that $n$ is not prime) is less than 1/4. Thus, if $t$ different values of $a$ are chosen, the probability that all of them will pass TEST (return inconclusive) for $n$ is less than $(1/4)^t$. For example, for $t=10$ , the probability that a nonprime number will pass all ten tests is less than $10^{-6}$ .Thus, for a sufficiently large value of $t$, we can be confident that $n$ is prime if Miller’s test always returns inconclusive.

This gives us a basis for determining whether an odd integer $n$ is prime with a reasonable degree of confidence. The procedure is as follows: Repeatedly invoke TEST ($n$ ) using randomly chosen values for $a$. If, at any point, TEST returns composite, then $n$ is determined to be nonprime. If TEST continues to return inconclusive for $t$ tests, then for a sufficiently large value of $t$, assume that $n$  is prime.

Conclusion: If $n$ passes the test for all chosen witnesses, then it is likely prime. However, if $n$ fails the test for any witness, then it is definitely composite.

It's important to note that while the Miller-Rabin algorithm is probabilistic, the probability of misidentifying a composite number as prime can be made extremely low by choosing a sufficient number of random witnesses. This makes it very reliable in practice for large numbers.

A Deterministic Primality Algorithm

Prior to 2002, there was no known method of efficiently proving the primality of very large numbers. All of the algorithms in use, including the most popular (Miller-Rabin), produced a probabilistic result. In 2002, Agrawal, Kayal, and Saxena developed a relatively simple deterministic algorithm that efficiently determines whether a given large number is a prime.The algorithm, known as the AKS algorithm, does not appear to be as efficient as the Miller-Rabin algorithm.

Python Code:

import random

def miller_rabin(n, k=5):

    if n == 2 or n == 3:

        return True

    if n < 2 or n % 2 == 0:

        return False

    

    # Express n - 1 as (2^r) * d

    r, d = 0, n - 1

    while d % 2 == 0:

        r += 1

        d //= 2

    

    # Perform k rounds of Miller-Rabin test

    for _ in range(k):

        a = random.randint(2, n - 2)

        x = pow(a, d, n)

        

        if x == 1 or x == n - 1:

            continue

        

        for _ in range(r - 1):

            x = pow(x, 2, n)

            if x == n - 1:

                break

        else:

            return False

    

    return True

# Example usage:

n = 21

if miller_rabin(n):

    print(n, "is probably prime.")

else:

    print(n, "is composite.")