Section 6.3 Primality testing
One of the most important areas where non-deterministic methods are used in cryptography is in the area of producing and testing numbers that are highly likely to be prime - that is, it is quite expensive to determine with absolute certainty that a number n is prime, but it can be checked to any amount of desired likelihood. (Such primes are sometimes referred to as industrial-grade primes - that is, good enough for application.) The idea is that even if the tests miss an occasional number that isn't prime, it happens so infrequently that the economic cost of looking for one is prohibitive. Recall that a composite number is a number that has two or more non-trivial factors. We'll begin by looking at conditions that prime numbers always satisfy. What springs to mind is Fermat's little theorem Theorem 2.6.1. We will adopt a slightly modified version that removes the restrictions on a.Theorem 6.3.1. Modified Fermat's theorem.
pa
apβ‘amodp.
29β‘8mod9
and so 9 (shockingly) cannot be prime. This sort of test is exclusive -- we can exclude numbers that fail, but passing the test for a given value of a does not mean that n is prime! For example,
621β‘6mod21
and yet 21 is obviously not prime.
We take the position that 2 βseesβ the compositeness of 9, but that 6 does not see the compositeness of 21. In this light, we define the notion of a witness of compositeness.
Definition 6.3.2.
A number a is said to be a (Fermat) witness for the compositeness of a composite number n if
anβ amodn.
a531=amod531
for every integer a, and thus has no witnesses to the fact that it is composite. There are infintely many Carmichael numbers, and so it behooves us to develop a test so that every composite n has lots of witnesses.
One such test is called the Miller-Rabin test, which relies on Fermat's little theorem as its background assumption but provides a further discrimination that gives every composite number lots of witnesses.
Theorem 6.3.3.
p
pβ1=2kq where q is odd.
apβ€a.- aqβ‘1modp;
- A number in the listaq,a2q,a4qβ¦,a2kβ1qis congruent to β1modp.
Proof.
\begin{equation*}
a^{2^k q} = a^{p-1} \equiv 1 \mod p.
\end{equation*}
The list
\begin{equation*}
a^q, a^{2q}, \ldots, a^{2^{k-1}q}, a^{2^k q} = 1
\end{equation*}
is a list of repeated squarings. Since the last number is 1, the previous number must have been 1 or -1. If the previous number is -1, we're finished. If the previous number is 1, then the number prior to that much have been 1 or -1 and so on down the chain. If we reach the first number in the list, it must be 1 or -1 because the next number was 1. If it is -1, then we're done. If it is 1, we're in the first condition, completing the proof.Definition 6.3.4.
Let n be odd and write nβ1=2kq with q odd. An integer a with gcd(a,n)=1 is a Miller-Rabin witness for the compositeness of n if- aqβ 1modn and
- a2iqβ β1modn for any i=1,β¦,kβ1
Algorithm 6.3.5.
na- If n is even, then n is composite.
- If 1<gcd(a,n)<n, then n is composite.
- Write nβ1=2kq
- Set a=aqmodn and i=0.
- If a=1modn, the test is inconclusive.
- If a=β1modn, the test is inconclusive.
- If i<kβ1, set a = a^2 \mod n\text{,} increment i\text{,} and return to 6.
- Else n is composite.
divmod
, which is the library function for division with remainder. A segment of hint code follows.
xxxxxxxxxx
n = 37
m = n -1
i, q, r = 0,0,0
while True:
q, r = divmod(m, 2)
if r == 1:
break
m = q
i = i + 1
print("%d has the form (2^%d)%d"%(n-1, i, m))
Proposition 6.3.6.
Let n be an odd composite number. Then at least 75% of integers 1 \lt a \leq n-1 are Miller-Rabin witnesses for the compositeness of n\text{.}