RA: Primality Testing

PDF of Eric’s handwritten notes is here.

RSA Protocol

We will look at the setting where Alice has some message m that she wants to send to Bob. She encodes this message using the public key that Bob publishes, which will be a pair of numbers (N,e). Bob uses a secret, private key to decrypt incoming messages. This way, even if an eavesdropper gets the encrypted message, she can’t decipher the message provided that the encryption is secure.

Protocol:
Bob:
1) Choose two random n-bit primes p and q for n \approx 2000.
Choose a random n-bit r. Check if it’s prime (we’ll see how to do this in a moment). The probability that it will be prime is \approx 1/n.
2) Find e which is relatively prime to (p-1)(q-1)
(i.e., find e where gcd(e, (p-1)(q-1)) = 1).
3) Let N = pq
4) Publish public key (N,e)
5) Bob’s private key is d = e^{-1} \mod (p-1)(q-1), which we find using the extended Euclid algorithm.
Alice (wants to send a message m to Bob):
1) Looks up Bob’s public key: (N,e)
2) Computes y \equiv m^e \mod N using the fast modular exponentiation algorithm.
3) Sends y to Bob.
Bob:
1) Gets y.
2) Computes y^d \mod N.

Note:  de \equiv 1 \mod (p-1)(q-1).  Therefore, we know that de = 1+k(p-1)(q-1) for some integer k.
Then y^d \equiv (m^e)^d \equiv m^{de} \equiv m\times (m^{(p-1)(q-1)})^{k} \equiv m \mod N by Euler’s theorem when gcd(m,N)=1.
If gcd(m,N) >1 , then the statement is still true (y^d \equiv m \mod N) but to prove it we need to use the Chinese remainder theorem so we’ll skip that here.
Assumption: Given N,e,y, where y\equiv m^e, it is computationally difficult to determine m. The natural way would be to factor N, but there is no known polynomial time algorithm for factoring.

Other issues

If the message corresponds to a small number where m^e < N, then mod N doesn’t do anything so to decrypt the message one just computes m^{1/e} which is easy if e is small.  To avoid this issue, Alice can choose a random string r and pad the message. Alice sends two messages: (m+r)^e and r^e, and Bob can decrypt both and use r to get m.

We also need that m < N, but we can break a large message into smaller messages and encode each smaller message separately.

Primality testing

How do we test whether or not some number x is prime?
If x is prime, then \forall a\in \{1,...,x-1\}, a^{x-1} \equiv 1 \mod x.
If x is composite, then \exists a where a^{x-1}\not \equiv 1\mod x. Such an a will be a witness (or certificate) that x is not prime. Our goal will be to find such an a, if it exists. We call a a Fermat witness (FW).

To see why a composite x always has such an a, consider some composite x and some a such that gcd(a,x) = d>1. (Note, x is composite so x has at least one factor a and this factor a has gcd(a,x)>1.)  Then a^{x-1} and x are multiples of d, say a^{x-1}=di, x=dj for integers i,j.  Hence, a^{x-1} \mod x = a^{x-1} - kx = d(i-kj) for some integer k.  Therefore,   a^{x-1} \mod x is also a multiple of d>1, so a^{x-1} \mod x \neq 1.

This was a trivial Fermat witness because from the gcd statement, we see that d divides x already.

We are looking for nontrivial format witnesses (NFWs). We are looking for an a where gcd(a,x) = 1 and a^{x-1} \not \equiv 1 \mod x.

Not every composite x will have a NFW. The Carmichael numbers are composite x‘s with no NFWs.  Carmichael numbers are rare, the smallest one is 561. We will ignore these “pseudo-primes” for the moment and deal with them later.  It turns out for non-Carmichael composite numbers there are a lot of Fermat witnesses.  By definition, non-Carmichael composite numbers have at least one NFW, and from that we can prove the following lemma saying that there are a lot of Fermat witnesses.

Lemma: If there exists \ge 1 NFW for x, then \ge 1/2 of the a\in \{1,2,...,x-1\} are Fermat witnesses.

Proof:

