Pseudoprime Fermat

Pseudoprimele lui Fermat sunt numere compuse care trec testul Fermat . Numit după matematicianul francez Pierre de Fermat . În teoria numerelor , pseudoprimele lui Fermat constituie cea mai importantă clasă de pseudoprime .

Definiție

Pseudoprime

Un număr compus se numește pseudoprim dacă îndeplinește o condiție necesară (dar nu suficientă ) pentru ca numărul să fie prim, adică dacă are unele proprietăți ale unui număr prim .

Mica Teoremă a lui Fermat

Mica Teoremă a lui Fermat spune că dacă n este un număr prim, atunci pentru fiecare număr un coprim la n , congruența este valabilă . $a^{n-1} \equiv 1 \pmod n$

Ferme pseudosimple

Un număr compus n se numește pseudoprim Fermat în baza a (coprim la n ) dacă se face comparație . Cu alte cuvinte, se spune că un număr compus este pseudoprim dacă trece testul Fermat pentru a baza a [1] . Un număr care este pseudoprimul lui Fermat în fiecare bază coprime se numește număr Carmichael . $a^{n-1} \equiv 1 \pmod n$

Variante

Există câteva variații ale definiției:

Unele surse necesită ca pseudoprimul să fie impar [2] , deoarece un număr par este evident compus.
Fiecare număr impar satisface pentru , așa că în acest caz nu vom obține informații noi despre număr. Acest lucru este exclus în definiția dată de Crandall și Pomerance [3] : Un număr compus este un pseudoprim Fermat la bază dacă și $q$ $a^{q-1} \equiv 1 \pmod q$ $a=q-1$ $q$ $n$ $A$ $a^{n-1} \equiv 1\pmod n$ $2 \le a \le n-2.$

Proprietăți

Distribuție

Există infinit de pseudoprime într-o bază dată (mai mult, există infinit de pseudoprime puternice [4] și infinit de numere Carmichael [5] ), dar sunt destul de rare [6] . Există doar trei pseudoprime Fermat de bază 2 mai puțin de 1000, 245 mai puțin de un milion și doar 21853 mai puțin de 25 de miliarde [4] .

Tabele cu unele pseudoprime Fermat

Cel mai mic pseudosimplu al lui Fermat

Cele mai mici pseudosimple Fermat pentru fiecare bază a ≤ 200 sunt date în tabelul de mai jos; culorile disting numerele după numărul de divizori primi diferiți [7] .

Cel mai mic pseudosimplu al lui Fermat
A	Cel mai mic p-pF	A	Cel mai mic p-pF	A	Cel mai mic p-pF	A	Cel mai mic p-pF
unu	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
patru	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
opt	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
zece	33 = 3 11	60	341 = 11 31	110	111 = 3 37	160	161 = 7 23
unsprezece	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
paisprezece	15 = 3 5	64	65 = 5 13	114	115 = 5 23	164	165 = 3 5 11
cincisprezece	341 = 11 13	65	112 = 2⁴ 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
optsprezece	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
douăzeci	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
treizeci	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²
cincizeci	51 = 3 17	100	153 = 3² 17	150	169 = 13²	200	201 = 3 67

Numerele Poole

Pseudosimplele Fermat la baza 2 se numesc numere Poulet , după matematicianul belgian Paul Poulet [8] . Factorizarea celor șaizeci și unu de numere Poolet, inclusiv cele treisprezece numere Carmichael (evidențiate cu aldine), se află în tabelul de mai jos.

Numerele 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

Numărul Poole, a cărui toți divizorii d împart și numărul 2 d − 2, se numește super număr Poole . Există infinit de multe numere Poulet care nu sunt numere super-Poulet [9] .

Primele pseudoprime ale lui Fermat (până la 10000) se bazează pe a

