Pseudoprime

A pseudoprime is a probable prime (an integer which shares a property common to all prime numbers) which is not actually prime. Pseudoprimes can be classified according to which property they satisfy. The most important class of pseudoprimes come from Fermat's little theorem and hence are called Fermat pseudoprimes. This theorem states that if p is prime and a is coprime to p, then ap-1 - 1 is divisible by p. If a number x is not prime, a is coprime to x and x divides ax-1 - 1, then x is called a pseudoprime to base a. A number x that is a pseudoprime for all values of a that are coprime to x is called a Carmichael number. The smallest Fermat pseudoprime for the base 2 is 341. It is not a prime, since it equals 11 · 31, nevertheless it satisfies Fermats little theorem; 2341=2 (mod 341). 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 a very small chance that the number found is not a prime number but a pseudoprime, then much faster and simpler tests are possible. Probabilistic algorithms such as the Fermat primality test, the Solovay-Strassen primality test, and the Miller-Rabin primality test are refinements of this idea. There are infinitely many pseudoprimes (in fact infinitely many Carmichael numbers), but they are rather rare. There are only 3 pseudo-primes to base 2 below 1000, and below a million there are only 245. Pseudoprimes to base 2 are called Poulet numbers or sometimes Sarrus numbers or Fermatians . The Poulet numbers and Carmichael numbers (in bold) up to 41041 are:
||n || ||n || ||n || ||n ||
341 = 11 · 31 11 2821 = 7 · 13 · 31 21 8481 = 3 · 11 · 257 31 15709 = 23 · 683 41 30121 = 7 · 13 · 331
561 = 3 · 11 · 17 12 3277 = 29 · 112 22 8911 = 7 · 19 · 67 32 15841 = 7 · 31 · 73 42 30889 = 17 · 23 · 79
645 = 3 · 5 · 43 13 4033 = 37 · 109 23 10261 = 31 · 331 33 16705 = 5 · 13 · 257 43 31417 = 89 · 353
1105 = 5 · 13 · 17 14 4369 = 17 · 257 24 10585 = 5 · 29 · 73 34 18705 = 3 · 5 · 29 · 43 44 31609 = 73 · 433
1387 = 19 · 73 15 4371 = 3 · 31 · 47 25 11305 = 5 · 7 · 17 · 19 35 18721 = 97 · 193 45 31621 = 103 · 307
1729 = 7 · 13 · 19 16 4681 = 31 · 151 26 12801 = 3 · 17 · 251 36 19951 = 71 · 281 46 33153 = 3 · 43 · 257
1905 = 3 · 5 · 127 17 5461 = 43 · 127 27 13741 = 7 · 13 · 151 37 23001 = 3 · 11 · 17 · 41 47 34945 = 5 · 29 · 241
2047 = 23 · 89 18 6601 = 7 · 23 · 41 28 13747 = 59 · 233 38 23377 = 97 · 241 48 35333 = 89 · 397
2465 = 5 · 17 · 29 19 7957 = 73 · 109 29 13981 = 11 · 31 · 41 39 25761 = 3 · 31 · 277 49 39865 = 5 · 7 · 17 · 67
0 2701 = 37 · 73 20 8321 = 53 · 157 30 14491 = 43 · 337 40 29341 = 13 · 37 · 61 50 41041 = 7 · 11 · 13 · 41
A Poulet number all of whose divisors d divide 2d - 2 is called super-Poulet number. There are an infinitely many Poulet numbers which are not super-Poulet Numbers. The first smallest pseudoprimes for bases a ≤ 200 are given in the following table; the colors mark the number of prime factors.
a smallest p-p a smallest p-p a smallest p-p a smallest p-p
    51 65 = 5 · 13 bgcolor="#FFEBAD" | 101 bgcolor="#FFEBAD" | 175 = 52 · 7 bgcolor="#FFEBAD" | 151 bgcolor="#FFEBAD" | 175 = 52 · 7
