Pseudoprimes Fermat

Fermats pseudoprimtal er sammensatte tal , der består Fermat-testen . Opkaldt efter den franske matematiker Pierre de Fermat . I talteorien udgør Fermats pseudoprimer den vigtigste klasse af pseudoprimer .

Definition

Pseudoprimer

Et sammensat tal kaldes pseudoprimtal , hvis det opfylder en nødvendig (men ikke tilstrækkelig ) betingelse for, at tallet er primtal, det vil sige, hvis det har nogle egenskaber af et primtal .

Fermats lille sætning

Fermats lille sætning siger, at hvis n er et primtal, så gælder kongruensen for hvert tal en coprime til n .

Pseudosimple Farms

Et sammensat tal n kaldes et Fermat-pseudoprime i base a (coprime til n ), hvis sammenligning foretages . Med andre ord siges et sammensat tal at være pseudoprime, hvis det består Fermat-testen for at basere et [1] . Et tal, der er Fermats pseudoprime i hver coprime-base, kaldes et Carmichael-tal .

Variationer

Der er nogle variationer af definitionen:

• Nogle kilder kræver, at pseudoprimtallet er ulige [2] , da et lige tal åbenbart er sammensat.
• Hvert ulige tal opfylder for , så i dette tilfælde vil vi ikke få nye oplysninger om tallet. Dette er udelukket i definitionen givet af Crandall og Pomerance [3] : Et sammensat tal er et Fermat-pseudoprimtal til basen, hvis og

Egenskaber

Fordeling

Der er uendeligt mange pseudoprimer i en given base (derudover er der uendeligt mange stærke pseudoprimer [4] og uendeligt mange Carmichael-tal [5] ), men de er ret sjældne [6] . Der er kun tre base-2 Fermat pseudoprimer mindre end 1000, 245 mindre end en million og kun 21853 mindre end 25 milliarder [4] .

Tabeller med nogle Fermat-pseudoprimer

Fermats mindste pseudosimple

De mindste Fermat-pseudosimple for hver base a ≤ 200 er angivet i tabellen nedenfor; farver skelner tal ved antallet af forskellige primdivisorer [7] .

Fermats mindste pseudosimple
-en	Mindste p-pF	-en	Mindste p-pF	-en	Mindste p-pF	-en	Mindste p-pF
en	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
fire	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
otte	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
ti	33 = 3 11	60	341 = 11 31	110	111 = 3 37	160	161 = 7 23
elleve	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
fjorten	15 = 3 5	64	65 = 5 13	114	115 = 5 23	164	165 = 3 5 11
femten	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
atten	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
tyve	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
tredive	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²
halvtreds	51 = 3 17	100	153 = 3² 17	150	169 = 13²	200	201 = 3 67

Poole tal

Fermat pseudosimple til base 2 kaldes Poulet-tal , efter den belgiske matematiker Paul Poulet [8] . Faktoriseringen af ​​de enogtresindstyve Poolet-tal, inklusive de tretten Carmichael-tal (fremhævet med fed), er i tabellen nedenfor.

Poole numre
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

Poole-tallet, hvor alle divisorer d også deler tallet 2 d − 2, kaldes super Poole -tallet . Der er uendeligt mange Poulet-numre, der ikke er super-Poulet-numre [9] .

Fermats første pseudoprimer (op til 10000) baserer en