Primele pseudoprime ale lui Fermat (până la 10000) în baza a
A	Pseudoprime Fermat (până la 10.000)	Secvența OEIS (linkul este extern)
unu	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, … ( toate numerele compuse)	A002808
2	341 561 645 1105 1387 1729 1905 2047 2465 2701 2821 3277 4033 4369 4371 4681 5461 6601 7957 8321 83218	A001567
3	91 121 286 671 703 949 1105 1541 1729 1891 2465 2665 2701 2821 3281 3367 3751 4961 5551 6601 731	A005935
patru	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, 8913, 891, 891	A005936
6	35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3913, 813, 3913, 813, 3913, 813, 3913, 3913, 813, 3913, 813, 913, 817	A005937
7	6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321	A005938
opt	9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949, 1801, 1801, 1801, 1801, 180, 180 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, 9263, 97, 97, 97, 94	A020137
9	4, 8, 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949. 2501, 2665, 2701, 2806, 2821, 2926, 3052, 3281, 3367, 3751, 4376, 4636, 4961, 5356, 5551, 6364, 6601, 6643, 7081, 7381, 7913, 8401, 8695, 874 8911	A020138
zece	9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981. , 7777, 8149, 8401, 8911	A005939
unsprezece	10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257, 2465, 2821, 645, 703, 793, 1105, 1330. , 9730	A020139
12	65, 91, 133, 143, 145, 247, 377, 385, 703, 1045, 1099, 1105, 1649, 1729, 1885, 1891, 2041, 2261, 2041, 2263, 5, 5, 2, 3, 5, 2, 3 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, 5028, 5028, 5028, 561, 561, 5028, 5028, 615, 5028, 5028, 515, 5028, 5028, 515, 5028, 5028, 615, 5028, 5028, 5028, 515, 5028, 515 , 9577, 9637	A020141
paisprezece	15, 39, 65, 195, 481, 561, 781, 793, 841, 985, 1105, 1111, 1541, 1891, 2257, 2465, 2561, 2665, 2561, 2665, 71, 5, 71, 5, 71, 5, 71, 5, 71, 5, 71, 5, 7 7449, 7543, 7585, 8321, 9073	A020142
cincisprezece	14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8971, 8971,	A020143
16	15, 51, 85, 91, 255, 341, 435, 451, 561, 595, 645, 703, 1105, 1247, 1261, 1271, 1285, 1387, 1285, 1387, 1587, 1587, 168, 91, 168, 91, 168, 91, 91, 1247, 1261, 1271 , 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	A020144
17	4, 8, 9, 16, 45, 91, 145, 261, 781, 1111, 1228, 1305, 1729, 1885, 2149, 2821, 3991, 4005, 4037, 637, 63, 61, 6, 7, 6, 7, 8 , 8481, 8911	A020145
optsprezece	25, 49, 65, 85, 133, 221, 323, 325, 343, 425, 451, 637, 931, 1105, 1225, 1369, 1387, 1649, 1729, 1729, 2929, 2929, 2929, 2929 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, 1661, 1849, 1849, 1891, 205, 205, 205, 205, 205, 2035, 1105, 1629 , 4033, 4681, 5461, 5466, 5713, 6223, 6541, 6601, 6697, 7957, 8145, 8281, 8401, 8869, 9211, 9997	A020147
douăzeci	21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501, 2761, 2501, 2761, 2841, 701, 701, 701, 701, 701, 701, 701, 701, 701, 701, 701, 701, 570, 701, 570 , 6817, 7999, 8421, 8911	A020148
21	4, 10, 20, 55, 65, 85, 221, 703, 793, 1045, 1105, 1852, 2035, 2465, 3781, 4630, 5185, 5473, 5185, 5473, 5945, 639, 69, 6, 9, 6	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, 710 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, 1065, 1105, 1065, 1105, 1065, 1105, 1065, 1105, 1105, 1105, 1181, 712, 712, 712, 1027 2465, 2501, 2701, 2821, 2926, 3097, 3445, 4033, 4081, 4345, 4371, 4681, 5005, 5149, 6253, 6369, 6533, 6541, 7189, 7267, 7957, 8321, 8365, 865 8911, 8965, 9805	A020151
24	25, 115, 175, 325, 553, 575, 805, 949, 1105, 1541, 1729, 1771, 1825, 1975, 2413, 2425, 2465, 2105, 1541, 1729, 1771, 1825, 1975, 2413, 2425, 2465, 2425, 2465, 2105, 2105, 273, 60, 27, 81, 6, 8, 8 , 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, 6, 8, 8, 8, 8, 8, 8, 8 1288, 1541, 1729, 1891, 2047. 5662, 5731, 5963, 6601, 7449, 7588, 7813, 8029, 8646, 8911, 9881, 9876,	A020153
26	9, 15, 25, 27, 45, 75, 133, 135, 153, 175, 217, 225, 259, 425, 475, 561, 589, 675, 703, 775. 3145, 3325, 3385, 3565, 3825, 4123, 4525, 4741, 4921, 5041, 5425, 6093, 6475, 6525, 6601, 6695, 8697, 8697, 8697	A020154
27	26, 65, 91, 121, 133, 247, 259, 286, 341, 365, 481, 671, 703, 949, 1001, 1105, 1541, 1649, 1791. 2993, 3146, 3281, 3367, 3605, 3751, 4033, 4745, 4921, 4961, 5299, 5461, 5551, 5611, 5621, 6305, 6533, 6601, 7381, 7585, 7957, 8227, 8321, 840 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, 2415, 2041, 2415, 2041, 2415, 2041, 2415, 2415, 2415, 2415, 2415, 2415, 2415 , 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, 1872, 187, 2, 187, 2, 1 2821, 3484, 3523, 4069, 4371, 4411, 5149, 5185, 5356, 5473, 5565, 5611, 6097, 6601, 7161, 7291, 841, 841, 84, 84, 84	A020157
treizeci	49, 91, 133, 217, 247, 341, 403, 469, 493, 589, 637, 703, 871, 899, 901, 931, 1273, 1519, 1519, 1519, 1519, 1519, 1519, 1519, 1519, 1519, 1519, 1519, 1519, 1519, 1519, 1519, 1519, 1519, 1519, 1519, 1519 , 3367, 3577, 4081, 4097, 4123, 5729, 6031, 6061, 6097, 6409, 6601, 6817, 7657, 8023, 8029, 8411, 8029, 8411,	A020158

