Pseudoprime

A pseudoprime is a probable prime (an integer that shares a property common to all prime numbers) that is not actually prime. Pseudoprimes are classified according to which property of primes they satisfy.

Some sources use the term pseudoprime to describe all probable primes, both composite numbers and actual primes.

Pseudoprimes are of primary importance in public-key cryptography, which makes use of the difficulty of factoring large numbers into their prime factors. Carl Pomerance estimated in 1988 that it would cost $10 million to factor a number with 144 digits, and $100 billion to factor a 200-digit number (the cost today is dramatically lower but still prohibitively high).^[1]^[2] But finding two large prime numbers as needed for this use is also expensive, so various probabilistic primality tests are used, some of which in rare cases inappropriately deliver composite numbers instead of primes. On the other hand, deterministic primality tests, such as the AKS primality test, do not give false positives; because of this, there are no pseudoprimes with respect to them.

Fermat pseudoprimes[edit]

Fermat's little theorem states that if $p$ is prime and $a$ is coprime to $p$ , then $a p -1 - 1$ is divisible by $p$ . For an integer $a > 1$ , if a composite integer $x$ divides $a x -1 - 1$ , then $x$ is called a Fermat pseudoprime to base $a$ . It follows that if $x$ is a Fermat pseudoprime to base $a$ , then $x$ is coprime to $a$ . Some sources use variations of this definition, for example to allow only odd numbers to be pseudoprimes.^[3]

An integer $x$ that is a Fermat pseudoprime to all values of $a$ that are coprime to $x$ is called a Carmichael number.

Classes[edit]

References[edit]

^ Clawson, Calvin C. (1996). Mathematical Mysteries: The Beauty and Magic of Numbers. Cambridge: Perseus. p. 195. ISBN 0-7382-0259-2.
^ Cipra, Barry Arthur (December 23, 1988). "PCs Factor a 'Most Wanted' Number". Science. 242 (4886): 1634–1635. Bibcode:1988Sci...242.1634C. doi:10.1126/science.242.4886.1634. PMID 17730568.
^ Weisstein, Eric W. "Fermat Pseudoprime". MathWorld.

[1] Clawson, Calvin C. (1996). Mathematical Mysteries: The Beauty and Magic of Numbers. Cambridge: Perseus. p. 195. ISBN 0-7382-0259-2.

[2] Cipra, Barry Arthur (December 23, 1988). "PCs Factor a 'Most Wanted' Number". Science. 242 (4886): 1634–1635. Bibcode:1988Sci...242.1634C. doi:10.1126/science.242.4886.1634. PMID 17730568.

[3] Weisstein, Eric W. "Fermat Pseudoprime". MathWorld.

[1]

[2]

[3]

v t e Prime number classes
By formula	Fermat ( $2 2 n + 1$ ) Mersenne ( $2 p - 1$ ) Double Mersenne ( $2 2 p -1 - 1$ ) Wagstaff $(2 p + 1)/3$ Proth ( $k \cdot2 n + 1$ ) Factorial ( $n! \pm 1$ ) Primorial ( $p n # \pm 1$ ) Euclid ( $p n # + 1$ ) Pythagorean ( $4 n + 1$ ) Pierpont ( $2 m \cdot3 n + 1$ ) Quartan ( $x 4 + y 4$ ) Solinas ( $2 m \pm 2 n \pm 1$ ) Cullen ( $n \cdot2 n + 1$ ) Woodall ( $n \cdot2 n - 1$ ) Cuban ( $x 3 - y 3)/(x - y$ ) Leyland ( $x y + y x$ ) Thabit ( $3\cdot2 n - 1$ ) Williams ( $(b -1)\cdot b n - 1$ ) Mills ( $⌊ A 3 n ⌋$ )
By integer sequence	Fibonacci Lucas Pell Newman–Shanks–Williams Perrin
By property	Wieferich (pair) Wall–Sun–Sun Wolstenholme Wilson Lucky Fortunate Ramanujan Pillai Regular Strong Stern Supersingular (elliptic curve) Supersingular (moonshine theory) Good Super Higgs Highly cototient Unique
Base-dependent	Palindromic Emirp Repunit $(10 n - 1)/9$ Permutable Circular Truncatable Minimal Delicate Primeval Full reptend Unique Happy Self Smarandache–Wellin Strobogrammatic Dihedral Tetradic
Patterns	Twin ( $p, p + 2$ ) Bi-twin chain ( $n \pm 1, 2 n \pm 1, 4 n \pm 1, \dots$ ) Triplet ( $p, p + 2 or p + 4, p + 6$ ) Quadruplet ( $p, p + 2, p + 6, p + 8$ ) k-tuple Cousin ( $p, p + 4$ ) Sexy ( $p, p + 6$ ) Chen Sophie Germain/Safe ( $p, 2 p + 1$ ) Cunningham ( $p, 2 p \pm 1, 4 p \pm 3, 8 p \pm 7, ...$ ) Arithmetic progression ( $p + a\cdotn, n = 0, 1, 2, 3, ...$ ) Balanced ( $consecutive p - n, p, p + n$ )
By size	Mega (1,000,000+ digits) Largest known list
Complex numbers	Eisenstein prime Gaussian prime
Composite numbers	Pseudoprime Catalan Elliptic Euler Euler–Jacobi Fermat Frobenius Lucas Perrin Somer–Lucas Strong Carmichael number Almost prime Semiprime Sphenic number Interprime Pernicious
Related topics	Probable prime Industrial-grade prime Illegal prime Formula for primes Prime gap
First 60 primes	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
List of prime numbers