Fermats første pseudoprimer (op til 10.000) i base a
-en	Fermat pseudoprimer (op til 10.000)	OEIS-sekvens (link er eksternt)
en	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, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, ( 100, … alle sammensatte tal)	A002808
2	341 561 645 1105 1387 1729 1905 2047 2465 2701 2821 3277 4033 4369 4371 4681 5461 6601 7957 83218	A001567
3	91 121 286 671 703 949 1105 1541 1729 1891 2465 2665 2701 2821 3281 3367 3751 4961 5551 6601 401	A005935
fire	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, 7819, 81	A005936
6	35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3913, 3, 3, 3, 4, 3, 4	A005937
7	6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321	A005938
otte	9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651. 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, 7069, 9,91, 7069, 91	A020137
9	4, 8, 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036. 2501, 2665, 2701, 2806, 2821, 2926, 3052, 3281, 3367, 3751, 4376, 4636, 4961, 5356, 5551, 6364, 6601, 6643, 7081, 7381, 7913, 8401, 8695, 874444, 886, 886, 886, 886, 886, 886, 796, 7913, 8401, 8695544444, 886, 886666666666666666666666666666666666666666666666666666666666666666666666666666666662 8911	A020138
ti	9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333. , 7777, 8149, 8401, 8911	A005939
elleve	10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257. , 9730	A020139
12	65, 91, 133, 143, 145, 247, 377, 385, 703, 1045, 1099, 1105, 1649, 1729, 1885, 1891. 5785, 6061, 6305, 6601, 8911, 9073	A020140
13	4, 6, 12, 21, 85, 105, 231, 244, 276, 357, 427, 561, 1099, 1785, 1891, 2465. , 9577, 9637	A020141
fjorten	15, 39, 65, 195, 481, 561, 781, 793, 841, 985, 1105, 1111, 1541, 1891, 2257. 7449, 7543, 7585, 8321, 9073	A020142
femten	14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7401, 7401, 0	A020143
16	15, 51, 85, 91, 255, 341, 435, 451, 561, 595, 645, 703, 1105, 1247, 1261, 1271, 1285. , 2431, 2465, 2701, 2821, 3133, 3277, 3367, 3655, 3683, 4033, 4369, 4371, 4681, 4795, 4859, 5083, 5151, 5461, 5551, 662 , 7735, 7735, 7735. 7957, 8119, 8227, 8245, 8321, 8481, 8695, 8749, 8911, 9061, 9131, 9211, 9105, 9105,	A020144
17	4, 8, 9, 16, 45, 91, 145, 261, 781, 1111, 1228, 1305, 1729, 1885, 2149, 2821, 3991. , 8481, 8911	A020145
atten	25, 49, 65, 85, 133, 221, 323, 325, 343, 425, 451, 637, 931, 1105, 1225, 1369, 1387. 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. , 4033, 4681, 5461, 5466, 5713, 6223, 6541, 6601, 6697, 7957, 8145, 8281, 8401, 8869, 9211, 9997	A020147
tyve	21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501. , 6817, 7999, 8421, 8911	A020148
21	4, 10, 20, 55, 65, 85, 221, 703, 793, 1045, 1105, 1852, 2035, 2465, 3781, 4630, 5185.	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, 667 7665, 8119, 8365, 8421, 8911, 9453	A020150
23	22, 33, 91, 154, 165, 169, 265, 341, 385, 451, 481, 553, 561, 638, 946, 1027. 2465, 2501, 2701, 2821, 2926, 3097, 3445, 4033, 4081, 4345, 4371, 4681, 5005, 5149, 6253, 6369, 6533, 6541, 7189, 7267, 7957, 8321, 83655, 8651, 874 8911, 8965, 9805	A020151
24	25, 115, 175, 325, 553, 575, 805, 949, 1105, 1541, 1729, 1771, 1825, 1975, 2413, 2425. , 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, 81, 8, 8, 8, 81 1288, 1541, 1729, 1891, 2047. 5662, 5731, 5963, 6601, 7449, 7588, 7813, 8029, 8646, 8911, 9876, 9	A020153
26	9, 15, 25, 27, 45, 75, 133, 135, 153, 175, 217, 225, 259, 425, 475, 561, 589, 675, 703. 3145, 3325, 3385, 3565, 3825, 4123, 4525, 4741, 4921, 5041, 5425, 6093, 6475, 6525.	A020154
27	26, 65, 91, 121, 133, 247, 259, 286, 341, 365, 481, 671, 703, 949, 1001, 1105, 1541. 2993, 3146, 3281, 3367, 3605, 3751, 4033, 4745, 4921, 4961, 5299, 5461, 5551, 5611, 5621, 6305, 6533, 6601, 7381, 7585, 7957, 8227, 8321 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,1 , 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, 172, 172, 176 2821, 3484, 3523, 4069, 4371, 4411, 5149, 5185, 5356, 5473, 5565, 5611, 6097.	A020157
tredive	49, 91, 133, 217, 247, 341, 403, 469, 493, 589, 637, 703, 871, 899, 901, 931, 1273. , 3367, 3577, 4081, 4097, 4123, 5729, 6031, 6061, 6097, 6409, 6601, 6817, 7657, 8023, 8029, 8111, 8111	A020158

For mere information om Fermat-pseudoprimer til baserne 31 - 100, se artiklerne A020159 - A020228 i Encyclopedia of Integer Sequences [10] .

Årsager til, at et tal er pseudoprime

Nedenfor er en tabel over alle baser b < n , for hvilke n er et Fermat-pseudoprimtal (alle sammensatte tal er pseudoprimtal i grundtal 1, og for b > n forskydes løsningen blot med k * n , hvor k > 0), hvis den sammensatte nummer n er ikke angivet i tabellen, så er det kun pseudoprime i base 1, eller i baser, der er sammenlignelige med 1 (mod n ), det vil sige antallet af baser b er 1. Tabellen er kompileret for n < 180 [11] .

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