Pentru mai multe informații despre pseudoprimele Fermat la bazele 31 - 100, vezi articolele A020159 - A020228 din Encyclopedia of Integer Sequences [10] .

Motive pentru care un număr este pseudoprim

Mai jos este un tabel cu toate bazele b < n pentru care n este un pseudoprim Fermat (toate numerele compuse sunt pseudoprime în baza 1, iar pentru b > n soluția este pur și simplu deplasată cu k * n , unde k > 0) dacă compusul numărul n nu este indicat în tabel, atunci este pseudoprim doar în baza 1, sau în baze care sunt comparabile cu 1 (mod n ), adică numărul bazelor b este 1. Tabelul este întocmit pentru n < 180 [11] .

Bazele b pentru care n este pseudoprim
n	Bazele b pentru care n este pseudosimplu Fermat(< n )	Număr de baze b (< n ) [12]
9	optsprezece	2
cincisprezece	1, 4, 11, 14	patru
21	1, 8, 13, 20	patru
25	1, 7, 18, 24	patru
27	1, 26	2
28	1, 9, 25	3
33	1, 10, 23, 32	patru
35	1, 6, 29, 34	patru
39	1, 14, 25, 38	patru
45	1, 8, 17, 19, 26, 28, 37, 44	opt
49	1, 18, 19, 30, 31, 48	6
51	1, 16, 35, 50	patru
52	1, 9, 29	3
55	1, 21, 34, 54	patru
57	1, 20, 37, 56	patru
63	1, 8, 55, 62	patru
65	1, 8, 12, 14, 18, 21, 27, 31, 34, 38, 44, 47, 51, 53, 57, 64	16
66	1, 25, 31, 37, 49	5
69	1, 22, 47, 68	patru
70	1, 11, 51	3
75	1, 26, 49, 74	patru
76	1, 45, 49	3
77	1, 34, 43, 76	patru
81	1,80	2
85	1, 4, 13, 16, 18, 21, 33, 38, 47, 52, 64, 67, 69, 72, 81, 84	16
87	1, 28, 59, 86	patru
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	patru
95	1, 39, 56, 94	patru
99	1, 10, 89, 98	patru
105	1, 8, 13, 22, 29, 34, 41, 43, 62, 64, 71, 76, 83, 92, 97, 104	16
111	1, 38, 73, 110	patru
112	1, 65, 81	3
115	1, 24, 91, 114	patru
117	1, 8, 44, 53, 64, 73, 109, 116	opt
119	1, 50, 69, 118	patru
121	1, 3, 9, 27, 40, 81, 94, 112, 118, 120	zece
123	1, 40, 83, 122	patru
124	1, 5, 25	3
125	1, 57, 68, 124	patru
129	1, 44, 85, 128	patru
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	patru
141	1, 46, 95, 140	patru
143	1, 12, 131, 142	patru
145	1, 12, 17, 28, 41, 46, 57, 59, 86, 88, 99, 104, 117, 128, 133, 144	16
147	1, 50, 97, 146	patru
148	1, 121, 137	3
153	1, 8, 19, 26, 35, 53, 55, 64, 89, 98, 100, 118, 127, 134, 145, 152	16
154	1, 23, 67	3
155	1, 61, 94, 154	patru
159	1, 52, 107, 158	patru
161	1, 22, 139, 160	patru
165	1, 23, 32, 34, 43, 56, 67, 76, 89, 98, 109, 122, 131, 133, 142, 164	16
169	1, 19, 22, 23, 70, 80, 89, 99, 146, 147, 150, 168	12
171	1, 37, 134, 170	patru
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	patru

