Cryptography: Test for Primality

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

•Traditional method: divide by all numbers (primes) in turn less than the square root of the number.

–only works for small numbers

•Alternatively use statistical primality tests based on properties of primes for which all primes numbers satisfy property

–but some composite numbers, called pseudo-primes, also satisfy the property

 

•One attractive and popular algorithm:

  Miller-Rabin Algorithm

•A most notable feature of this algorithm is that it only makes a probabilistic assessment of primality: If the algorithm says that the number is composite (the same thing as not a prime), then the number is definitely not a prime.

•On the other hand, if the algorithm says that the number is a prime, then with a very small probability the number may not actually be a prime.

–With proper algorithmic design, this probability can be made so small that, as someone has said, there would be a greater probability that, as you are sitting at a workstation, you’d win a lottery and get hit by a bolt of lightening at the same time.

•This algorithm used to test a large number for primality.

•Miller-Rabin Algorithm is Based on an Intuitive Decomposition of an Even Number into Odd and Even Parts

•Basic:

Any positive odd integer n ≥ 3 can be expressed as

  n - 1 = 2kq with k > 0, q odd

Properties of Prime Numbers 

For any numbers to be prime, two properties needs to be satisfied.

The first property is stated as follows:

If p is prime and a is a positive integer less than p, then a2 mod p = 1 if and only if either

  a mod p = 1 or a mod p = -1 mod p = p - 1.

•By the rules of modular arithmetic
(a mod p)(a mod p) = a2 mod p.

•Thus, if either a mod p = 1 or a mod p = -1, then a2 mod p = 1.

•Conversely, if a2 mod p = 1, then (a mod p)2 = 1, which is true only for a mod p = 1 or a mod p = -1

●   Miller-Rabin Algorithm

TEST (n) is:

1. Find integers k, q, k > 0, q odd, so that (n–1)=2kq

2. Select a random integer a, 1<a<n–1

3. if aq mod n = 1 then return (“inconclusive");

4. for j = 0 to k – 1 do

  5. if (a2jq mod n = n-1)

    then return(“inconclusive")

6.   else return (“composite")

 

•Given an odd number n that is not prime and a randomly chosen integer, a with 1 < a < 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.