Strong pseudoprime

A strong pseudoprime is an Euler pseudoprime with a special property:

A composite number $\scriptstyle q=d\cdot 2^{s}+1$ (where $\scriptstyle d\$ is odd) is a strong pseudoprime to a base $\scriptstyle a\$ if:

• $a^{d}\equiv 1{\pmod {q}}$

or

• $a^{d\cdot 2^{r}}\equiv -1{\pmod {q}}$ if $0\leq r<s-1$

The first condition is stronger.

Properties

• Every strong pseudoprime is also an Euler pseudoprime.
• Every strong pseudoprime is odd, because every Euler pseudoprime is odd.
• If a strong pseudoprime $\scriptstyle q\$ is pseudoprime to a base $\scriptstyle a\$ in $\scriptstyle a^{d}\equiv 1{\pmod {q}}$, than $\scriptstyle q\$ is pseudoprime to a base $\scriptstyle a'=q-a\$ in $\scriptstyle a'^{d}\equiv -1{\pmod {q}}$ and vice versa.
• There exist Carmichael numbers that are also strong pseudoprimes.

Further reading

• Richard E. Crandall and Carl Pomerance. Prime Numbers: A Computational Perspective. Springer-Verlag, 2001, ISBN 0-387-25282-7
• Paolo Ribenboim. The New Book of Prime Number Records. Springer-Verlag, 1996, ISBN 0-387-94457-5

Links

• Table of strong pseudoprimes between 49 and 1393