Trebuie remarcat că dacă p este prim, atunci p 2 este pseudoprimul lui Fermat la baza b dacă și numai dacă p este un prim Wieferich la baza b . De exemplu, 1093 2 = 1 194 649 este baza pseudosimplu 2 a lui Fermat.

Numărul de baze b pentru n (pentru prim n , numărul de baze b trebuie să fie egal cu n-1 , deoarece toate b satisfac mica teoremă a lui 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, … (secvența A063994 în OEIS )

Cea mai mică bază b > 1 pentru care n este pseudoprim (sau prim):

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, … (secvența A105222 în OEIS ).

Pseudosimplu slab

Un număr compus n care satisface comparația b n = b (mod n ) se numește pseudoprim slab Fermat față de baza b (aici b nu trebuie să fie coprim cu n ) [13] . Cele mai mici pseudoprime slabe la baza b sunt:

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, … (secvența A000790 în OEIS )

Dacă se cere ca n > b , atunci:

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, 56, 56 … (secvența A239293 în OEIS )

Aplicații

Datorită rarității lor, astfel de pseudoprime au aplicații practice importante. De exemplu, algoritmii criptografici cu cheie publică, cum ar fi RSA , necesită capacitatea de a găsi rapid numere prime mari [14] . Algoritmul obișnuit pentru generarea numerelor prime este de a genera numere impare aleatoare și de a le testa pentru prim . Cu toate acestea, testele de primalitate deterministă sunt lente. Dacă suntem dispuși să acceptăm o probabilitate arbitrar mică ca numărul găsit să nu fie prim, ci pseudoprim, se poate folosi un test Fermat mult mai rapid și mai simplu .

Note

↑ Desmedt, Yvo. Scheme de criptare // Manual de algoritmi și teoria calculului: subiecte și tehnici speciale (engleză) / Atallah, Mikhail J.și Blanton, Marina. - CRC Press , 2010. - P. 10-23. — ISBN 978-1-58488-820-8 .
^ Weisstein, Eric W. Fermat Pseudoprime pe site- ul Wolfram MathWorld .
↑ Crandall, Pomerance, 2011 , p. 155.
↑ 1 2 Pomerance, Selfridge, Wagstaff 1980 , Teorema 1.
↑ W. R. Alford ; Andrew Granville ; Carl Pomerance . Există infinit de multe numere Carmichael // Analele matematicii : jurnal . - 1994. - Vol. 139 . - P. 703-722 . - doi : 10.2307/2118576 .
↑ Crandall, Pomerance, 2011 , Teorema 3.4.2, p. 154-155.
↑ Secvența OEIS A007535 _
↑ Secvența OEIS A001567 _
↑ W. Sierpinski. Capitolul V.7 // Teoria elementară a numerelor = Teoria Liczb / Ed. A. Schinzel. - 2 subediții. - Amsterdam: Olanda de Nord, 15-02-1988. - S. 232. - 528 p. — (Biblioteca de matematică din Olanda de Nord). — ISBN 9780444866622 . Arhivat pe 8 decembrie 2015 la Wayback Machine
↑ Vezi și tabelul lui Fermat de pseudoprime pentru baze până la 150 (germană) ; aici n nu este definit ca fiind pseudoprim în baze comparabile cu 1 sau -1 (mod n ).
↑ Informații mai detaliate pentru n = 181 ... 5000 sunt în tabel (germană) ; aici n nu este definit ca fiind pseudoprim în baze comparabile cu 1 sau -1 (mod n ).
↑ Secvența OEIS A063994 _
↑ Crandall, Pomerance, 2011 , Teorema 3.4.1, p. 154.
↑ Crandall, Pomerance, 2011 , Algoritmul 8.1.2, p. 438.

Literatură

Richard Crandall, Carl Pomerance. Numerele prime: aspecte criptografice și computaționale. - Casa de carte „LIBROKOM”, 2011. - P. 154-158, 438-441.
Carl Pomerance ; John L. Selfridge , Samuel S. Wagstaff, Jr Pseudoprimele la 25 10 9 // Matematica calculului : jurnal. - 1980. - iulie ( vol. 35 , nr. 151 ). - P. 1003-1026 . - doi : 10.1090/S0025-5718-1980-0572872-7 .