ART

.


In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.

Definition

Fermat's little theorem states that if p is prime and a is coprime to p, then ap−1 − 1 is divisible by p. If a composite integer x is coprime to an integer a > 1 and x divides ax−1 − 1, then x is called a Fermat pseudoprime to base a. In other words, a composite integer is a Fermat pseudoprime to base a if it successfully passes Fermat primality test for the base a.[1]

The smallest base-2 Fermat pseudoprime is 341. It is not a prime, since it equals 11·31, but it satisfies Fermat's little theorem: 2340 ≡ 1 (mod 341) and thus passes Fermat primality test for the base 2.

Pseudoprimes to base 2 are sometimes called Poulet numbers, Sarrus numbers, or Fermatians (sequence A001567 in OEIS).

An integer x that is a Fermat pseudoprime for all values of a that are coprime to x is called a Carmichael number.[1]
Variations

Some sources use variations of the definition, for example to only allow odd numbers to be pseudoprimes.[2]

Every odd number q satisfies \( a^{q-1} \equiv 1 \pmod q \) for a=q-1. This trivial case is excluded in the definition of a Fermat pseudoprime given by Crandall and Pomerance:[3]

A composite number q is a Fermat pseudoprime to a base a, if \( a^{q-1} \equiv 1 \pmod q \) and \( 2 \le a \le q-2. \)

This stronger definition excludes every power of three (9, 27, 81, 243, ...), and many even integers from the base-2 Fermat pseudoprimes.

Properties
Distribution

There are infinitely many pseudoprimes to a given base (in fact, infinitely many Carmichael numbers), but they are rather rare. There are only three pseudo-primes to base 2 below 1000, and below a million there are only 245. Starting at 17·257, the product of consecutive Fermat numbers is a base-2 pseudo-prime.
Factorizations

The factorizations of the 60 Poulet numbers up to 60787, including 13 Carmichael numbers (in bold), are in the below table.

Poulet 1 to 15
341 11 · 31
561 3 · 11 · 17
645 3 · 5 · 43
1105 5 · 13 · 17
1387 19 · 73
1729 7 · 13 · 19
1905 3 · 5 · 127
2047 23 · 89
2465 5 · 17 · 29
2701 37 · 73
2821 7 · 13 · 31
3277 29 · 113
4033 37 · 109
4369 17 · 257
4371 3 · 31 · 47
Poulet 16 to 30
4681 31 · 151
5461 43 · 127
6601 7 · 23 · 41
7957 73 · 109
8321 53 · 157
8481 3 · 11 · 257
8911 7 · 19 · 67
10261 31 · 331
10585 5 · 29 · 73
11305 5 · 7 · 17 · 19
12801 3 · 17 · 251
13741 7 · 13 · 151
13747 59 · 233
13981 11 · 31 · 41
14491 43 · 337
Poulet 31 to 45
15709 23 · 683
15841 7 · 31 · 73
16705 5 · 13 · 257
18705 3 · 5 · 29 · 43
18721 97 · 193
19951 71 · 281
23001 3 · 11 · 17 · 41
23377 97 · 241
25761 3 · 31 · 277
29341 13 · 37 · 61
30121 7 · 13 · 331
30889 17 · 23 · 79
31417 89 · 353
31609 73 · 433
31621 103 · 307
Poulet 46 to 60
33153 3 · 43 · 257
34945 5 · 29 · 241
35333 89 · 397
39865 5 · 7 · 17 · 67
41041 7 · 11 · 13 · 41
41665 5 · 13 · 641
42799 127 · 337
46657 13 · 37 · 97
49141 157 · 313
49981 151 · 331
52633 7 · 73 · 103
55245 3 · 5 · 29 · 127
57421 7 · 13 · 631
60701 101 · 601
60787 89 · 683

A Poulet number all of whose divisors d divide 2d − 2 is called a super-Poulet number. There are infinitely many Poulet numbers which are not super-Poulet Numbers.
Smallest Fermat pseudoprimes

