Pseudoprimes Fermat

Fermats pseudoprimtal är sammansatta tal som klarar Fermat-testet . Uppkallad efter den franske matematikern Pierre de Fermat . I talteorin utgör Fermats pseudoprimer den viktigaste klassen av pseudoprimer .

Definition

Pseudoprimer

Ett sammansatt tal kallas pseudoprimtal om det uppfyller något nödvändigt (men inte tillräckligt ) villkor för att talet ska vara primtal, det vill säga om det har vissa egenskaper hos ett primtal .

Fermats lilla sats

Fermats lilla sats säger att om n är ett primtal, så gäller kongruensen för varje tal ett samprimtal till n . $a^{n-1} \equiv 1 \pmod n$

Pseudosimple Farms

Ett sammansatt nummer n kallas ett Fermat-pseudoprime i bas a (samprime till n ) om jämförelse görs . Med andra ord, ett sammansatt tal sägs vara pseudoprime om det klarar Fermat-testet för att basera en [1] . Ett tal som är Fermats pseudoprimtal i varje coprime-bas kallas ett Carmichael-tal . $a^{n-1} \equiv 1 \pmod n$

Variationer

Det finns några varianter av definitionen:

Vissa källor kräver att pseudoprimtal är udda [2] , eftersom ett jämnt tal uppenbarligen är sammansatt.
Varje udda nummer uppfyller för , så i det här fallet får vi ingen ny information om numret. Detta är uteslutet i definitionen som ges av Crandall och Pomerance [3] : Ett sammansatt tal är ett Fermat-pseudoprimtal till basen om och $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.$

Egenskaper

Distribution

Det finns oändligt många pseudoprimer i en given bas (desutom finns det oändligt många starka pseudoprimer [4] och oändligt många Carmichael-tal [5] ), men de är ganska sällsynta [6] . Det finns bara tre bas-2 Fermat-pseudoprimer mindre än 1000, 245 mindre än en miljon och endast 21853 mindre än 25 miljarder [4] .

Tabeller med några Fermat-pseudoprimer

Fermats minsta pseudosimple

De minsta Fermat-pseudosimplarna för varje bas a ≤ 200 anges i tabellen nedan; färger särskiljer tal genom antalet olika primtalsdelare [7] .

Fermats minsta pseudosimple
a	Minsta p-pF	a	Minsta p-pF	a	Minsta p-pF	a	Minsta p-pF
ett	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
fyra	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
åtta	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
tio	33 = 3 11	60	341 = 11 31	110	111 = 3 37	160	161 = 7 23
elva	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
fjorton	15 = 3 5	64	65 = 5 13	114	115 = 5 23	164	165 = 3 5 11
femton	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
arton	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
tjugo	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
trettio	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²
femtio	51 = 3 17	100	153 = 3² 17	150	169 = 13²	200	201 = 3 67

Poole nummer

Fermat pseudosimples till bas 2 kallas Poulet-tal , efter den belgiske matematikern Paul Poulet [8] . Faktoriseringen av de sextioförsta Poolet-talen, inklusive de tretton Carmichael-talen (markerade med fet stil), finns i tabellen nedan.

Poole siffror
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-talet, där alla divisorer d också delar talet 2 d − 2, kallas super Poole- talet . Det finns oändligt många Poulet-nummer som inte är super-Poulet-nummer [9] .

Fermats första pseudoprimer (upp till 10000) baserar en

Fermats första pseudoprimer (upp till 10000) i bas a
a	Fermat pseudoprimer (upp till 10 000)	OEIS-sekvens (länk är extern)
ett	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, 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, … alla sammansatta 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
fyra	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, 819, 8113, 89	A005936
6	35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3923, 3, 3, 4, 3, 3, 4	A005937
7	6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321	A005938
åtta	9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861. 1417, 1541, 1649, 1661, 1729, 1785, 1905, 2047, 2169, 2465, 2501, 2701, 2821, 3145, 3171, 3201, 3277, 3605, 3641, 4005, 4033, 4097, 4369, 437, 4641. 4681, 4921, 5461, 5565, 5963, 6305, 6533, 6601, 6951, 7107, 7161, 7957, 8321, 8481.	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, 8744, 8866, 8911	A020138
tio	9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333. , 7777, 8149, 8401, 8911	A005939
elva	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. 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
fjorton	15, 39, 65, 195, 481, 561, 781, 793, 841, 985, 1105, 1111, 1541, 1891, 2257. 7449, 7543, 7585, 8321, 9073	A020142
femton	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, 6601, 6643, 7471, 7735, 7735, 7735 , 7735, 7735, 7735. 7957, 8119, 8227, 8245, 8321, 8481, 8695, 8749, 8911, 9061, 9131, 9211, 9605, 9105,	A020144
17	4, 8, 9, 16, 45, 91, 145, 261, 781, 1111, 1228, 1305, 1729, 1885, 2149, 2821, 3991. , 8481, 8911	A020145
arton	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
tjugo	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, 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. 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. , 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,84 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, 6601, 60297, 81, 60297, 81, 81	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, 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,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, 176 2821, 3484, 3523, 4069, 4371, 4411, 5149, 5185, 5356, 5473, 5565, 5611, 6097, 6601.	A020157
trettio	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, 8401, 8401, 8401	A020158

