4.4 Compositeness Tests

We now look at tests that will try to show that a number is composite. In other words, the test either shows that the number is composite or exits (apparently) without giving any information.

If p is a prime number, then all numbers between 1 and p - 1 give units in $\mathbb {Z}$/p$\mathbb {Z}$. In fact, $\mathbb {Z}$/p$\mathbb {Z}$ is a field and we have the elementary result

Lemma 6   The group of units in a finite field is a cyclic group.

Proof. By Legendre's theorem we see that the order of any element divides the order of the group. On the other hand, if x has order dividing d then it is a solution of T^d - 1; the latter has at most d solutions since we are in a field. Thus, the exponent of the group of units (i. e. the least common multiple of the orders) must be equal to the order of the group. Now, given elements x and y of orders m and n in an abelian group it is easy to construct an element of the form x^ay^b which has order equal to the least common multiple of m and n. Thus we have a unit of order equal to the order of the group of units; in words the group is cyclic. $\qedsymbol$

In particular, by Legendre's theorem we see that a^{p - 1} = 1 in $\mathbb {Z}$/p$\mathbb {Z}$ for any non-zero element a. Thus if we wish to check whether a number N is composite we can try to find a so that a^{N - 1} $\neq$ 1 in $\mathbb {Z}$/N$\mathbb {Z}$. This is already a good check to see that N does not have square factors.

Lemma 7   When N is an odd number that has square factors, let us define the set of ``bad'' elements S

S = {a $$\in$$ $$\mathbb {Z}$$/N$$\mathbb {Z}$$| a^{N - 1} = 1}

Then, the cardinality of S is at most 2N/9. If N has no prime factors smaller than p this can be improved to (p - 1)N/p².

The proof depends on the following very important result

Proposition 8   The group of units in $\mathbb {Z}$/p^e$\mathbb {Z}$ is cyclic for any odd prime number p and any e $\geq$ 1.

We will defer the proof of this proposition to the next subsection.

Proof. (of the lemma) Since N is odd and has square factors there is an odd prime p and an e $\geq$ 2 so that p^e is the exact power that divides N. Any element a $\in$ S gives an element b in $\mathbb {Z}$/p^e$\mathbb {Z}$ so that b^{N - 1} = 1. Since the latter group is cyclic of order p^e - p^{e - 1} it follows that the number of possible values of b is gcd(N - 1, p^e - p^{e - 1}) (exercise!). Since p divides N, this GCD is equal to gcd(N - 1, p - 1), which is not more than p - 1. The fraction of such b's is thus at most (p - 1)/p² (since e $\geq$ 2). By the Chinese remainder theorem, the set S is the same fraction of elements of $\mathbb {Z}$/N$\mathbb {Z}$. $\qedsymbol$

While this result is useful to know, one can write numbers (which are called Carmichael numbers) such as N = 561 = 3×11×17, with the property that the order of every unit in $\mathbb {Z}$/N$\mathbb {Z}$ divides N - 1. The necessary improvement on the test was suggested by Miller and Rabin.

We write N = 1 + q2^k with q odd. Now, when N is a prime, $\mathbb {Z}$/N$\mathbb {Z}$ is a field. Thus, the only element other than 1 whose square is 1 is -1. It follows that for any a $\neq$ 0, either a^q = 1 or there is some e between 0 and k - 1 so that a^q2e = - 1. Now we have seen that computing powers in $\mathbb {Z}$/N$\mathbb {Z}$ is easily done. Thus we can pick any a and form the powers a^q2e for 0 $\leq$ e < k in succession. If a^q $\neq$ 1 and none of these powers is -1, then N must be composite. On the other hand, it could happen that for all the a's we pick either a^q = 1 or some a^q2e = - 1. In this case we appear to have obtained no information. However, we have

Lemma 9   Let N be a composite number of the form 1 + q2^k. Let us define the set of ``bad'' elements

T = {a $$\in$$ $$\mathbb {Z}$$/N$$\mathbb {Z}$$| a^q = 1 or a^q2e = - 1 for some e with 0 $\leq$ e < k }

Then, the cardinality of T is less than N/4.

Proof. Let us write the prime factorisation N = p₁^{e₁ ...} p_r^e_r. Now, if a is in T, then clearly a^q2k = 1, so a is also in the set S defined earlier. Since 2N/9 < N/4 (!) we may as well assume that e_i = 1 for all i. In other words, we assume that N is a product of distinct prime factors. Now, we write p_i = 1 + q_i2^k_i with q_i odd; for later use we note that k is not less than the minimum of the k_i's. We further decompose T into the set T_-1 = {a| a^q = 1} and the sets (for 0 $\leq$ e < k)

