Pseudoprimos Fermat

Los pseudoprimos de Fermat son números compuestos que pasan la prueba de Fermat . Nombrado en honor al matemático francés Pierre de Fermat . En teoría de números , los pseudoprimos de Fermat constituyen la clase más importante de pseudoprimos .

Definición

Pseudoprimos

Un número compuesto se llama pseudoprimo si cumple alguna condición necesaria (pero no suficiente ) para que el número sea primo, es decir, si tiene algunas propiedades de un número primo .

Pequeño teorema de Fermat

El pequeño teorema de Fermat dice que si n es un número primo, entonces para cada número coprimo de n , la congruencia se cumple . $a^{n-1} \equiv 1 \pmod n$

Granjas pseudosimples

Un número compuesto n se llama pseudoprimo de Fermat en base a (coprimo con n ) si se hace una comparación . En otras palabras, se dice que un número compuesto es pseudoprimo si pasa la prueba de Fermat para basar a [1] . Un número que es el pseudoprimo de Fermat en cada base coprima se llama número de Carmichael . $a^{n-1} \equiv 1 \pmod n$

Variaciones

Hay algunas variaciones en la definición:

Algunas fuentes requieren que el pseudoprimo sea impar [2] , ya que un número par es obviamente compuesto.
Cada número impar cumple para , por lo que en este caso no obtendremos nueva información sobre el número. Esto se descarta en la definición dada por Crandall y Pomerance [3] : Un número compuesto es un pseudoprimo de Fermat a la base si y $q$ $a^{q-1} \equiv 1 \pmod q$ $a=q-1$ $q$ $norte$ $a$ $a^{n-1} \equiv 1\pmod n$ $2 \ le a \ le n-2.$

Propiedades

Distribución

Hay infinitos pseudoprimos en una base dada (además, hay infinitos pseudoprimos fuertes [4] e infinitos números de Carmichael [5] ), pero son bastante raros [6] . Solo hay tres pseudoprimos de Fermat de base 2 menores que 1000, 245 menos de un millón y solo 21853 menos de 25 mil millones [4] .

Tablas con algunos pseudoprimos de Fermat

El pseudosimple más pequeño de Fermat

Los pseudosimples de Fermat más pequeños para cada base a ≤ 200 se dan en la siguiente tabla; los colores distinguen números por el número de divisores primos diferentes [7] .

El pseudosimple más pequeño de Fermat
a	p-pF más pequeño	a	p-pF más pequeño	a	p-pF más pequeño	a	p-pF más pequeño
una	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
cuatro	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
ocho	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
diez	33 = 3 11	60	341 = 11 31	110	111 = 3 37	160	161 = 7 23
once	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
catorce	15 = 3 5	64	65 = 5 13	114	115 = 5 23	164	165 = 3 5 11
quince	341 = 11 13	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
Dieciocho	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
veinte	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
treinta	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²
cincuenta	51 = 3 17	100	153 = 3² 17	150	169 = 13²	200	201 = 3 67

Números de Poole

Los pseudosimples de Fermat en base 2 se denominan números de Poulet , en honor al matemático belga Paul Poulet [8] . La factorización de los sesenta y un números de Poolet, incluidos los trece números de Carmichael (resaltados en negrita), se encuentra en la siguiente tabla.

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

El número de Poole, cuyos divisores d también dividen el número 2 d − 2, se llama supernúmero de Poole . Hay un número infinito de números de Poulet que no son supernúmeros de Poulet [9] .

Los primeros pseudoprimos de Fermat (hasta 10000) se basan en

