5.3 Primality Certificates

We now examine the situation where N is almost certainly prime (having passed the Miller-Rabin test many times with flying colors!). In such a situation, we wish to provide a ``certificate'' that N is a prime. In unison with Knuth, we could ask ``Why?''. After all, it is really so highly improbable that N is not a prime that this is not worth considering. One situation that one can think of is where an ``oracle'' produces keys for us. While we trust the oracle not to ``leak'' a key, we are not so sure that the oracle (in order to save time and money) may be using some quick and dirty method to generate the modulus, which may be weak. Then we would ask the oracle to ``provide proof'' that it has given us a prime number. Another situation is that someone ``pays'' us to factor a number--we would need to certify that the factorisation is complete. The certificate should be very ``easy'' to check.

From this point of view, it is no use saying ``it passed the Miller-Rabin test for me why don't you try it''. In fact (somewhat more surprisingly perhaps) it is no use saying ``I have tried all divisors upto $\sqrt{N}$''. Thus even if you are ``convinced'' that you have a prime; how can you convince someone else without asking the other person to perform an identical computation!

Again group theoretic methods are very useful. In the situation of the group scheme as above, suppose we find an non-trivial element g in G(N) whose order m is larger than the order of G(p) for any prime less than $\sqrt{N}$ (recall that we have a good estimate of the order of G(p)). Let d < m, then there is some ``co-ordinate'' of g^d which differs from the same coordinate for the identity element of G; this is what one means by saying that g^d is not the identity element of G(N). Thus, this difference must be a unit of $\mathbb {Z}$/N$\mathbb {Z}$ (since we are morally certain that N is a prime!). In particular, for every prime factor q of m we provide a co-ordinate of g^m/q and its inverse x_q in $\mathbb {Z}$/N$\mathbb {Z}$. This is a certificate of primality.

The person receiving this certificate would argue as follows. Suppose p is the a prime factor of N that it is less than $\sqrt{N}$. Then some power g^d for d = m/q must become trivial in G(p) (since a this group cannot have an element of order large than it!). But the given co-ordinate of g^d differs from the same co-ordinate of identity by a unit in $\mathbb {Z}$/N$\mathbb {Z}$ (we have given a proof of this by providing x_q). Thus this co-ordinate cannot be zero. Hence there are not such prime prime factors--hence N is prime.

Thus a primality ``certificate'' would be the tuple (G, g, m,{x_q}_q|). Of course, the correct-ness of this certificate depends on the primality of various q's, so we would need a certificate for those as well!

To make this explicit, suppose we find an element a in $\mathbb {Z}$/N$\mathbb {Z}$ so that a^m = 1 but a^m/q $\neq$ 1 and q $\geq$ $\sqrt{N}$; for some integer m and a prime factor q. Then, N is prime; for if p is a factor of N, then the gcd(a^m/q - 1, p) divides gcd(a^m/q - 1, N) and thus a^m/q $\neq$ 1 in $\mathbb {Z}$/p$\mathbb {Z}$. But that means q divides p - 1. On the other hand, if N is not prime, N msut have a prime factor smaller than $\sqrt{N}$.

This can be carried some steps further.

Proposition 12   Suppose that N - 1 = f ^. r, where f is completely factored into primes p_i, r has all its factors greater than B and gcd(f, r) = 1. Moreover, suppose that f ^. B $\geq$ $\sqrt{N}$. Now suppose that we find a_i so that its order is a multiple of the exact power of p_i that divides N - 1. Moreover, we have b so that b^{N - 1} = 1 and gcd(b^f - 1, N) = 1, then N is a prime. Conversely, given such a factorisation of N - 1, there are a's as required.

Proof. Let d be a prime divisor of N. Then, the order of a_i in $\mathbb {Z}$/d$\mathbb {Z}$ is divisible by exactly the same power of p_i that divides N - 1 ( gcd(a^{p_ie_i - 1} - 1, N) = 1 implies the same with N replaced by d). This means that f divides d - 1. Now, let e be the order of a₀ in the units of $\mathbb {Z}$/d$\mathbb {Z}$. Then e divides d - 1 and N - 1 = f ^. r and does not divide f = (N - 1)/r. Thus gcd(e, r) > 1. In particular, gcd(e, u) > B (since every prime factor of r has this property). Thus gcd(e, u) ^. f divides d - 1, so that d becomes larger than $\sqrt{N}$. But this cannot be true for every prime factor of N unless N is prime. (Exercise: find a more group-theoretic proof). $\qedsymbol$

This can be used to provide a primality certificate as follows. We use trial division upto a bound B₀ to obtain a factorisation N - 1 = fr. If fB₀ $\geq$ $\sqrt{N}$, then we take B = B₀ and we are done. Otherwise we check for the primality of r (say using the Miller-Rabin test). If it is prime then we are done again (we have a complete factorisation of F = N - 1). Otherwise we increase the bound B and continue. The main problem (as usual) is with N - 1 having a few large prime factors; in this case we would have to proceed to a bound B like $\sqrt{N}$. As it turns out, once we have a factorisation of N - 1, then we can proceed more surely, testing (in succession a^{N - 1/q} for each prime factor q of N - 1; if we fail for a given a we can continue with the next a). One can show that the latter will succeed quite quickly.

Lemma 13   Let q be a prime so that q^f exactly divides the order of a cyclic group G. The collection of elements, whose order is exactly divisible by q^e for e < f has cardinality at most 1/q times the cardinality of G.

Thus the probability that a given element a will fail for all q is the product of (1 - 1/q) which is very small. The proof of the lemma is easy and left as an exercise.

As we can see the main stumbling block for this method is that we need to factor N - 1 since the units in $\mathbb {Z}$/N$\mathbb {Z}$ is the only group available with us (so far) to apply this method to. Later we will expand the class of groups (and so we can try to pick a group with order easily factorisable) and it will be easier to find such primality certificates.