Strong pseudoprime

An odd natural number is called a strong pseudoprime number if it is a composite number that behaves like a prime number with respect to a base that is relatively prime to it : let be (with odd). If one of the congruences ${\displaystyle n}$ ${\displaystyle a}$
${\displaystyle n=d\cdot 2^{s}+1}$ ${\displaystyle d}$

• ${\displaystyle a^{d}\equiv 1\mod n}$
• ${\displaystyle a^{d\cdot 2^{r}}\equiv -1\mod n\quad }$for one with ${\displaystyle r}$ ${\displaystyle 0\leqq r<s}$

is fulfilled, then the number is called strong pseudoprime for the base . ${\displaystyle n}$ ${\displaystyle a}$

A strong pseudoprime is always also a pseudoprime in relation to a consequence (explained below) from Fermat's Little Theorem.

Derivation

According to Fermat's little theorem , for every prime number and for every relatively prime number : ${\displaystyle p}$ ${\displaystyle a}$

${\displaystyle p\mid a^{p-1}-1}$

(in words: divides the power of minus 1). Compound numbers that also have this property with respect to a coprime basis are called Fermat's pseudoprimes to the basis . Due to ${\displaystyle p}$ ${\displaystyle (p-1)}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle a}$

${\displaystyle a^{p-1}-1=(a^{\frac {p-1}{2}}+1)\cdot (a^{\frac {p-1}{2}}-1)}$

For every (odd) prime number , one of the two factors on the right must be divisible by (if a product is divisible by a prime number, one of the factors must be divisible by it). This provides a more stringent condition and leads to the concept of Euler's pseudoprimes . The second factor can be broken down further if is an even number. In this case you get: ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle {\tfrac {p-1}{2}}}$

${\displaystyle a^{p-1}-1=(a^{\frac {p-1}{2}}+1)\cdot (a^{\frac {p-1}{4}}+1)\cdot (a^{\frac {p-1}{4}}-1)}$

If now applies (with odd), the procedure can be repeated a total of times and the statement is made that one of the factors must divide. In congruence notation this is the condition mentioned at the beginning of the article (it is also called strong Fermat congruence ). A strong pseudoprime is therefore a pseudoprime in relation to the strong Fermat congruence. ${\displaystyle n=d\cdot 2^{s}+1}$ ${\displaystyle d}$ ${\displaystyle s}$ ${\displaystyle p}$ ${\displaystyle s+1}$

Examples

For the Carmichael number 561 (a Fermat pseudoprime number with respect to all coprime bases) the following applies:

${\displaystyle 560=2^{4}\cdot 35}$

and one finds the decomposition

${\displaystyle a^{560}-1=(a^{280}+1)\cdot (a^{140}+1)\cdot (a^{70}+1)\cdot (a^{35}+1)\cdot (a^{35}-1)}$

We choose 2. If 561 were a prime number, then it would have to share one of the factors on the right. Since the remainders of modulo 561 are equal to 263, 166, 67 and 1, 561 does not divide any of the factors and so the number is not prime. ${\displaystyle 2^{k}}$ ${\displaystyle k=35,70,140,280}$

This is the procedure of the Miller-Selfridge-Rabin primality test . Since every number is less than strong pseudoprime for at most a quarter of the bases , there are no absolute strong pseudoprimes (in contrast to this, there are these with the Euler and Fermat pseudoprimes - the latter are the aforementioned Carmichael numbers). ${\displaystyle n}$ ${\displaystyle n}$

There are infinitely many strong pseudoprimes for every basis. For the first bases you can read the smallest strong pseudoprime numbers (which are at least less than or equal to 10,000) in the following table:

b	strong pseudoprimes to base b	OEIS episode
2	2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, ...	(Follow A001262 in OEIS )
3	121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, ...	(Follow A020229 in OEIS )
4th	341, 1387, 2047, 3277, 4033, 4371, 4681, 5461, 8321, 8911, 10261, ...	(Follow A020230 in OEIS )
5	781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, ...	(Follow A020231 in OEIS )
6th	217, 481, 1111, 1261, 2701, 3589, 5713, 6533, 11041, ...	(Follow A020232 in OEIS )
7th	25, 325, 703, 2101, 2353, 4525, 11041, ...	(Follow A020233 in OEIS )
8th	9, 65, 481, 511, 1417, 2047, 2501, 3277, 3641, 4033, 4097, 4681, 8321, 11041, ...	(Follow A020234 in OEIS )
9	91, 121, 671, 703, 1541, 1729, 1891, 2821, 3281, 3367, 3751, 5551, 7381, 8401, 8911, 10585, ...	(Follow A020235 in OEIS )
10	9, 91, 1729, 4187, 6533, 8149, 8401, 10001, 11111, ...	(Follow A020236 in OEIS )
11	133, 793, 2047, 4577, 5041, 12403, ...	(Follow A020237 in OEIS )
...	...	...
100	9, 33, 91, 99, 259, 451, 481, 703, 1729, 2821, 2981, 3367, 4187, 5461, 6533, 6541, 6601, 7107, 7471, 8149, 8401, 8911, 10001, 11111, ...	(Follow A020326 in OEIS )

The smallest number that occurs in all three sequences on bases 2, 3 and 5 is 25,326,001 = 2251 · 11251. For a prime number test for smaller numbers, the test on bases 2, 3 and 5 is sufficient.

The smallest number that occurs in all nine sequences with bases 2, 3, 5, 7, 11, 13, 17, 19, and 23 is 3,825,123,056,546,413,051 = 149491 · 747451 · 34233211.

literature

• Peter Giblin: Primes and programming. An introduction to number theory with computing. Cambridge University Press, Cambridge et al. 1993, ISBN 0-521-40182-8 , online and the pseudo- prime literature.

Web links

• Eric W. Weisstein : StrongPseudoprime . In: MathWorld (English).

Individual evidence

1. ↑ See article Computational Number Theory by Carl Pomerance in Princeton companion to mathematics (quoted in full in the article Pseudoprime ).
2. ↑ See Giblin, p. 109.
3. ↑ Jiang Yupeng : Strong pseudoprimes to the first 9 prime bases. Cornell University Library, June 30, 2012, accessed August 13, 2016 .