The smallest pseudoprime for each base a ≤ 200 is given in the following table; the colors mark the number of prime factors. Unlike in the definition at the start of the article, pseudoprimes below a are excluded in the table.
a smallest p-p a smallest p-p a smallest p-p a smallest p-p

table.

a smallest p-p a smallest p-p a smallest p-p a smallest p-p
    51 65 = 5 · 13 101 175 = 5² · 7 151 175 = 5² · 7
2 341 = 11 · 31 52 85 = 5 · 17 102 133 = 7 · 19 152 153 = 3² · 17
3 91 = 7 · 13 53 65 = 5 · 13 103 133 = 7 · 19 153 209 = 11 · 19
4 15 = 3 · 5 54 55 = 5 · 11 104 105 = 3 · 5 · 7 154 155 = 5 · 31
5 124 = 2² · 31 55 63 = 3² · 7 105 451 = 11 · 41 155 231 = 3 · 7 · 11
6 35 = 5 · 7 56 57 = 3 · 19 106 133 = 7 · 19 156 217 = 7 · 31
7 25 = 5² 57 65 = 5 · 13 107 133 = 7 · 19 157 186 = 2 · 3 · 31
8 9 = 3² 58 133 = 7 · 19 108 341 = 11 · 31 158 159 = 3 · 53
9 28 = 2² · 7 59 87 = 3 · 29 109 117 = 3² · 13 159 247 = 13 · 19
10 33 = 3 · 11 60 341 = 11 · 31 110 111 = 3 · 37 160 161 = 7 · 23
11 15 = 3 · 5 61 91 = 7 · 13 111 190 = 2 · 5 · 19 161 190=2 · 5 · 19
12 65 = 5 · 13 62 63 = 3² · 7 112 121 = 11² 162 481 = 13 · 37
13 21 = 3 · 7 63 341 = 11 · 31 113 133 = 7 · 19 163 186 = 2 · 3 · 31
14 15 = 3 · 5 64 65 = 5 · 13 114 115 = 5 · 23 164 165 = 3 · 5 · 11
15 341 = 11 · 13 65 112 = 24 · 7 115 133 = 7 · 19 165 172 = 2² · 43
16 51 = 3 · 17 66 91 = 7 · 13 116 117 = 3² · 13 166 301 = 7 · 43
17 45 = 3² · 5 67 85 = 5 · 17 117 145 = 5 · 29 167 231 = 3 · 7 · 11
18 25 = 5² 68 69 = 3 · 23 118 119 = 7 · 17 168 169 = 13²
19 45 = 3² · 5 69 85 = 5 · 17 119 177 = 3 · 59 169 231 = 3 · 7 · 11
20 21 = 3 · 7 70 169 = 13² 120 121 = 11² 170 171 = 3² · 19
21 55 = 5 · 11 71 105 = 3 · 5 · 7 121 133 = 7 · 19 171 215 = 5 · 43
22 69 = 3 · 23 72 85 = 5 · 17 122 123 = 3 · 41 172 247 = 13 · 19
23 33 = 3 · 11 73 111 = 3 · 37 123 217 = 7 · 31 173 205 = 5 · 41
24 25 = 5² 74 75 = 3 · 5² 124 125 = 5³ 174 175 = 5² · 7
25 28 = 2² · 7 75 91 = 7 · 13 125 133 = 7 · 19 175 319 = 11 · 19
26 27 = 3³ 76 77 = 7 · 11 126 247 = 13 · 19 176 177 = 3 · 59
27 65 = 5 · 13 77 247 = 13 · 19 127 153 = 3² · 17 177 196 = 2² · 7²
28 45 = 3² · 5 78 341 = 11 · 31 128 129 = 3 · 43 178 247 = 13 · 19
29 35 = 5 · 7 79 91 = 7 · 13 129 217 = 7 · 31 179 185 = 5 · 37
30 49 = 7² 80 81 = 34 130 217 = 7 · 31 180 217 = 7 · 31
31 49 = 7² 81 85 = 5 · 17 131 143 = 11 · 13 181 195 = 3 · 5 · 13
32 33 = 3 · 11 82 91 = 7 · 13 132 133 = 7 · 19 182 183 = 3 · 61
33 85 = 5 · 17 83 105 = 3 · 5 · 7 133 145 = 5 · 29 183 221 = 13 · 17
34 35 = 5 · 7 84 85 = 5 · 17 134 135 = 3³ · 5 184 185 = 5 · 37
35 51 = 3 · 17 85 129 = 3 · 43 135 221 = 13 · 17 185 217 = 7 · 31
36 91 = 7 · 13 86 87 = 3 · 29 136 265 = 5 · 53 186 187 = 11 · 17
37 45 = 3² · 5 87 91 = 7 · 13 137 148 = 2² · 37 187 217 = 7 · 31
38 39 = 3 · 13 88 91 = 7 · 13 138 259 = 7 · 37 188 189 = 3³ · 7
39 95 = 5 · 19 89 99 = 3² · 11 139 161 = 7 · 23 189 235 = 5 · 47
40 91 = 7 · 13 90 91 = 7 · 13 140 141 = 3 · 47 190 231 = 3 · 7 · 11
41 105 = 3 · 5 · 7 91 115 = 5 · 23 141 355 = 5 · 71 191 217 = 7 · 31
42 205 = 5 · 41 92 93 = 3 · 31 142 143 = 11 · 13 192 217 = 7 · 31
43 77 = 7 · 11 93 301 = 7 · 43 143 213 = 3 · 71 193 276 = 2² · 3 · 23
44 45 = 3² · 5 94 95 = 5 · 19 144 145 = 5 · 29 194 195 = 3 · 5 · 13
45 76 = 2² · 19 95 141 = 3 · 47 145 153 = 3² · 17 195 259 = 7 · 37
46 133 = 7 · 19 96 133 = 7 · 19 146 147 = 3 · 7² 196 205 = 5 · 41
47 65 = 5 · 13 97 105 = 3 · 5 · 7 147 169 = 13² 197 231 = 3 · 7 · 11
48 49 = 7² 98 99 = 3² · 11 148 231 = 3 · 7 · 11 198 247 = 13 · 19
49 66 = 2 · 3 · 11 99 145 = 5 · 29 149 175 = 5² · 7 199 225 = 3² · 5²
50 51 = 3 · 17 100 153 = 3² · 17 150 169 = 13² 200 201 = 3 · 67

