Pseudoprime tests

Our next plan is to discuss pseudoprime tests for compositeness. See the book [5], Chapters 3 and 6. Note especially the definition at the top of page 33 and the definition of a Carmichael number: A number $n$ is a Carmichael number if $a^{n-1}\equiv 1\pmod{n}$ for all $a$ relatively prime to $n$.

Recall modular exponentiation using repeated squaring; to compute $a^{b}\bmod{m}$:

1. Set $n=1$.
2. While $b>0$:
   1. if $b$ is odd then $n=n*a\bmod{m}$.
   2. Set $b=[b/2]$.
   3. Set $a=a^2\bmod{m}$
3. Output answer $n$.

A sample computation: $2^{1370}\bmod{1371}$.

n	a	b
1	2	1370
1	4	685
4	16	342
4	256	171
1024	1099	85
1156	1321	42
1156	1129	21
1303	982	10
1303	511	5
898	631	2
898	571	1
4		0

The answer is four, obtained in 12 steps involving numbers modulo 1371.

The number 561 is a Carmichael number because 561=(3)(11)(17). 561-1 is divisible by 2, by 10, and by 16. Consequently, if a isn't divisible by 3, 11, or 17, then $a^{560}$ is congruent to 1 mod 2, mod 11, and mod 17. By the chinese remainder theorem it is then congruent to 1 mod 561.

A number $n$ is a (Fermat) pseudoprime base $a$ if it is composite and $a^{n-1}\equiv 1\pmod{n}$. Psuedoprimes are (relatively) rare. The psuedoprimes base $2$ less than 10,000 are shown below, see [6].

$n$	Factors
341	11 31
561	3 11 17
645	3 5 43
1105	5 13 17
1387	19 73
1729	7 13 19
1905	3 5 127
2047	23 89
2465	5 17 29
2701	37 73
2821	7 13 31
3277	29 113
4033	37 109
4369	17 257
4371	3 31 47
4681	31 151
5461	43 127
6601	7 23 41
7957	73 109
8321	53 157
8481	3 11 257
8911	7 19 67

The strong pseudoprime test is much better at detecting composite numbers than the traditional Fermat pseudoprime test. The test is given on page 77 of Bressoud.

The principle is: if $n$ is prime, $r$ is even, and $x^r\equiv 1\pmod{n}$, then $x^{r/2}\equiv \pm 1\pmod{n}$. If we write $n-1=2^{m}t$, and $n$ is prime, then either $x^{t}\equiv 1$, or the sequence of powers $x^{t},x^{2t},x^{4t},\ldots,x^{2^{m}}t$ must contain first a -1, followed by a 1.

Here is a sample computation of the strong pseudoprime test for 341, using base 2.

• Step 1: $N=341$, so $N-1=340=4*85$. So first we compute $2^{85}\pmod{341}$ using the repeated squaring algorithm:

  1	2	85
  2	4	42
  2	16	21
  32	256	10
  32	64	5
  2	4	2
  2	16	1
  32		0

• We see that $2^{85}\equiv 32\pmod{341}$. This is not $\pm 1$, so we continue squaring:
  
  $$(2^{85})^2\equiv 2^{170}\equiv 1\pmod{341}$$
  
  

• Because we have obtained a $1$ before a $-1$, we see that $341$ is composite.

Note that it is still the case that $2^{340}\equiv 1\pmod{341}$, so $341$ is a Fermat pseudoprime.

To illustrate the power of this method in detecting composites, we have the following facts, confirmed by computer search in [7]:

• The smallest strong pseudoprime base 2 is 2047.
• The smallest number that is a strong pseudoprime base 2 and 3 is 1373653
• The smallest number that is a strong pseudoprime base 2 and 3 and 5 is 25326001
• The smallest number less than $2.5\times 10^{9}$ that is a strong pseudoprime base 2 and 3 and 5 and 7 is 3215031751.

This gives a very quick test for primality for numbers less than 25 billion.

Recall from our discussion above that a Carmichael number is a composite number $N$ such that $a^{N-1}\equiv 1\pmod{N}$ for all $a$ relatively prime to $N$.

Proposition 17   There are no ``strong'' Carmichael numbers; in other words, for all composite $N$, there is at least one $a$ such that $N$ is not a strong pseudoprime base $a$.

We will make repeated use of the following assertion.

Lemma 18   If $(x,n)=1$, $x^{r}\equiv 1\pmod{n}$, and $x^{s}\equiv 1\pmod{n}$, then $x^{m}\equiv 1\pmod{n}$ where $m=(r,s)$.

Proof: Because $(x,n)=1$, we know that $x$ has a multiplicative inverse $y=x^{-1}$ mod $n$. Write $m=ar+bs$ for integers $a,b$. Then $x^{m}\equiv x^{ar+bs}\equiv 1$.

Now we prove the proposition, following [5, Theorem 6.5], though expressing it differently. Also we treat even numbers and prime powers together.

Suppose that $N$ is even and composite. Then $N-1$ is odd, so $(-1)^{N-1}\equiv -1\pmod{N}$. Thus $-1$ is a base for which $N$ is not a pseudoprime.

The following is new and different, and is a much simpler approach than I was using in class.

Suppose that $N$ is odd and composite. Suppose that $N=p_1^{e_1}p_2^{e_2}\cdots p_{k}^{e_{k}}$ is the prime factorization of $N$. Find $x$ such that $x\equiv -1\pmod{p_1^{e_1}}$, but $x\equiv 1\pmod{p_i^{e_i}}$ for $i> 1$. Write $N-1=2^{c}u$, with $u$ odd. Then $x^{2u}\equiv 1\pmod{N}$, but $x^{u}\equiv -1\pmod{p_1^{e_1}}$ and $x^{u}\equiv 1\pmod{p_i^{e_i}}$ for $i> 1$. Therefore $x^{u}\not\equiv -1\pmod{N}$. Thus $x$ is a base such that $N$ is not a strong pseudoprime base $x$.