T_e = {a| a^q2e = - 1}

Then, elements of T_-1 reduce to units in $\mathbb {Z}$/p_i$\mathbb {Z}$ which have order dividing q. This is a subgroup of order gcd(q, p_i - 1) = gcd(q, q_i). Thus, by the Chinese remainder theorem

#T_-1 = gcd(q, q₁) ^... gcd(q, q_r)

The elements of T_e, can be characterised as elements, whose q-th power has order exactly 2^{e + 1}. These q-th powers then have order exactly 2^{e + 1} when reduced modulo p_i. In particular, this means that e < k_i for every i; the other T_e's are empty. There are exactly gcd(q, q_i)2^{e + 1} elements in $\mathbb {Z}$/p_i$\mathbb {Z}$ with order dividing q2^{e + 1} and among these a subgroup of index 2 has elements of order dividing q2^e (a subgroup of a cyclic group is cyclic). Thus, by Chinese remainder theorem we obtain

#T_e = gcd(q, q₁) ^... gcd(q, q_r) ^. 2^re

Thus we see that the cardinality of T is

gcd(q, q₁) ^... gcd(q, q_r)$$\left(\vphantom{ 1 + \sum_{i=0}^{l-1} 2^{re} }\right.$$1 + $$\sum_{i=0}^{l-1}$$2^re$$\left.\vphantom{ 1 + \sum_{i=0}^{l-1} 2^{re} }\right)$$ = gcd(q, q₁) ^... gcd(q, q_r)$$\left(\vphantom{ \frac{2^{rl}+2^r-2}{2^r-1} }\right.$$$${\frac{2^{rl}+2^r-2}{2^r-1}}$$$$\left.\vphantom{ \frac{2^{rl}+2^r-2}{2^r-1} }\right)$$

where l is the minimum of the k_i's. Now, the Chinese remainder theorem shows that the number of units in $\mathbb {Z}$/N$\mathbb {Z}$ is precisely q₁ ^... q_r ^. 2^{$\sum_{i}$k_i}; this is at least one less than N. Thus the proportion of elements in T is strictly smaller than

$${\frac{\gcd(q,q_1)\cdots\gcd(q,q_r)}{q_1\cdots q_r}}$$ ^. $${\frac{2^{rl}+2^r-2}{(2^r-1)\cdot 2^{k_1+\cdots+k_r}}}$$

The first term is no more than 1, while the second is no more than 1/2^{r - 1} (note that l $\geq$ 1). Thus, we obtain the result unless r = 2. Moreover, if k₂ > k₁ (or vice versa) then we see that the second term is no more than 1/2^r so we have the result in this case as well. Thus we may assume that k₁ = k₂ = l. Now, if gcd(q, q₁) < q₁ then (since these are odd numbers and one divides the other) gcd(q, q₁) $\leq$ 3q₁. This implies that the above expression is no more than 1/6. Thus, we may further assume that gcd(q, q₁) = q₁. By expanding the identity (1 + q2^k) = (1 + q₁2^l)(1 + q₂2^l) we see that gcd(q, q₁) = gcd(q, q₂). Since the primes p₁ and p₂ are distinct q₁ $\neq$ q₂; thus q₁ = gcd(q, q₁) $\leq$ 3q₁ as above. Now we again obtain that the above expression is no more than 1/6. This completes the argument. $\qedsymbol$

What the above reasoning amounts to is that if we choose uniformly among all possible a's in $\mathbb {Z}$/N$\mathbb {Z}$, there is a chance of less than 1/4 that we will pick an a which gives ``no information'' as the output of our test even though N is composite. This is not ``no information'' at all! If we repeat this test n times there is a chance of less than (1/4)ⁿ that N is composite and we did not detect it. It seems more than reasonable to call an N that satisfies such a test a strong pseudo-prime. When we specify the a₁, a₂, ..., a_n, we say that N is a strong pseudo-prime with bases a₁, a₂, ..., a_n.

While have not actually proved that N is a prime in such a case (unlike trial division) there appears to be good enough reason to treat it like a prime. In later sections we will look at primality tests and primality certificates. It is clear that we should not even attempt those unless we have already put our N through the Miller-Rabin grinder and it has come out successful!