Primeros pseudoprimos de Fermat (hasta 10000) en base a
a	Pseudoprimos de Fermat (hasta 10.000)	Secuencia OEIS (link is external)
una	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 números 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	A005935
cuatro	15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071, 2465, 2701, 33.3 3367 3683 4033 4369 4371 4681 4795 4859 5461 5551 6601 6643 7957 8321 8481 8695 8911 9061 9131 9211 9195	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, 31, 983, 983.	A005937
7	6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321	A005938
ocho	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, 66443, 7081, 7381, 7913, 8401, 8695, 874, 874, 8746, 8746, 8746, 874, 874, 874, 874, 874, 874, 874, 874, 874, 874, 874, 874, 874, 874, 874, 874, 874, 874, 874, 874, 874, 874, 874, 874, 8746, 8746, 8746, 8746, 8746, 8746, 8466, 8746, 8466, 8866ES 8911	A020138
diez	9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, 4141, 4187, 4521, 5461, 6533 7, 41054,1 , 7777, 8149, 8401, 8911	A005939
once	10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257, 2465, 2821, 4577, 4921, 5041, 5185, 86015,8 86015,8 , 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 5, 5 3653, . 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, 8 84911, 8 , 9577, 9637	A020141
catorce	15, 39, 65, 195, 481, 561, 781, 793, 841, 985, 1105, 1111, 1541, 1891, 2257, 2465, 2561, 2665, 2743, 3277, 5185, 5713, 651,65 7449, 7543, 7585, 8321, 9073	A020142
quince	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, 209240 , 2431, 2465, 2701, 2821, 3133, 3277, 3367, 3655, 3683, 4033, 4369, 4371, 4681, 4795, 4859, 5083, 5151, 5461, 5551, 6601, 6643, 7471, 7735, 7735, 7735 , 7735, 7735, 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, 697,3 76 713,3 , 8481, 8911	A020145
Dieciocho	25, 49, 65, 85, 133, 221, 323, 325, 343, 425, 451, 637, 931, 1105, 1225, 1369, 1387, 1649, 1729, 1921, 2149, 2465, 2701, 29725,. 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, 3 2015 , 4033, 4681, 5461, 5466, 5713, 6223, 6541, 6601, 6697, 7957, 8145, 8281, 8401, 8869, 9211, 9997	A020147
veinte	21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501, 2761, 2821, 2947, 3059, 3201, 404,7, 1 5, 6313, 1 , 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 2437 2437 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, 3219, 2. 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, 8745, 8745, 865, 865, 865, 865, 865, 865, 86515, 86515, 86515, 86515, 86515, 86515, 86515, 86515, 86515, 86515 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, 28,85, 3781, 694 , 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. 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, 2821,. 2993, 3146, 3281, 3367, 3605, 3751, 4033, 4745, 4921, 4961, 5299, 5461, 5551, 5611, 5621, 6305, 6533, 6601, 7381, 7585, 7957, 8227, 8321, 8401, 8410 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, 3 5149. , 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
treinta	49, 91, 133, 217, 247, 341, 403, 469, 493, 589, 637, 703, 871, 899, 901, 931, 1273, 1519, 1537, 1729, 2059, 2077, 2821, 327, 3,7 , 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 sobre los pseudoprimos de Fermat a las bases 31 - 100, consulte los artículos A020159 - A020228 de la Encyclopedia of Integer Sequences [10] .

Razones por las que un número es pseudoprimo

A continuación se muestra una tabla de todas las bases b < n para las cuales n es un pseudoprimo de Fermat (todos los números compuestos son pseudoprimos en base 1, y para b > n la solución simplemente se desplaza por k * n , donde k > 0) si el compuesto el número n no está indicado en la tabla, entonces es pseudoprimo solo en base 1, o en bases comparables a 1 (mod n ), es decir, el número de bases b es 1. La tabla está compilada para n < 180 [11] .

Bases b para las que n es pseudoprima
norte	Bases b para las que n es pseudosimple Fermat(< n )	Número de bases b (< n ) [12]
9	Dieciocho	2
quince	1, 4, 11, 14	cuatro
21	1, 8, 13, 20	cuatro
25	1, 7, 18, 24	cuatro
27	1, 26	2
28	1, 9, 25	3
33	1, 10, 23, 32	cuatro
35	1, 6, 29, 34	cuatro
39	1, 14, 25, 38	cuatro
45	1, 8, 17, 19, 26, 28, 37, 44	ocho
49	1, 18, 19, 30, 31, 48	6
51	1, 16, 35, 50	cuatro
52	1, 9, 29	3
55	1, 21, 34, 54	cuatro
57	1, 20, 37, 56	cuatro
63	1, 8, 55, 62	cuatro
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	cuatro
70	1, 11, 51	3
75	1, 26, 49, 74	cuatro
76	1, 45, 49	3
77	1, 34, 43, 76	cuatro
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	cuatro
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	cuatro
95	1, 39, 56, 94	cuatro
99	1, 10, 89, 98	cuatro
105	1, 8, 13, 22, 29, 34, 41, 43, 62, 64, 71, 76, 83, 92, 97, 104	dieciséis
111	1, 38, 73, 110	cuatro
112	1, 65, 81	3
115	1, 24, 91, 114	cuatro
117	1, 8, 44, 53, 64, 73, 109, 116	ocho
119	1, 50, 69, 118	cuatro
121	1, 3, 9, 27, 40, 81, 94, 112, 118, 120	diez
123	1, 40, 83, 122	cuatro
124	1, 5, 25	3
125	1, 57, 68, 124	cuatro
129	1, 44, 85, 128	cuatro
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	cuatro
141	1, 46, 95, 140	cuatro
143	1, 12, 131, 142	cuatro
145	1, 12, 17, 28, 41, 46, 57, 59, 86, 88, 99, 104, 117, 128, 133, 144	dieciséis
147	1, 50, 97, 146	cuatro
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	cuatro
159	1, 52, 107, 158	cuatro
161	1, 22, 139, 160	cuatro
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	cuatro
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	cuatro