Det skal bemærkes, at hvis p er primtal, så er p2 Fermats pseudoprime til base b , hvis og kun hvis p er en Wieferich prime til base b . For eksempel er 1093 2 = 1 194 649 Fermats pseudosimple base 2.

Antallet af baser b for n (for primtal n skal antallet af baser b være lig med n-1 , da alle b opfylder Fermats lille sætning ):

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, … (sekvens A063994 i OEIS )

Den mindste base b > 1, for hvilken n er pseudoprime (eller prime):

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, … (sekvens A105222 i OEIS ).

Svag pseudosimple

Et sammensat tal n , der opfylder sammenligningen b n = b (mod n ), kaldes et svagt Fermat-pseudoprimtal til base b (her behøver b ikke at være coprime til n ) [13] . De mindste svage pseudoprimer til base b er:

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, … (sekvens A000790 i OEIS )

Hvis det kræves, at n > b , så:

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, … (sekvens A239293 i OEIS )

Ansøgninger

På grund af deres sjældenhed har sådanne pseudoprimer vigtige praktiske anvendelser. For eksempel kræver public-key kryptografiske algoritmer såsom RSA evnen til hurtigt at finde store primtal [14] . Den sædvanlige algoritme til at generere primtal er at generere tilfældige ulige tal og teste dem for primehed . Deterministiske primalitetstests er dog langsomme. Hvis vi er villige til at acceptere en vilkårligt lille sandsynlighed for, at det fundne tal ikke er primtal, men pseudoprimtal, kan en meget hurtigere og enklere Fermats test bruges .

Noter

1. ↑ Desmedt, Yvo. Krypteringsskemaer // Algoritmer og beregningsteorihåndbog: Særlige emner og teknikker  (engelsk) / Atallah, Mikhail J.& Blanton, Marina. - CRC Press , 2010. - S. 10-23. — ISBN 978-1-58488-820-8 .
2. ↑ Weisstein, Eric W. Fermat Pseudoprime  på Wolfram MathWorld -webstedet .
3. ↑ Crandall, Pomerance, 2011 , s. 155.
4. ↑ 1 2 Pomerance, Selfridge, Wagstaff 1980 , sætning 1.
5. ↑ W. R. Alford ; Andrew Granville ; Carl Pomerance . Der er uendeligt mange Carmichael-numre  // Annals of Mathematics  : journal  . - 1994. - Bd. 139 . - s. 703-722 . - doi : 10.2307/2118576 .
6. ↑ Crandall, Pomerance, 2011 , sætning 3.4.2, s. 154-155.
7. ↑ OEIS -sekvens A007535 _
8. ↑ OEIS -sekvens A001567 _
9. ↑ W. Sierpinski. Kapitel V.7 // Elementær Talteori = Teoria Liczb / Udg. A. Schinzel. - 2 underudgaver. - Amsterdam: Nordholland, 1988-02-15. - S. 232. - 528 s. — (Nordhollands matematiske bibliotek). — ISBN 97804444866622 . Arkiveret 8. december 2015 på Wayback Machine
10. ↑ Se også Fermats tabel over pseudoprimer for baser op til 150  (tysk) ; her er n ikke defineret til at være pseudoprime i baser, der er sammenlignelige med 1 eller -1 (mod n ).
11. ↑ Mere detaljerede oplysninger for n = 181 ... 5000 er i tabellen  (tysk) ; her er n ikke defineret til at være pseudoprime i baser, der er sammenlignelige med 1 eller -1 (mod n ).
12. ↑ OEIS -sekvens A063994 _
13. ↑ Crandall, Pomerance, 2011 , sætning 3.4.1, s. 154.
14. ↑ Crandall, Pomerance, 2011 , Algorithm 8.1.2, s. 438.

Litteratur

• Richard Crandall, Carl Pomerance. Primtal: Kryptografiske og beregningsmæssige aspekter. - Boghuset "LIBROKOM", 2011. - S. 154-158, 438-441.
• Carl Pomerance ; John L. Selfridge , Samuel S. Wagstaff, Jr  Pseudoprimerne til 25 10 9  // Mathematics of Computation : journal. - 1980. - Juli ( bind 35 , nr. 151 ). - S. 1003-1026 . - doi : 10.1090/S0025-5718-1980-0572872-7 .