För mer information om Fermats pseudoprimer till baserna 31 - 100, se artiklarna A020159 - A020228 i Encyclopedia of Integer Sequences [10] .

Orsaker till att ett tal är pseudoprime

Nedan finns en tabell över alla baser b < n för vilka n är ett Fermat-pseudoprimtal (alla sammansatta tal är pseudoprimtal i bas 1, och för b > n skiftas lösningen helt enkelt med k * n , där k > 0) om den sammansatta nummer n anges inte i tabellen, då är det pseudoprime bara i bas 1, eller i baser som är jämförbara med 1 (mod n ), det vill säga antalet baser b är 1. Tabellen är sammanställd för n < 180 [11] .

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

Det bör noteras att om p är primtal så är p 2 Fermats pseudoprim till bas b om och endast om p är ett Wieferich primtal till bas b . Till exempel är 1093 2 = 1 194 649 Fermats pseudoenkla bas 2.

Antalet baser b för n (för primtal n måste antalet baser b vara lika med n-1 , eftersom alla b uppfyller Fermats lilla teorem ):

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 minsta basen b > 1 för vilken n är 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 pseudoenkel

Ett sammansatt tal n som uppfyller jämförelsen b n = b (mod n ) kallas en svag Fermat-pseudoprim till bas b (här behöver b inte vara coprime till n ) [13] . De minsta svaga pseudoprimerna till bas b är:

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 )

Om det krävs att n > b , då:

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 )

Applikationer

På grund av deras sällsynthet har sådana pseudoprimer viktiga praktiska tillämpningar. Till exempel kräver public-key kryptografiska algoritmer som RSA förmågan att snabbt hitta stora primtal [14] . Den vanliga algoritmen för att generera primtal är att generera slumpmässiga udda tal och testa dem för primitet . Men deterministiska primatitetstester är långsamma. Om vi är villiga att acceptera en godtyckligt liten sannolikhet att talet som hittas inte är primtal, utan pseudoprimtal, kan ett mycket snabbare och enklare Fermats test användas .

Anteckningar

↑ Desmedt, Yvo. Krypteringsscheman // Handbok för algoritmer och beräkningsteori: Särskilda ämnen och tekniker (engelska) / Atallah, Mikhail J.& Blanton, Marina. - CRC Press , 2010. - S. 10-23. — ISBN 978-1-58488-820-8 .
↑ Weisstein, Eric W. Fermat Pseudoprime på Wolfram MathWorld- webbplatsen .
↑ Crandall, Pomerance, 2011 , sid. 155.
↑ 1 2 Pomerance, Selfridge, Wagstaff 1980 , sats 1.
↑ W. R. Alford ; Andrew Granville ; Carl Pomerance . Det finns oändligt många Carmichael Numbers // Annals of Mathematics : journal . - 1994. - Vol. 139 . - s. 703-722 . - doi : 10.2307/2118576 .
↑ Crandall, Pomerance, 2011 , sats 3.4.2, sid. 154-155.
↑ OEIS - sekvens A007535 _
↑ OEIS - sekvens A001567 _
↑ W. Sierpinski. Kapitel V.7 // Elementär talteori = Teoria Liczb / Ed. A. Schinzel. - 2 underupplagor. - Amsterdam: North Holland, 1988-02-15. - S. 232. - 528 sid. — (North-Holland Mathematical Library). — ISBN 9780444866622 . Arkiverad 8 december 2015 på Wayback Machine
↑ Se även Fermats tabell över pseudoprimer för baser upp till 150 (tyska) ; här definieras n inte som pseudoprim i baser jämförbara med 1 eller -1 (mod n ).
↑ Mer detaljerad information för n = 181 ... 5000 finns i tabellen (tyska) ; här definieras n inte som pseudoprim i baser jämförbara med 1 eller -1 (mod n ).
↑ OEIS - sekvens A063994 _
↑ Crandall, Pomerance, 2011 , sats 3.4.1, sid. 154.
↑ Crandall, Pomerance, 2011 , Algorithm 8.1.2, sid. 438.

Litteratur

Richard Crandall, Carl Pomerance. Primtal: Kryptografiska och beräkningsaspekter. - Bokhuset "LIBROKOM", 2011. - S. 154-158, 438-441.
Carl Pomerance ; John L. Selfridge , Samuel S. Wagstaff, Jr Pseudoprimerna till 25 10 9 // Mathematics of Computing : journal. - 1980. - Juli ( vol. 35 , nr 151 ). - P. 1003-1026 . - doi : 10.1090/S0025-5718-1980-0572872-7 .