This is my version of Bressoud's proof, which is much more complicated. Why does he do it this way, and why did I listen to him?

Now suppose that $N$ is an odd prime power, say $N=p^{k}$, with $k>1$. Suppose that $x^{N-1}\equiv 1\pmod{N}$. As always, $x^{\phi(N)}=x^{p^{k-1}(p-1)}\equiv 1\pmod{N}$. Then by the lemma we must have $x^{r}\equiv 1\pmod{N}$ where $r=(p^{k-1}(p-1),N-1)=(p-1,N-1)$ because $p$ does not divide $N-1$. Let $x$ be a primitive root mod $p^{k}$. (See [1, Theorem 2.41]) Since $r<\phi(N)$, we see that $x^{r}\not\equiv 1\pmod{N}$, so we've found an $x$ so that $N$ is not a strong pseudoprime base $x$.

Now suppose that $N$ is odd and has at least two different prime factors $p$ and $q$. Suppose that $p-1=2^{a}s$, $q-1=2^{b}t$, and $N-1=2^{c}u$, with $s$, $t$, and $u$ odd, and with $a\ge b$. Choose $x$ so that

$$x^{(p-1)/2}\equiv 1\pmod{p}$$

and

$$x^{(q-1)/2}\equiv -1 \pmod{q}.$$

This is possible by the Chinese remainder theorem (why?). Now consider the numbers $x^{u}$, $x^{2u}$, $x^{4u}$, and so on; these are the numbers we look at in the strong pseudoprime test. Suppose that $j$ is the smallest number such that $x^{2^{j}u}\equiv 1\pmod{p}$. But also $x^{2^{a-1}s}\equiv 1\pmod{p}$, by our choice of $x$. Then $x^{r}\equiv 1\pmod{p}$, where $r=(2^{a-1}s,2^{j}u)$. Since $j$ is minimal, we must have $j\le a-1$ (why?).

Now let $k$ be the smallest integer so that $x^{2^{k}u}\equiv 1\pmod{q}$. We always have $x^{q-1}\equiv 1\pmod{q}$, so that $x^{m}\equiv 1\pmod{q}$ where $m=(2^{k}u,2^{b}t)$. Now if $k$ were smaller than $b$, it would follow that $x^{(q-1)/2}\equiv 1\pmod{q}$ (why?) but that isn't so. Therefore $b\le k$.

We now know that $j<a\le b\le k$, so that $j<k$.

Now return to the sequence $x^{u},x^{2u},x^{4u},\ldots$. Let $i$ be the smallest power such that $x^{2^{i}u}\equiv 1\pmod{N}$. Then $x^{2^{i}u}\equiv 1\pmod{p}$, so that $i\ge j$. But if $N$ is a pseudoprime base $x$, and $i>j$, then $x^{2^{i-1}u}\equiv 1\pmod{p}$, and in particular it is NOT equivalent to $-1$ mod $p$, hence not $-1$ mod $N$. Thus we must have $i=j$. But then $x^{2^{i}u}\not\equiv 1\pmod{q}$, which is a contradiction. Thus $N$ is not a pseudoprime base $x$, which is what we wanted to show.

Efficiency of psuedoprime testing

Let us consider the time required to perform a pseudoprime test. For simplicity, we will talk about the Fermat test. We know from our discussion of arithmetic that multiplication of two numbers of size $N$ takes time $O((\log N)^{2})$ if we use traditional multiplication, and less time if we use Karatsuba. Although we did not prove this, we will further use the fact that computing quotients and remainders of numbers of size $N$ also requires time $O((\log N)^{2})$.

Carrying out a Fermat pseudoprime test requires us to compute $a^{N-1}\pmod{N}$. The repeated squaring algorithm requires at most one squaring and one multiplication modulo $N$ for each step of the algorithm. These steps need to be done until repeated division of $N-1$ by $2$ yields a number smaller than one. This, in turn, requires $\log_{2}(N)+1$ steps at most. Therefore the number of steps required to do a Fermat test is $O(\log(N)^3)$.

This should be contrasted with the ``Trial Division'' method of determining if a number is prime. In this method, we divide $N$ successively by every (prime) number smaller than $\sqrt{N}$. If we find a factor, then $N$ is composite; if not, then $N$ is prime. The number of steps here is at worst (the number of primes less than $\sqrt{N}$) times (the time for each division), which is at most $O((\sqrt{N}/\log(\sqrt{N}))(\log(N))^{2})$, or $O(\sqrt{N}\log(N))$.

To see the significance of this difference, suppose that we can apply trial division to a 10 digit number $N$ in five seconds (this is how long it takes, roughly, on my current computer using Maple - admittedly we could do a lot better). The time to do trial division, being $O(\sqrt{N}\log(N))$, grows proportionally like $\sqrt{N}\log(N)$ as $N$ gets bigger. For a twenty digit number, the factor $\sqrt{10^{20}}\log(10^{20})/\sqrt{10^{10}}\log(10^{10})$ is $2\times 10^{5}$, or $200,000$. Thus to do a twenty digit number would take a million seconds (5*200000), or something like two weeks. To do a fifty digit number would take $25\times 10^{20}$ seconds. This number is greater than the age of the universe.

By comparison, if a pseudoprime test on a 10 digit number takes 1 second (it really takes much less time) doing a pseudoprime test on a 50 digit number takes about 125 times as long - about two minutes.

This illustrates the difference between algorithms whose running time is polynomial in $\log(N)$, and algorithms whose running time depends on a power of $N$.