Pseudoprima de Fermat - Fermat pseudoprime
En teoría de números , los pseudoprimos de Fermat constituyen la clase más importante de pseudoprimos que provienen del pequeño teorema de Fermat .
Definición
El pequeño teorema de Fermat establece que si p es primo y una es primos entre sí a p , entonces un p -1 - 1 es divisible por p . Para un entero a > 1, si un entero compuesto x divide a x −1 - 1, entonces x se denomina pseudoprime de Fermat a la base a . En otras palabras, un entero compuesto es un pseudoprime de Fermat a la base a si pasa con éxito la prueba de primalidad de Fermat para la base a . La afirmación falsa de que todos los números que pasan la prueba de primalidad de Fermat para la base 2 son primos se llama hipótesis china .
El pseudoprime de Fermat en base 2 más pequeño es 341. No es un primo, ya que es igual a 11 · 31, pero satisface el pequeño teorema de Fermat: 2 340 ≡ 1 (mod 341) y, por lo tanto, pasa la prueba de primalidad de Fermat para la base 2.
Los pseudoprimos de base 2 a veces se denominan números de Sarrus , en honor a PF Sarrus que descubrió que 341 tiene esta propiedad, números de Poulet , en honor a P. Poulet que hizo una tabla de tales números, o fermatianos (secuencia A001567 en la OEIS ).
Un pseudoprime de Fermat a menudo se denomina pseudoprime , entendiéndose el modificador Fermat .
Un entero x que es un pseudoprimo de Fermat para todos los valores de a que son coprimos ax se llama número de Carmichael .
Propiedades
Distribución
Hay infinitos pseudoprimos para cualquier base dada a > 1. En 1904, Cipolla mostró cómo producir un número infinito de pseudoprimos base a > 1: Sea p un primo que no divide a 2 - 1. Sea A = ( a p - 1) / ( a - 1) y sea B = ( a p + 1) / ( a + 1). Entonces n = AB es compuesto y es un pseudoprime a la base a . Por ejemplo, si a = 2 y p = 5, entonces A = 31, B = 11 y n = 341 es un pseudoprime a base 2.
De hecho, hay infinitos pseudoprimos fuertes para cualquier base mayor que 1 (ver Teorema 1 de) e infinitos números de Carmichael, pero son comparativamente raros. Hay tres pseudoprimos en base 2 por debajo de 1000, 245 por debajo de un millón y 21853 por debajo de 25 · 10 9 . Hay 4842 pseudoprimes fuertes en base 2 y 2163 números de Carmichael por debajo de este límite (consulte la Tabla 1 de).
A partir de 17 · 257, el producto de números de Fermat consecutivos es un pseudoprime en base 2, al igual que todos los compuestos de Fermat y los compuestos de Mersenne .
Factorizaciones
Las factorizaciones de los 60 números de Poulet hasta el 60787, incluidos 13 números de Carmichael (en negrita), se encuentran en la siguiente tabla.
(secuencia A001567 en la OEIS )
|
|
|
|
Un número de Poulet cuyos divisores d dividen 2 d - 2 se denomina número super-Poulet . Hay infinitos números de Poulet que no son números superpoulet.
Los pseudoprimes de Fermat más pequeños
El pseudoprime más pequeño para cada base a ≤ 200 se da en la siguiente tabla; los colores marcan el número de factores primos. A diferencia de la definición al comienzo del artículo, los pseudoprimes debajo de a se excluyen de la tabla. (Para permitir pseudoprimes por debajo de a , consulte OEIS : A090086 )
(secuencia A007535 en la OEIS )
a | pp más pequeño | a | pp más pequeño | a | pp más pequeño | a | pp más pequeño |
---|---|---|---|---|---|---|---|
1 | 4 = 2² | 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 · 31 | sesenta y cinco | 112 = 2⁴ · 7 | 115 | 133 = 7 · 19 | 165 | 172 = 2² · 43 |
dieciséis | 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 = 3⁴ | 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 |
Lista de pseudoprimos de Fermat en base fija n
norte | Primeros pocos pseudoprimos de Fermat en base n | Secuencia OEIS |
1 | 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100, .. . (Todos los compuestos) | A002808 |
2 | 341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, ... | A001567 |
3 | 91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, ... | A005935 |
4 | 15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071, 2465, 2701, 2821, 3133, 3277, 3367, 3683, 4033, 4369, 4371, 4681, 4795, 4859, 5461, 5551, 6601, 6643, 7957, 8321, 8481, 8695, 8911, 9061, 9131, 9211, 9605, 9919, ... | A020136 |
5 | 4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881, ... | A005936 |
6 | 35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3913, 4123, 4495, 5713, 6533, 6601, 8029, 8365, 8911, 9331, 9881, ... | A005937 |
7 | 6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, ... | A005938 |
8 | 9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949, 1001, 1105, 1281, 1365, 1387, 1417, 1541, 1649, 1661, 1729, 1785, 1905, 2047, 2169, 2465, 2501, 2701, 2821, 3145, 3171, 3201, 3277, 3605, 3641, 4005, 4033, 4097, 4369, 4371, 4641, 4681, 4921, 5461, 5565, 5963, 6305, 6533, 6601, 6951, 7107, 7161, 7957, 8321, 8481, 8911, 9265, 9709, 9773, 9881, 9945, ... | A020137 |
9 | 4, 8, 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288, 1387, 1541, 1729, 1891, 2465, 2501, 2665, 2701, 2806, 2821, 2926, 3052, 3281, 3367, 3751, 4376, 4636, 4961, 5356, 5551, 6364, 6601, 6643, 7081, 7381, 7913, 8401, 8695, 8744, 8866, 8911, ... | A020138 |
10 | 9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, 4141, 4187, 4521, 5461, 6533, 6541, 6601, 7107, 7471, 7777, 8149, 8401, 8911, ... | A005939 |
11 | 10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257, 2465, 2821, 4577, 4921, 5041, 5185, 6601, 7869, 8113, 8170, 8695, 8911, 9730, ... | A020139 |
12 | 65, 91, 133, 143, 145, 247, 377, 385, 703, 1045, 1099, 1105, 1649, 1729, 1885, 1891, 2041, 2233, 2465, 2701, 2821, 2983, 3367, 3553, 5005, 5365, 5551, 5785, 6061, 6305, 6601, 8911, 9073, ... | A020140 |
13 | 4, 6, 12, 21, 85, 105, 231, 244, 276, 357, 427, 561, 1099, 1785, 1891, 2465, 2806, 3605, 5028, 5149, 5185, 5565, 6601, 7107, 8841, 8911, 9577, 9637, ... | A020141 |
14 | 15, 39, 65, 195, 481, 561, 781, 793, 841, 985, 1105, 1111, 1541, 1891, 2257, 2465, 2561, 2665, 2743, 3277, 5185, 5713, 6501, 6533, 6541, 7107, 7171, 7449, 7543, 7585, 8321, 9073, ... | A020142 |
15 | 14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8701, 8911, 9073, ... | A020143 |
dieciséis | 15, 51, 85, 91, 255, 341, 435, 451, 561, 595, 645, 703, 1105, 1247, 1261, 1271, 1285, 1387, 1581, 1687, 1695, 1729, 1891, 1905, 2047, 2071, 2091, 2431, 2465, 2701, 2821, 3133, 3277, 3367, 3655, 3683, 4033, 4369, 4371, 4681, 4795, 4859, 5083, 5151, 5461, 5551, 6601, 6643, 7471, 7735, 7957, 8119, 8227, 8245, 8321, 8481, 8695, 8749, 8911, 9061, 9131, 9211, 9605, 9919, ... | A020144 |
17 | 4, 8, 9, 16, 45, 91, 145, 261, 781, 1111, 1228, 1305, 1729, 1885, 2149, 2821, 3991, 4005, 4033, 4187, 4912, 5365, 5662, 5833, 6601, 6697, 7171, 8481, 8911, ... | A020145 |
18 | 25, 49, 65, 85, 133, 221, 323, 325, 343, 425, 451, 637, 931, 1105, 1225, 1369, 1387, 1649, 1729, 1921, 2149, 2465, 2701, 2821, 2825, 2977, 3325, 4165, 4577, 4753, 5525, 5725, 5833, 5941, 6305, 6517, 6601, 7345, 8911, 9061, ... | A020146 |
19 | 6, 9, 15, 18, 45, 49, 153, 169, 343, 561, 637, 889, 905, 906, 1035, 1105, 1629, 1661, 1849, 1891, 2353, 2465, 2701, 2821, 2955, 3201, 4033, 4681, 5461, 5466, 5713, 6223, 6541, 6601, 6697, 7957, 8145, 8281, 8401, 8869, 9211, 9997, ... | A020147 |
20 | 21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501, 2761, 2821, 2947, 3059, 3201, 4047, 5271, 5461, 5473, 5713, 5833, 6601, 6817, 7999, 8421, 8911, ... | A020148 |
21 | 4, 10, 20, 55, 65, 85, 221, 703, 793, 1045, 1105, 1852, 2035, 2465, 3781, 4630, 5185, 5473, 5995, 6541, 7363, 8695, 8965, 9061, .. . | A020149 |
22 | 21, 69, 91, 105, 161, 169, 345, 483, 485, 645, 805, 1105, 1183, 1247, 1261, 1541, 1649, 1729, 1891, 2037, 2041, 2047, 2413, 2465, 2737, 2821, 3241, 3605, 3801, 5551, 5565, 5963, 6019, 6601, 6693, 7081, 7107, 7267, 7665, 8119, 8365, 8421, 8911, 9453, ... | A020150 |
23 | 22, 33, 91, 154, 165, 169, 265, 341, 385, 451, 481, 553, 561, 638, 946, 1027, 1045, 1065, 1105, 1183, 1271, 1729, 1738, 1749, 2059, 2321, 2465, 2501, 2701, 2821, 2926, 3097, 3445, 4033, 4081, 4345, 4371, 4681, 5005, 5149, 6253, 6369, 6533, 6541, 7189, 7267, 7957, 8321, 8365, 8651, 8745, 8911, 8965, 9805, ... | A020151 |
24 | 25, 115, 175, 325, 553, 575, 805, 949, 1105, 1541, 1729, 1771, 1825, 1975, 2413, 2425, 2465, 2701, 2737, 2821, 2885, 3781, 4207, 4537, 6601, 6931, 6943, 7081, 7189, 7471, 7501, 7813, 8725, 8911, 9085, 9361, 9809, ... | A020152 |
25 | 4, 6, 8, 12, 24, 28, 39, 66, 91, 124, 217, 232, 276, 403, 426, 451, 532, 561, 616, 703, 781, 804, 868, 946, 1128, 1288, 1541, 1729, 1891, 2047, 2701, 2806, 2821, 2911, 2926, 3052, 3126, 3367, 3592, 3976, 4069, 4123, 4207, 4564, 4636, 4686, 5321, 5461, 5551, 5611, 5662, 5731, 5963, 6601, 7449, 7588, 7813, 8029, 8646, 8911, 9881, 9976, ... | A020153 |
26 | 9, 15, 25, 27, 45, 75, 133, 135, 153, 175, 217, 225, 259, 425, 475, 561, 589, 675, 703, 775, 925, 1035, 1065, 1147, 2465, 3145, 3325, 3385, 3565, 3825, 4123, 4525, 4741, 4921, 5041, 5425, 6093, 6475, 6525, 6601, 6697, 8029, 8695, 8911, 9073, ... | A020154 |
27 | 26, 65, 91, 121, 133, 247, 259, 286, 341, 365, 481, 671, 703, 949, 1001, 1105, 1541, 1649, 1729, 1891, 2071, 2465, 2665, 2701, 2821, 2981, 2993, 3146, 3281, 3367, 3605, 3751, 4033, 4745, 4921, 4961, 5299, 5461, 5551, 5611, 5621, 6305, 6533, 6601, 7381, 7585, 7957, 8227, 8321, 8401, 8911, 9139, 9709, 9809, 9841, 9881, 9919, ... | A020155 |
28 | 9, 27, 45, 87, 145, 261, 361, 529, 561, 703, 783, 785, 1105, 1305, 1413, 1431, 1885, 2041, 2413, 2465, 2871, 3201, 3277, 4553, 4699, 5149, 5181, 5365, 7065, 8149, 8321, 8401, 9841, ... | A020156 |
29 | 4, 14, 15, 21, 28, 35, 52, 91, 105, 231, 268, 341, 364, 469, 481, 561, 651, 793, 871, 1105, 1729, 1876, 1897, 2105, 2257, 2821, 3484, 3523, 4069, 4371, 4411, 5149, 5185, 5356, 5473, 5565, 5611, 6097, 6601, 7161, 7294, 8321, 8401, 8421, 8841, 8911, ... | A020157 |
30 | 49, 91, 133, 217, 247, 341, 403, 469, 493, 589, 637, 703, 871, 899, 901, 931, 1273, 1519, 1537, 1729, 2059, 2077, 2821, 3097, 3277, 3283, 3367, 3577, 4081, 4097, 4123, 5729, 6031, 6061, 6097, 6409, 6601, 6817, 7657, 8023, 8029, 8401, 8911, 9881, ... | A020158 |
Para obtener más información (base 31 a 100), consulte OEIS : A020159 a OEIS : A020228 , y para todas las bases hasta 150, consulte la tabla de pseudoprimes Fermat (texto en alemán) , esta página no define n es un pseudoprime a una base congruente con 1 o -1 (mod n )
¿Qué bases b forman n una pseudoprima de Fermat?
Si el compuesto es par, entonces es un pseudoprime de Fermat a la base trivial . Si el compuesto es impar, entonces es un pseudoprime de Fermat a las bases triviales .
Para cualquier compuesto , el número de módulos de bases distintas , para el cual es una base pseudoprime de Fermat , es
donde se encuentran los distintos factores primos de . Esto incluye las bases triviales.
Por ejemplo, este producto es . Porque , la base no trivial más pequeña es .
Cada compuesto impar es un pseudoprime de Fermat a al menos dos módulos de bases no triviales a menos que sea una potencia de 3.
Para el compuesto n <200, la siguiente es una tabla de todas las bases b < n donde n es un pseudoprime de Fermat. Si un número compuesto n no está en la tabla (o n está en la secuencia A209211 ), entonces n es un pseudoprime solo para el módulo n de base 1 trivial .
norte | bases b en las que n es una pseudoprima de Fermat (< n ) | número de bases de b (< n ) (secuencia A063994 en la OEIS ) |
9 | 1, 8 | 2 |
15 | 1, 4, 11, 14 | 4 |
21 | 1, 8, 13, 20 | 4 |
25 | 1, 7, 18, 24 | 4 |
27 | 1, 26 | 2 |
28 | 1, 9, 25 | 3 |
33 | 1, 10, 23, 32 | 4 |
35 | 1, 6, 29, 34 | 4 |
39 | 1, 14, 25, 38 | 4 |
45 | 1, 8, 17, 19, 26, 28, 37, 44 | 8 |
49 | 1, 18, 19, 30, 31, 48 | 6 |
51 | 1, 16, 35, 50 | 4 |
52 | 1, 9, 29 | 3 |
55 | 1, 21, 34, 54 | 4 |
57 | 1, 20, 37, 56 | 4 |
63 | 1, 8, 55, 62 | 4 |
sesenta y cinco | 1, 8, 12, 14, 18, 21, 27, 31, 34, 38, 44, 47, 51, 53, 57, 64 | dieciséis |
66 | 1, 25, 31, 37, 49 | 5 |
69 | 1, 22, 47, 68 | 4 |
70 | 1, 11, 51 | 3 |
75 | 1, 26, 49, 74 | 4 |
76 | 1, 45, 49 | 3 |
77 | 1, 34, 43, 76 | 4 |
81 | 1, 80 | 2 |
85 | 1, 4, 13, 16, 18, 21, 33, 38, 47, 52, 64, 67, 69, 72, 81, 84 | dieciséis |
87 | 1, 28, 59, 86 | 4 |
91 | 1, 3, 4, 9, 10, 12, 16, 17, 22, 23, 25, 27, 29, 30, 36, 38, 40, 43, 48, 51, 53, 55, 61, 62, 64, 66, 68, 69, 74, 75, 79, 81, 82, 87, 88, 90 |
36 |
93 | 1, 32, 61, 92 | 4 |
95 | 1, 39, 56, 94 | 4 |
99 | 1, 10, 89, 98 | 4 |
105 | 1, 8, 13, 22, 29, 34, 41, 43, 62, 64, 71, 76, 83, 92, 97, 104 | dieciséis |
111 | 1, 38, 73, 110 | 4 |
112 | 1, 65, 81 | 3 |
115 | 1, 24, 91, 114 | 4 |
117 | 1, 8, 44, 53, 64, 73, 109, 116 | 8 |
119 | 1, 50, 69, 118 | 4 |
121 | 1, 3, 9, 27, 40, 81, 94, 112, 118, 120 | 10 |
123 | 1, 40, 83, 122 | 4 |
124 | 1, 5, 25 | 3 |
125 | 1, 57, 68, 124 | 4 |
129 | 1, 44, 85, 128 | 4 |
130 | 1, 61, 81 | 3 |
133 | 1, 8, 11, 12, 18, 20, 26, 27, 30, 31, 37, 39, 45, 46, 50, 58, 64, 65, 68, 69, 75, 83, 87, 88, 94, 96, 102, 103, 106, 107, 113, 115, 121, 122, 125, 132 |
36 |
135 | 1, 26, 109, 134 | 4 |
141 | 1, 46, 95, 140 | 4 |
143 | 1, 12, 131, 142 | 4 |
145 | 1, 12, 17, 28, 41, 46, 57, 59, 86, 88, 99, 104, 117, 128, 133, 144 | dieciséis |
147 | 1, 50, 97, 146 | 4 |
148 | 1, 121, 137 | 3 |
153 | 1, 8, 19, 26, 35, 53, 55, 64, 89, 98, 100, 118, 127, 134, 145, 152 | dieciséis |
154 | 1, 23, 67 | 3 |
155 | 1, 61, 94, 154 | 4 |
159 | 1, 52, 107, 158 | 4 |
161 | 1, 22, 139, 160 | 4 |
165 | 1, 23, 32, 34, 43, 56, 67, 76, 89, 98, 109, 122, 131, 133, 142, 164 | dieciséis |
169 | 1, 19, 22, 23, 70, 80, 89, 99, 146, 147, 150, 168 | 12 |
171 | 1, 37, 134, 170 | 4 |
172 | 1, 49, 165 | 3 |
175 | 1, 24, 26, 51, 74, 76, 99, 101, 124, 149, 151, 174 | 12 |
176 | 1, 49, 81, 97, 113 | 5 |
177 | 1, 58, 119, 176 | 4 |
183 | 1, 62, 121, 182 | 4 |
185 | 1, 6, 31, 36, 38, 43, 68, 73, 112, 117, 142, 147, 149, 154, 179, 184 | dieciséis |
186 | 1, 97, 109, 157, 163 | 5 |
187 | 1, 67, 120, 186 | 4 |
189 | 1, 55, 134, 188 | 4 |
190 | 1, 11, 61, 81, 101, 111, 121, 131, 161 | 9 |
195 | 1, 14, 64, 79, 116, 131, 181, 194 | 8 |
196 | 1, 165, 177 | 3 |
Para obtener más información ( n = 201 a 5000), consulte, esta página no define n es un pseudoprime a una base congruente con 1 o -1 (mod n ). Cuando p es un primo, p 2 es un pseudoprimo de Fermat a la base b si y solo si p es un primo de Wieferich a la base b . Por ejemplo, 1093 2 = 1194649 es un pseudoprime de Fermat a base 2, y 11 2 = 121 es un pseudoprime de Fermat a base 3.
El número de valores de b para n son (Para n primos, el número de valores de b debe ser n - 1, ya que todo b satisface el pequeño teorema de Fermat )
- 1, 1, 2, 1, 4, 1, 6, 1, 2, 1, 10, 1, 12, 1, 4, 1, 16, 1, 18, 1, 4, 1, 22, 1, 4, 1, 2, 3, 28, 1, 30, 1, 4, 1, 4, 1, 36, 1, 4, 1, 40, 1, 42, 1, 8, 1, 46, 1, 6, 1, ... (secuencia A063994 en la OEIS )
La mínima base b > 1 que n es un pseudoprime a la base b (o número primo) son
- 2, 3, 2, 5, 2, 7, 2, 9, 8, 11, 2, 13, 2, 15, 4, 17, 2, 19, 2, 21, 8, 23, 2, 25, 7, 27, 26, 9, 2, 31, 2, 33, 10, 35, 6, 37, 2, 39, 14, 41, 2, 43, 2, 45, 8, 47, 2, 49, 18, 51, ... (secuencia A105222 en la OEIS )
El número de los valores de b para n debe dividir ( n ), o A000010 ( n ) = 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8 , 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16 , 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, ... (El cociente puede ser cualquier número natural y el cociente = 1 si y solo si n es un número primo o de Carmichael (561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, ... A002997 ), el cociente = 2 si y solo si n está en la secuencia: 4, 6, 15, 91, 703, 1891 , 2701, 11305, 12403, 13981, 18721, ... A191311 )
El menor número con n valores de b son (o 0 si no existe tal número)
- 1, 3, 28, 5, 66, 7, 232, 45, 190, 11, 276, 13, 1106, 0, 286, 17, 1854, 19, 3820, 891, 2752, 23, 1128, 595, 2046, 0, 532, 29, 1770, 31, 9952, 425, 1288, 0, 2486, 37, 8474, 0, 742, 41, 3486, 43, 7612, 5589, 2356, 47, 13584, 325, 9850, 0, ... (secuencia A064234 en la OEIS ) ( si y sólo si n es incluso y no totient de número squarefree , entonces el n º término de esta secuencia es 0)
Pseudoprimes débiles
Un número compuesto n que satisface eso se llama pseudoprime débil a la base b . Un pseudoprime para basar a (según la definición habitual) satisface esta condición. Por el contrario, un pseudoprime débil que es coprime con la base es un pseudoprime en el sentido habitual; de lo contrario, este puede ser el caso o no. Los pseudoprime menos débiles a la base b = 1, 2, ... son:
- 4, 341, 6, 4, 4, 6, 6, 4, 4, 6, 10, 4, 4, 14, 6, 4, 4, 6, 6, 4, 4, 6, 22, 4, 4, 9, 6, 4, 4, 6, 6, 4, 4, 6, 9, 4, 4, 38, 6, 4, 4, 6, 6, 4, 4, 6, 46, 4, 4, 10, ... (secuencia A000790 en la OEIS )
Todos los términos son menores o iguales al número de Carmichael más pequeño, 561. A excepción de 561, solo pueden ocurrir semiprimos en la secuencia anterior, pero no todos los semiprimos menores que 561 ocurren, un semiprimo pq ( p ≤ q ) menor que 561 ocurre en las secuencias anteriores si y solo si p - 1 divide q - 1. (ver OEIS : A108574 ) Además, el pseudoprime más pequeño a la base n (tampoco es necesario que exceda n ) ( OEIS : A090086 ) también suele ser semiprime, el primer contraejemplo es A090086 (648) = 385 = 5 × 7 × 11.
Si requerimos n > b , son (para b = 1, 2, ...)
- 4, 341, 6, 6, 10, 10, 14, 9, 12, 15, 15, 22, 21, 15, 21, 20, 34, 25, 38, 21, 28, 33, 33, 25, 28, 27, 39, 36, 35, 49, 49, 33, 44, 35, 45, 42, 45, 39, 57, 52, 82, 66, 77, 45, 55, 69, 65, 49, 56, 51, ... (secuencia A239293 en la OEIS )
Los números de Carmichael son pseudoprimos débiles para todas las bases.
El pseudoprime más pequeño incluso débil en la base 2 es 161038 (consulte OEIS : A006935 ).
Pseudoprimos de Euler-Jacobi
Otro enfoque es utilizar nociones más refinadas de pseudoprimales, por ejemplo, pseudoprimos fuertes o pseudoprimes de Euler-Jacobi , para los cuales no hay análogos de los números de Carmichael . Esto conduce a algoritmos de probabilidad como la prueba Solovay-Strassen primalidad , el test de primalidad Baillie-PSW , y el test de primalidad Miller-Rabin , que producen lo que se conoce como números primos de grado industrial . Los números primos de grado industrial son números enteros cuya primalidad no ha sido "certificada" (es decir, rigurosamente probada), pero que se han sometido a una prueba como la prueba de Miller-Rabin que tiene una probabilidad de falla distinta de cero, pero arbitrariamente baja.
Aplicaciones
La rareza de tales pseudoprimes tiene importantes implicaciones prácticas. Por ejemplo, los algoritmos de criptografía de clave pública como RSA requieren la capacidad de encontrar rápidamente números primos grandes. El algoritmo habitual para generar números primos es generar números impares aleatorios y probar su primalidad. Sin embargo, las pruebas de primalidad deterministas son lentas. Si el usuario está dispuesto a tolerar una probabilidad arbitrariamente pequeña de que el número encontrado no sea un número primo sino un pseudoprimo, es posible utilizar la prueba de primalidad de Fermat, mucho más rápida y sencilla .
Referencias
enlaces externos
- WF Galway y Jan Feitsma, Tablas de pseudoprimes a base 2 y datos relacionados (lista completa de todos los pseudoprimes a base 2 por debajo de 2 64 , incluida la factorización, pseudoprimes fuertes y números de Carmichael)
- Una investigación para pseudoprime