Euler–Jacobi pseudoprimes
Main article: Euler–Jacobi pseudoprime

Another approach is to use more refined notions of pseudoprimality, e.g. strong pseudoprimes or Euler–Jacobi pseudoprimes, for which there are no analogues of Carmichael numbers. This leads to probabilistic algorithms such as the Solovay–Strassen primality test and the Miller–Rabin primality test, which produce what are known as industrial-grade primes. Industrial-grade primes are integers for which primality has not been "certified" (i.e. rigorously proven), but have undergone a test such as the Miller–Rabin test which has nonzero, but arbitrarily low, probability of failure.
Applications

The rarity of such pseudoprimes has important practical implications. For example, public-key cryptography algorithms such as RSA require the ability to quickly find large primes. The usual algorithm to generate prime numbers is to generate random odd numbers and test them for primality. However, deterministic primality tests are slow. If the user is willing to tolerate an arbitrarily small chance that the number found is not a prime number but a pseudoprime, it is possible to use the much faster and simpler Fermat primality test.
References

^ a b Desmedt, Yvo (2010). "Encryption Schemes". In Atallah, Mikhail J. & Blanton, Marina. Algorithms and theory of computation handbook: Special topics and techniques. CRC Press. pp. 10–23. ISBN 978-1-58488-820-8.
^ Weisstein, Eric W., "Fermat Pseudoprime" from MathWorld.
^ Richard Crandall, Carl Pomerance (2001). "Theorem 3.4.2". Prime Numbers – A Computational Perspective. Springer-Verlag. p. 132.

External links

W. F. Galway, Database of Base-2 Pseudoprimes up to 10^15 (including Strong Pseudoprimes and Carmichael numbers)

Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License

Hellenica World - Scientific Library