素性测试：Miller-Rabin方法

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 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 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 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 ).

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

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

This definition allows us to arrive at some fundamental conclusions:

If is prime, then it is pseudoprime for any not null.
If an can be found such that does not satisfy the definition of pseudoprimality, then 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 . If it is false, then is composite with absolute certainty, otherwise, it is (hoped) that is prime. More correctly, in this case, what is known is that 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 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.

Persistence

REST

Security

1. Introduction

2. Pseudoprimality