NTIC Strong Pseudoprimes

Section 12.4 Strong Pseudoprimes

Since composite numbers can pass Miller's test too, nomenclature can get frustrating if we don't organize. So we come up with another name.

🔗

Definition 12.4.1.

We call a composite number $n$ that passes Miller's test base $a$ a strong pseudoprime base $a$ .

🔗

The bad news is that strong pseudoprimes exist, as we saw above with

$n=2047\text{.}$ In fact, we can prove a theorem about them analogous to Fact 12.2.6, and which implies it (see Corollary 12.4.3).

🔗

Theorem 12.4.2.

If $n$ is a pseudoprime base $2\text{,}$ then $2^n-1$ is a strong pseudoprime base $2\text{.}$

🔗

Proof.

Let $n$ be composite and odd, but it passes the base two test:

\begin{equation*} 2^{n}\equiv 2\text{ (mod }n)\text{.} \end{equation*}

Since $n$ is odd, we can cancel $2$ in the congruence, and get

\begin{equation*} 2^{n-1}\equiv 1\text{ (mod }n)\text{.} \end{equation*}

Rewrite this as $2^{n-1}-1=nk$ for some integer $k\text{.}$

Since $2^{n-1}-1$ is odd, then so is $k$ necessarily. Now comes some final manipulation to prepare to apply Miller's test to $2^n-1\text{:}$

\begin{equation*} \left(2^{n}-1\right)-1=2^n-2 =2\left(2^{n-1}-1\right)=2nk\text{.} \end{equation*}

Now use the preceding equation as the exponent in Miller's test and a clever reduction:

\begin{equation*} 2^{[(2^n-1)-1]/2}=2^{2nk/2}=2^{nk}=\left(2^n\right)^k\equiv 1^k\equiv 1\text{ (mod }2^n-1)\text{.} \end{equation*}

Since $[(2^n-1)-1]/2=2^{n-1}-1$ is odd, the number passes Miller's test.

All that remains is to show $2^n-1$ is composite if $n$ is composite; this is a fairly straightforward extension of Lemma 12.1.2 (see Exercise 12.7.7).

🔗

Corollary 12.4.3.

If $n$ is a pseudoprime base $a\text{,}$ so is $2^n-1\text{.}$ (This is Fact 12.2.6.)

🔗

Proof.

All we need is that $(\pm 1)^2=1\text{.}$

🔗

Corollary 12.4.4.

There are infinitely many strong pseudoprimes (and hence pseudoprimes) base 2.

🔗

Proof.

Take your favorite pseudoprime, and keep subtracting one from two to the power of the previous (strong) pseudoprime.

🔗

Example 12.4.5.

For instance, we now know that $2^{341}-1$ must fall in that category. If you try the cell below you will see that the (very large) second number is odd, which confirms it.

xxxxxxxxxx
 
n=2^341-1
print(mod(2,n)^((n-1)/2))
print((n-1)/2)

🔗

But there are not any ‘strong Carmichael numbers’! In fact:

🔗

Theorem 12.4.6.

If $n$ is an odd composite positive integer, then $n$ passes Miller's test for at most $(n-1)/4$ bases $a$ between 1 and $n-1\text{.}$

🔗

Although the proof is accessible to us at this point, we will not provide it for the sake of space. It counts numbers of solutions of

$x^\ell-1$ modulo various prime powers and combines them with the Chinese Remainder Theorem to give a good counting argument.

🔗

Needless to say, no one could use the base

$a$ test for enough bases to prove primality for any realistic

$n\text{!}$ But Rabin used this fact to suggest a test for a probable prime with probability of failure less than

$\left(\frac{1}{4}\right)^k$ for any desired

$k\text{.}$

🔗

Algorithm 12.4.7. Miller-Rabin (probabilistic) primality test.

Run Miller's test for $k$ different bases less than $n-1\text{.}$ If a number passes all of them, the probability of failure is less than $\left(\frac{1}{4}\right)^k\text{.}$

🔗

For 100 bases, this is the probability that would come out.

xxxxxxxxxx
 
(1./4)^100

🔗

So if you run the test for 100 bases, you are in pretty decent shape.

🔗

You can also always use some slow test to prove primality. That is what is called a certificate of primality, and although you may not believe it, programs that reliably generate reasonably large (100-200 digits, right now) primes and can verify it are hot items on the virtual shelves of those who care about such things.

🔗

Finally, let's see this in action. Remember that we wanted keys larger than 1024 bits for at least a semblance of security in RSA? Here we go with a start:

xxxxxxxxxx
 
p=next_probable_prime(randrange(2^1024))
q=next_probable_prime(randrange(2^1024))
n=p*q
pretty_print(html(p))
pretty_print(html(q))
pretty_print(html(n))

🔗

The

$p$ and

$q$ we get above are just probable primes. Verifying them could take a little longer! Here, we try it with just one of them.

xxxxxxxxxx
 
p=next_probable_prime(randrange(2^1024))
%time is_prime(p)

🔗

Sage note 12.4.8. Reminder about timing.

Don't forget, you could use %time is_prime(p) to time this operation in a worksheet or Sage command line.