Let a be a NFW such that gcd(a,x) = 1 and a^{x-1} \not \equiv \mod x. We will prove the lemma by breaking up \{1,...,x-1\} into W and B, where all w\in W satisfy a^{x-1} \not\equiv 1 \mod x and all b\in B satisfy b^{x-1} \equiv 1 \mod x. (So W are Fermat witnesses and B is the “bad” set of non-witnesses.)  Then the lemma is equivalent to saying that |W| \ge |B|. To prove this, we will map elements in B to elements in W such that every element of B is mapped to a unique element of W, and hence W has at least as many elements as B, which proves the lemma.

The mapping that we use for any b\in B is f(b) = ab \mod x. Then (ab)^{x-1} \equiv a^{x-1}b^{x-1} \equiv a^{x-1} \not \equiv 1 \mod x, so f(b)\in W.

Suppose two b‘s map to the same w \in W. Then b'a \equiv ba \mod x. Since a is a NFW so gcd(a,N)=1 which means a^{-1} \mod x exists, so we get b' \equiv b\mod x.  \square

That proves the theorem.  Now (ignoring Carmichael numbers) we have an algorithm to test primality.  Choose a random a from  \left\{1,2,\dots,x-1\right\}, and compute a^{x-1} \mod x to see if this a is a Fermat witness or not.  This will work with probability \geq 1/2 because of the lemma.  To boost the probability we instead choose k numbers from   \{1,2,\dots,x-1\} and test to see if any of these k numbers are Fermat witnesses.  Here is the algorithm in detail:

Primality testing algorithm:

Input: x
Choose a_1,...,a_k randomly from \{1,...,x-1\}.

For i=1 \rightarrow k:

Compute a_i^{x-1} \mod x

If \forall i, a_i^{k-1} \equiv 1 \mod x, output “x is a prime number”
If \exists i such that a_i^{x-1} \not\equiv 1 \mod x, then output “x is composite ”.

If x is prime, then Pr[algorithm says x is prime] = 1. If x is composite and not Carmichael, then Pr[algorithm is wrong] \le (\frac{1}{2})^k.

Dealing with Carmichael numbers

Recall that we put off Carmichael numbers from earlier. Carmichael numbers are composite but have no NFW. For example, 561 is a Carmichael number.

For x,N if x^2 \equiv 1 \mod N, then x is a square root of  1 \mod N.
Note, x \equiv 1 \mod N and x \equiv -1 \equiv N-1 \mod N are always square roots of 1 \mod N. Any other square root is a nontrivial square root of 1 \mod N.

Lemma:
If x is prime, then there are no nontrivial square roots of 1 \mod x.

Proof:

Take z where z^2 \equiv 1 \mod x. Then z^2 -1 \equiv 0 \mod x. Then z^2 -1 = kx. Note that z^2 = (z-1)(z+1). Then z-1 \equiv 0 \mod x or z+1 \equiv 0 \mod x. Then z \equiv 1\mod x or z \equiv -1 \mod x. Thus, z is a trivial square root of 1 \mod x.

Thus, to prove some number N is not prime, it suffices to find a nontrivial square root of 1 \mod x.

Suppose N is composite and odd (if N is even, then things are easy). Then N-1 is even, so N-1 = 2^t v, where v is odd (we take out as many factors of 2 as possible). We will use Fermat’s test, which checks if a^{N-1} \equiv 1 \mod N for a random a\in \{1,...,N-1\}. First, we compute a^{N-1} \mod N by repeated squares:

a^{v} \mod N
then  a^{2v} \mod N
a^{2^2v} \mod N
…
a^{2^tv} \mod N

If a^{n-1} \not \equiv 1 \mod N, then we know that N is composite by Fermat’s little theorem. Suppose a^{n-1} \equiv 1 \mod N. Then go back to the first point where a^{2^i v} \equiv 1 \mod N. We know that a^{2^{i-1} v} \mod N is a square root of 1\mod N. If this is non-trivial, then we have proved that N is composite.

Fact: At least 3/4 of the choices for a in \{1,...,x-1\} lead to a nontrivial square root in this manner.

This algorithm works for all composite numbers (including Carmichael numbers).

This leads us to a new algorithm that works for any composite number. We run our algorithm as before and find the first i where a^{2^i v}\not\equiv 1 \mod N, but which is a square root of 1\mod N. If it is -1, output “prime”. Else, output “not prime”.