Cabe señalar que si p es primo, entonces p 2 es el pseudoprimo de Fermat en base b si y sólo si p es un primo de Wieferich en base b . Por ejemplo, 1093 2 = 1 194 649 es la base 2 pseudosimple de Fermat.

El número de bases b para n (para primos n , el número de bases b debe ser igual a n-1 , ya que todos los b satisfacen 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 OEIS )

La base más pequeña b > 1 para la cual n es pseudoprimo (o primo):

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 OEIS ).

Pseudosimple débil

Un número compuesto n que satisface la comparación b n = b (mod n ) se denomina pseudoprimo débil de Fermat en base b (aquí b no necesita ser coprimo con n ) [13] . Los pseudoprimos débiles más pequeños a la base b 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 OEIS )

Si se requiere que n > b , entonces:

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 OEIS )

Aplicaciones

Debido a su rareza, estos pseudoprimos tienen importantes aplicaciones prácticas. Por ejemplo, los algoritmos criptográficos de clave pública como RSA requieren la capacidad de encontrar rápidamente números primos grandes [14] . El algoritmo habitual para generar números primos es generar números impares aleatorios y comprobar su primacía . Sin embargo, las pruebas de primalidad determinista son lentas. Si estamos dispuestos a aceptar una probabilidad arbitrariamente pequeña de que el número encontrado no sea primo, sino pseudoprimo, se puede utilizar una prueba de Fermat mucho más rápida y sencilla .

Notas

↑ Desmedt, Yvo. Esquemas de cifrado // Manual de algoritmos y teoría de la computación: temas y técnicas especiales (inglés) / Atallah, Mikhail J.y Blanton, Marina. - Prensa CRC , 2010. - Pág. 10-23. — ISBN 978-1-58488-820-8 .
↑ Weisstein, Eric W. Fermat Pseudoprime en el sitio web de Wolfram MathWorld .
↑ Crandall, Pomerance, 2011 , pág. 155.
↑ 1 2 Pomerance, Selfridge, Wagstaff 1980 , Teorema 1.
↑ WR Alford ; Andrés Granville ; Carlos Pomerance . Hay infinitamente muchos números de Carmichael // Annals of Mathematics : journal . - 1994. - vol. 139 . - Pág. 703-722 . -doi : 10.2307/ 2118576 .
↑ Crandall, Pomerance, 2011 , Teorema 3.4.2, p. 154-155.
↑ Secuencia OEIS A007535 _
↑ Secuencia OEIS A001567 _
↑ W. Sierpinski. Capítulo V.7 // Teoría elemental de números = Teoria Liczb / Ed. A. Schinzel. - 2 sub ediciones. - Ámsterdam: Holanda Septentrional, 1988-02-15. - S. 232. - 528 pág. — (Biblioteca Matemática de Holanda Septentrional). — ISBN 9780444866622 . Archivado el 8 de diciembre de 2015 en Wayback Machine .
↑ Véase también la tabla de pseudoprimos de Fermat para bases hasta 150 (alemán) ; aquí n no está definido como pseudoprimo en bases comparables a 1 o -1 (mod n ).
↑ Información más detallada para n = 181 ... 5000 está en la tabla (alemán) ; aquí n no está definido como pseudoprimo en bases comparables a 1 o -1 (mod n ).
↑ Secuencia OEIS A063994 _
↑ Crandall, Pomerance, 2011 , Teorema 3.4.1, p. 154.
↑ Crandall, Pomerance, 2011 , Algoritmo 8.1.2, p. 438.

Literatura

Richard Crandall, Carl Pomerance. Números primos: aspectos criptográficos y computacionales. - Casa del Libro "LIBROKOM", 2011. - P. 154-158, 438-441.
Carlos Pomerance ; John L. Selfridge , Samuel S. Wagstaff, Jr Los pseudoprimos a 25 10 9 // Matemáticas de Computación : diario. - 1980. - julio ( vol. 35 , núm. 151 ). - P. 1003-1026 . -doi : 10.1090/ S0025-5718-1980-0572872-7 .