info prev up next book cdrom email home

Strong Pseudoprime

A strong pseudoprime to a base $a$ is an Odd Composite Number $n$ with $n-1=d\cdot 2^s$ (for $d$ Odd) for which either

\begin{displaymath}
a^d\equiv 1\ \left({{\rm mod\ } {n}}\right)
\end{displaymath} (1)

or
\begin{displaymath}
a^{d\cdot 2^r}\equiv -1\ \left({{\rm mod\ } {n}}\right)
\end{displaymath} (2)

for some $r\in[0,s)$.


The definition is motivated by the fact that a Fermat Pseudoprime $n$ to the base $b$ satisfies

\begin{displaymath}
b^{n-1}-1\equiv 0\ \left({{\rm mod\ } {n}}\right).
\end{displaymath} (3)

But since $n$ is Odd, it can be written $n=2m+1$, and
\begin{displaymath}
b^{2m}-1 =(b^m-1)(b^m+1) \equiv 0 {\rm\ (mod\ } n).
\end{displaymath} (4)

If $n$ is Prime, it must Divide at least one of the Factors, but can't Divide both because it would then Divide their difference
\begin{displaymath}
(b^m+1)-(b^m-1)=2.
\end{displaymath} (5)

Therefore,
\begin{displaymath}
b^m\equiv \pm 1\ \left({{\rm mod\ } {n}}\right),
\end{displaymath} (6)

so write $n=2^at+1$ to obtain
\begin{displaymath}
b^{n-1}-1=(b^t-1)(b^t+1)(b^{2t}+1)\cdots(b^{2^{a-1}t}+1).
\end{displaymath} (7)


If $n$ Divides exactly one of these Factors but is Composite, it is a strong pseudoprime. A Composite number is a strong pseudoprime to at most 1/4 of all bases less than itself (Monier 1980, Rabin 1980). The strong pseudoprimes provide the basis for Miller's Primality Test and Rabin-Miller Strong Pseudoprime Test.


A strong pseudoprime to the base $a$ is also an Euler Pseudoprime to the base $a$ (Pomerance et al. 1980). The strong pseudoprimes include some Euler Pseudoprimes, Fermat Pseudoprimes, and Carmichael Numbers.


There are 4842 strong psp(2) less than $2.5\times 10^{10}$, where a psp(2) is also known as a Poulet Number. The strong $k$-pseudoprime test for $k=2$, 3, 5 correctly identifies all Primes below $2.5\times 10^{10}$ with only 13 exceptions, and if 7 is added, then the only exception less than $2.5\times 10^{10}$ is 315031751. Jaeschke (1993) showed that there are only 101 strong pseudoprimes for the bases 2, 3, and 5 less than $10^{12}$, nine if 7 is added, and none if 11 is added. Also, the bases 2, 13, 23, and 1662803 have no exceptions up to $10^{12}$.


If $n$ is Composite, then there is a base for which $n$ is not a strong pseudoprime. There are therefore no ``strong Carmichael Numbers.'' Let $\psi_k$ denote the smallest strong pseudoprime to all of the first $k$ Primes taken as bases (i.e, the smallest Odd Number for which the Rabin-Miller Strong Pseudoprime Test on bases less than or equal to $k$ fails). Jaeschke (1993) computed $\psi_k$ from $k=5$ to 8 and gave upper bounds for $k=9$ to 11.

$\displaystyle \psi_1$ $\textstyle =$ $\displaystyle 2047$  
$\displaystyle \psi_2$ $\textstyle =$ $\displaystyle 1373653$  
$\displaystyle \psi_3$ $\textstyle =$ $\displaystyle 25326001$  
$\displaystyle \psi_4$ $\textstyle =$ $\displaystyle 3215031751$  
$\displaystyle \psi_5$ $\textstyle =$ $\displaystyle 2152302898747$  
$\displaystyle \psi_6$ $\textstyle =$ $\displaystyle 3474749660383$  
$\displaystyle \psi_7$ $\textstyle =$ $\displaystyle 341550071728321$  
$\displaystyle \psi_8$ $\textstyle =$ $\displaystyle 341550071728321$  
$\displaystyle \psi_9$ $\textstyle \leq$ $\displaystyle 41234316135705689041$  
$\displaystyle \psi_{10}$ $\textstyle \leq$ $\displaystyle 1553360566073143205541002401$  
$\displaystyle \psi_{11}$ $\textstyle \leq$ $\displaystyle 56897193526942024370326972321$  

(Sloane's A014233). A seven-step test utilizing these results (Riesel 1994) allows all numbers less than $3.4\times 10^{14}$ to be tested.


Pomerance et al. (1980) have proposed a test based on a combination of Strong Pseudoprimes and Lucas Pseudoprimes. They offer a $620 reward for discovery of a Composite Number which passes their test (Guy 1994, p. 28).

See also Carmichael Number, Miller's Primality Test, Poulet Number, Rabin-Miller Strong Pseudoprime Test, Rotkiewicz Theorem, Strong Elliptic Pseudoprime, Strong Lucas Pseudoprime


References

Baillie, R. and Wagstaff, S. ``Lucas Pseudoprimes.'' Math. Comput. 35, 1391-1417, 1980.

Guy, R. K. ``Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes.'' §A12 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.

Jaeschke, G. ``On Strong Pseudoprimes to Several Bases.'' Math. Comput. 61, 915-926, 1993.

Monier, L. ``Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms.'' Theor. Comput. Sci. 12, 97-108, 1980.

Pomerance, C.; Selfridge, J. L.; and Wagstaff, S. S. Jr. ``The Pseudoprimes to $25\cdot 10^9$.'' Math. Comput. 35, 1003-1026, 1980. Available electronically from ftp://sable.ox.ac.uk/pub/math/primes/ps2.Z.

Rabin, M. O. ``Probabilistic Algorithm for Testing Primality.'' J. Number Th. 12, 128-138, 1980.

Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Basel: Birkhäuser, p. 92, 1994.

Sloane, N. J. A. Sequence A014233 in ``The On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-26