2 341 = 11 · 13 52 85 = 5 · 17 102 133 = 7 · 19 bgcolor="#FFEBAD" | 152 bgcolor="#FFEBAD" | 153 = 32 · 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 bgcolor="#B3B7FF" | 104 bgcolor="#B3B7FF" | 105 = 3 · 5 · 7 154 155 = 5 · 31
bgcolor="#FFEBAD" | 5 bgcolor="#FFEBAD" | 124 = 22 · 31 bgcolor="#FFEBAD" | 55 bgcolor="#FFEBAD" | 63 = 32 · 7 105 451 = 11 · 41 bgcolor="#B3B7FF" | 155 bgcolor="#B3B7FF" | 231 = 3 · 7 · 11
6 35 = 5 · 7 56 57 = 3 · 19 106 133 = 7 · 19 156 217 = 7 · 31
bgcolor="#FFCBCB" | 7 bgcolor="#FFCBCB" | 25 = 52 57 65 = 5 · 13 107 133 = 7 · 19 bgcolor="#B3B7FF" | 157 bgcolor="#B3B7FF" | 186 = 2 · 3 · 31
bgcolor="#FFCBCB" | 8 bgcolor="#FFCBCB" | 9 = 32 58 133 = 7 · 19 108 341 = 11 · 31 158 159 = 3 · 53
bgcolor="#FFEBAD" | 9 bgcolor="#FFEBAD" | 28 = 22 · 7 59 87 = 3 · 29 bgcolor="#FFEBAD" | 109 bgcolor="#FFEBAD" | 117 = 32 · 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 bgcolor="#B3B7FF" | 111 bgcolor="#B3B7FF" | 190 = 2 · 5 · 19 bgcolor="#B3B7FF" | 161 bgcolor="#B3B7FF" | 190=2 · 5 · 19
12 65 = 5 · 13 bgcolor="#FFEBAD" | 62 bgcolor="#FFEBAD" | 63 = 32 · 7 bgcolor="#FFCBCB" | 112 bgcolor="#FFCBCB" | 121 = 112 162 481 = 13 · 37
13 21 = 3 · 7 63 341 = 11 · 31 113 133 = 7 · 19 bgcolor="#B3B7FF" | 163 bgcolor="#B3B7FF" | 186 = 2 · 3 · 31
14 15 = 3 · 5 64 65 = 5 · 13 114 115 = 5 · 23 bgcolor="#B3B7FF" | 164 bgcolor="#B3B7FF" | 165 = 3 · 5 · 11
15 341 = 11 13 bgcolor="#FFEBAD" | 65 bgcolor="#FFEBAD" | 112 = 24 · 7 115 133 = 7 · 19 bgcolor="#FFEBAD" | 165 bgcolor="#FFEBAD" | 172 = 22 · 43
16 51 = 3 · 17 66 91 = 7 · 13 bgcolor="#FFEBAD" | 116 bgcolor="#FFEBAD" | 117 = 32 · 13 166 301 = 7 · 43
bgcolor="#FFEBAD" | 17 bgcolor="#FFEBAD" | 45 = 32 · 5 67 85 = 5 · 17 117 145 = 5 · 29 bgcolor="#B3B7FF" | 167 bgcolor="#B3B7FF" | 231 = 3 · 7 · 11
bgcolor="#FFCBCB" | 18 bgcolor="#FFCBCB" | 25 = 52 68 69 = 3 · 23 118 119 = 7 · 17 bgcolor="#FFCBCB" | 168 bgcolor="#FFCBCB" | 169 = 132
bgcolor="#FFEBAD" | 19 bgcolor="#FFEBAD" | 45 = 32 · 5 69 85 = 5 · 17 119 177 = 3 · 59 bgcolor="#B3B7FF" | 169 bgcolor="#B3B7FF" | 231 = 3 · 7 · 11
20 21 = 3 · 7 bgcolor="#FFCBCB" | 70 bgcolor="#FFCBCB" | 169 = 132 bgcolor="#FFCBCB" | 120 bgcolor="#FFCBCB" | 121 = 112 bgcolor="#FFEBAD" | 170 bgcolor="#FFEBAD" | 171 = 32 · 19
21 55 = 5 · 11 bgcolor="#B3B7FF" | 71 bgcolor="#B3B7FF" | 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
bgcolor="#FFCBCB" | 24 bgcolor="#FFCBCB" | 25 = 52 bgcolor="#FFEBAD" | 74 bgcolor="#FFEBAD" | 75 = 3 · 52 bgcolor="#FFEBAD" | 124 bgcolor="#FFEBAD" | 125 = 33 bgcolor="#FFEBAD" | 174 bgcolor="#FFEBAD" | 175 = 52 · 7
bgcolor="#FFEBAD" | 25 bgcolor="#FFEBAD" | 28 = 22 · 7 75 91 = 7 · 13 125 133 = 7 · 19 175 319 = 11 · 19
bgcolor="#FFEBAD" | 26 bgcolor="#FFEBAD" | 27 = 33 76 77 = 7 · 11 126 247 = 13 · 19 176 177 = 3 · 59
27 65 = 5 · 13 77 247 = 13 · 19 bgcolor="#FFEBAD" | 127 bgcolor="#FFEBAD" | 153 = 32 · 17 bgcolor="#FFEBAD" | 177 bgcolor="#FFEBAD" | 196 = 22 · 72
bgcolor="#FFEBAD" | 28 bgcolor="#FFEBAD" | 45 = 32 · 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
bgcolor="#FFCBCB" | 30 bgcolor="#FFCBCB" | 49 = 72 bgcolor="#FFEBAD" | 80 bgcolor="#FFEBAD" | 81 = 34 130 217 = 7 · 31 180 217 = 7 · 31
bgcolor="#FFCBCB" | 31 bgcolor="#FFCBCB" | 49 = 72 81 = 34 85 = 5 · 17 131 143 = 11 · 13 bgcolor="#B3B7FF" | 181 bgcolor="#B3B7FF" | 195 = 3 · 5 · 13
32 33 = 3 · 11 82 91 = 7 · 13 132 133 = 7 · 19 182 183 = 3 · 61
33 85 = 5 · 17 bgcolor="#B3B7FF" | 83 bgcolor="#B3B7FF" | 105 = 3 · 5 · 7 133 145 = 5 · 29 183 221 = 13 · 17
34 35 = 5 · 7 84 85 = 5 · 17 bgcolor="#FFEBAD" | 134 bgcolor="#FFEBAD" | 135 = 33 · 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
bgcolor="#FFEBAD" | 37 bgcolor="#FFEBAD" | 45 = 32 · 5 87 91 = 7 · 13 bgcolor="#FFEBAD" | 137 bgcolor="#FFEBAD" | 148 = 22 · 37 187 217 = 7 · 31
38 39 = 3 · 13 88 91 = 7 · 13 138 259 = 7 · 37 bgcolor="#FFEBAD" | 188 bgcolor="#FFEBAD" | 189 = 33 · 7
39 95 = 5 · 19 bgcolor="#FFEBAD" | 89 bgcolor="#FFEBAD" | 99 = 32 · 11 139 161 = 7 · 23 189 235 = 5 · 47
40 91 = 7 · 13 90 91 = 7 · 13 140 141 = 3 · 47 bgcolor="#B3B7FF" | 190 bgcolor="#B3B7FF" | 231 = 3 · 7 · 11
bgcolor="#B3B7FF" | 41 bgcolor="#B3B7FF" | 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 bgcolor="#FFEBAD" | 193 bgcolor="#FFEBAD" | 276 = 22 · 3 · 23
bgcolor="#FFEBAD" | 44 bgcolor="#FFEBAD" | 45 = 32 · 5 94 95 = 5 · 19 144 145 = 5 · 29 bgcolor="#B3B7FF" | 194 bgcolor="#B3B7FF" | 195 = 3 · 5 · 13
bgcolor="#FFEBAD" | 45 bgcolor="#FFEBAD" | 76 = 22 · 19 95 141 = 3 · 47 bgcolor="#FFEBAD" | 145 bgcolor="#FFEBAD" | 153 = 32 · 17 195 259 = 7 · 37
46 133 = 7 · 19 96 133 = 7 · 19 bgcolor="#FFEBAD" | 146 bgcolor="#FFEBAD" | 147 = 3 · 72 196 205 = 5 · 41
47 65 = 5 · 13 bgcolor="#B3B7FF" | 97 bgcolor="#B3B7FF" | 105 = 3 · 5 · 7 bgcolor="#FFCBCB" | 147 bgcolor="#FFCBCB" | 169 = 132 bgcolor="#B3B7FF" | 197 bgcolor="#B3B7FF" | 231 = 3 · 7 · 11
bgcolor="#FFCBCB" | 48 bgcolor="#FFCBCB" | 49 = 72 bgcolor="#FFEBAD" | 98 bgcolor="#FFEBAD" | 99 = 32 · 11 bgcolor="#B3B7FF" | 148 bgcolor="#B3B7FF" | 231 = 3 · 7 · 11 198 247 = 13 · 19
bgcolor="#B3B7FF" | 49 bgcolor="#B3B7FF" | 66 = 2 · 3 · 11 99 145 = 5 · 29 bgcolor="#FFEBAD" | 149 bgcolor="#FFEBAD" | 175 = 52 · 7 bgcolor="#FFEBAD" | 199 bgcolor="#FFEBAD" | 225 = 32 · 52
50 51 = 3 · 17 bgcolor="#FFEBAD" | 100 bgcolor="#FFEBAD" | 153 = 32 · 17 bgcolor="#FFCBCB" | 150 bgcolor="#FFCBCB" | 169 = 132 200 201 = 3 · 67

See also

External links

 

<< PreviousWord BrowserNext >>
deep purple
chinese democracy movement
opeth
charles ponzi
qsl
uffizi
power supply (star trek)
monastery
hurwitz polynomial
intellectual capital
corte
raster image processor
giulio racah
amaya
national center for supercomputing applications
ladin language
loudspeaker
assured destruction
first strike
sigmoid
lineprinter
bolzano
trento
cathedral
leeuwarden
1260s bc
michigan technological university
the stranger (novel)
1270s bc
the man in the high castle
exponential distribution
beyond this horizon
rocket ship galileo
academy award for best short film live action 2 reels
space cadet
red planet
humpty dumpty
augusta
between planets
academy award for best dance direction
augusta, maine
starman jones
geometric distribution
podkayne of mars
Copyright 2005-2009 OnPedia.com. All Rights Reserved