Pseudoprimes Fermat

Fermatova pseudoprvočísla jsou složená čísla , která projdou Fermatovým testem . Pojmenován po francouzském matematikovi Pierre de Fermat . V teorii čísel představují Fermatova pseudoprimes nejdůležitější třídu pseudoprimes .

Definice

Pseudoprimes

Složené číslo se nazývá pseudoprvočíslo , pokud splňuje nějakou nezbytnou (ale ne postačující ) podmínku , aby bylo číslo prvočíslo, tedy pokud má nějaké vlastnosti prvočísla .

Fermatova malá věta

Fermatova Malá věta říká, že je-li n prvočíslo, pak pro každé číslo sdružené s n platí kongruence . $a^{n-1} \equiv 1 \pmod n$

Pseudosimple Farms

Složené číslo n se nazývá Fermatovo pseudoprvo v základu a (coprime až n ), pokud je provedeno srovnání . Jinými slovy, složené číslo je považováno za pseudoprvočíslo, pokud projde Fermatovým testem na základ a [1] . Číslo, které je Fermatovo pseudoprvo v každém koprimém základu, se nazývá Carmichaelovo číslo . $a^{n-1} \equiv 1 \pmod n$

Variace

Existuje několik variant definice:

Některé zdroje vyžadují, aby pseudoprvo bylo liché [2] , protože sudé číslo je zjevně složené.
Každé liché číslo vyhovuje pro , takže v tomto případě nezískáme nové informace o čísle. To je vyloučeno v definici uvedené Crandallem a Pomerancem [3] : Složené číslo je Fermatovo pseudoprimum k základu , jestliže a $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.$

Vlastnosti

Distribuce

V daném základu je nekonečně mnoho pseudoprvot (navíc existuje nekonečně mnoho silných pseudoprvot [4] a nekonečně mnoho Carmichaelových čísel [5] ), ale jsou poměrně vzácná [6] . Existují pouze tři Fermatova pseudoprima s bází 2, méně než 1000, 245 méně než jeden milion a pouze 21853 méně než 25 miliard [4] .

Tabulky s některými Fermatovými pseudoprimes

Fermatovo nejmenší pseudojednoduché

Nejmenší Fermatova pseudojednoduchá pro každou bázi a ≤ 200 jsou uvedena v tabulce níže; barvy rozlišují čísla podle počtu různých prvočíselných dělitelů [7] .

Fermatův nejmenší pseudojednoduchý
A	Nejmenší p-pF	A	Nejmenší p-pF	A	Nejmenší p-pF	A	Nejmenší p-pF
jeden	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
čtyři	15 = 35	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
osm	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
deset	33 = 3 11	60	341 = 11 31	110	111 = 3 37	160	161 = 7 23
jedenáct	15 = 35	61	91 = 7 13	111	190 = 2 5 19	161	190 = 2 5 19
12	65 = 5 13	62	63 = 3² 7	112	121 = 112	162	481 = 13 37
13	21 = 3 7	63	341 = 11 31	113	133 = 7 19	163	186 = 2 3 31
čtrnáct	15 = 35	64	65 = 5 13	114	115 = 5 23	164	165 = 3 5 11
patnáct	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
osmnáct	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
dvacet	21 = 3 7	70	169 = 13²	120	121 = 112	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
třicet	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²
padesáti	51 = 3 17	100	153 = 3² 17	150	169 = 13²	200	201 = 3 67

Poole čísla

Fermatova pseudojednoduchá k základu 2 se nazývají Pouletova čísla , podle belgického matematika Paula Pouleta [8] . Faktorizace šedesátých prvních Pooletových čísel, včetně třinácti Carmichaelových čísel (zvýrazněných tučně), je v tabulce níže.

Pool čísla
Skupina 1–15		Skupina 16–30		Skupina 31–45		Skupina 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 číslo, jehož všichni dělitelé d také dělí číslo 2 d − 2, se nazývá supersdružené číslo . Existuje nekonečně mnoho čísel Poulet, která nejsou superčísly Poulet [9] .

Fermatova první pseudoprima (až 10000) základ a

Fermatova první pseudoprima (až 10000) v základu a
A	Fermat pseudoprimes (až 10 000)	Sekvence OEIS (odkaz je externí)
jeden	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, 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, … všechna složená čísla)	A002808
2	341 561 645 1105 1387 1729 1905 2047 2465 2701 2821 3277 4033 4369 4371 4681 5461 6601 7957 481 21	A001567
3	91 121 286 671 703 949 1105 1541 1729 1891 2465 2665 2701 2821 3281 3367 3751 4961 5551 6601 7381	A005935
čtyři	15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071. 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, 8013, 9813, 8013, 8013, 8	A005936
6	35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 41933, 38, 5 493 38	A005937
7	6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321	A005938
osm	9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 901, 51, 385, 21, 51 105 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, 95 7035, 95 7035, 9	A020137
9	4, 8, 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 111, 49, 1105, 113878, 41 2501, 2665, 2701, 2806, 2821, 2926, 3052, 3281, 3367, 3751, 4376, 4636, 4961, 5356, 5551, 8401, 8695, 8744, 8666, 8401, 8695, 8401, 8695, 8401, 8666, 8401, 8695, 8401, 8695, 8401, 86601, 8381, 7913. 8911	A020138
deset	3, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, 71 4187, 5 71 4187, 51 71 4141, 71 , 7777, 8149, 8401, 8911	A005939
jedenáct	10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257, 2465, 28721, 52 91, 81 81 , 9730	A020139
12	65, 91, 133, 143, 145, 247, 377, 385, 703, 1045, 1099, 1105, 1649, 1729, 1885, 1891, 2041, 282153, 262153, 282153,5,5 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, 56,598, 51, 81 59, 51, 51 , 9577, 9637	A020141
čtrnáct	15, 39, 65, 195, 481, 561, 781, 793, 841, 985, 1105, 1111, 1541, 1891, 2257, 2465, 2561, 177575, 36, 717 75, 35 7449, 7543, 7585, 8321, 9073	A020142
patnáct	14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 87031, 97031, 97031, 97031,	A020143
16	15, 51, 85, 91, 255, 341, 435, 451, 561, 595, 645, 703, 1105, 1247, 1261, 1271, 1285, 1387, 1 7, 1681, 1 7, 1581, 1 7, 1581 , 2431, 2465, 2701, 2821, 3133, 3277, 3367, 3655, 3683, 4033, 4369, 4371, 4681, 4795, 4859, 5083, 5151, 6601, 6643, 7471, 77735, 7735, 77735, 7735, 7735, 7735, 7735, 7735, 7735, 7735, 7735, 7735, 777351, 7471, 77351 , 7735, 7735, 7735. 7957, 8119, 8227, 8245, 8321, 8481, 8695, 8749, 8911, 9061, 9131, 9211, 99605	A020144
17	5 , 8481, 8911	A020145
osmnáct	25, 49, 65, 85, 133, 221, 323, 325, 343, 425, 451, 637, 931, 1105, 1225, 1369, 1387, 1649, 29 2929, 29 2929, 29 2929, 2921729 3325, 4165, 4577, 4753, 5525, 5725, 5833, 5941, 6305, 6517, 6601, 7345, 8911, 9061	A020146
19	20, 9, 15, 18, 45, 49, 153, 169, 343, 561, 637, 889, 905, 906, 1035, 1105, 1629, 1661, 1849, 2 27451,2 , 4033, 4681, 5461, 5466, 5713, 6223, 6541, 6601, 6697, 7957, 8145, 8281, 8401, 8869, 9211, 9997	A020147
dvacet	21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501, 2761, 373 59, 3 730 971, 3 730 921, 317 71, 5 , 6817, 7999, 8421, 8911	A020148
21	4, 10, 20, 55, 65, 85, 221, 703, 793, 1045, 1105, 1852, 2035, 2465, 3781, 4630, 5185, 5473, 8 7, 5995, 9, 6, 5915, 9	A020149
22	21 69 91 105 161 169 345 483 485 645 805 1105 1183 1247 1261 1541 1649 1729 1891 2037 2041; 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, 128105, 71 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, 2413, 2425, 2465, 2707, 278 , 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, 84, 80, 481, 84, 80 1288, 1541, 1729, 1891, 2047. 5662, 5731, 5963, 6601, 7449, 7588, 7813, 8029, 8646, 8911, 9861, 9861	A020153
26	9, 15, 25, 27, 45, 75, 133, 135, 153, 175, 217, 225, 259, 425, 475, 561, 589, 675, 703, 775, 41 1035, 65, 21 035, 65, 65 3145, 3325, 3385, 3565, 3825, 4123, 4525, 4741, 4921, 5041, 5425, 6093, 6475, 6525, 6601, 801597, 801587, 9	A020154
27	26, 65, 91, 121, 133, 247, 259, 286, 341, 365, 481, 671, 703, 949, 1001, 1105, 1541, 1649, 29 2719, 29 2959, 29 2719, 25. 2993, 3146, 3281, 3367, 3605, 3751, 4033, 4745, 4921, 4961, 5299, 5461, 5551, 5611, 5621, 6305, 6533, 6601, 7381, 8401, 8311, 8401, 8311, 8401, 8311, 8401, 831, 8401, 831, 8401, 831, 8401, 831, 8401, 831, 8401, 831, 8401, 831, 8401, 7951, 8401, 7951, 8401, 795, 8401. 9139, 9709, 9809, 9841, 9881, 9919	A020155
28	9, 27, 45, 87, 145, 261, 361, 529, 561, 703, 783, 785, 1105, 1105, 1305, 1413, 1431, 1885, 2041, 272013, 31 24713, 31 24713, 31 24713, 53 , 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, 21876, 1105, 21876, 0729 2821, 3484, 3523, 4069, 4371, 4411, 5149, 5185, 5356, 5473, 5565, 5611, 6097, 6601, 7161, 81, 4214, 81 81 814, 81	A020157
třicet	49, 91, 133, 217, 247, 341, 403, 469, 493, 589, 637, 703, 871, 899, 901, 931, 1273, 1519, 127293, 21 293, 21 293, 21 , 3367, 3577, 4081, 4097, 4123, 5729, 6031, 6061, 6097, 6409, 6601, 6817, 7657, 8023, 8029, 89101	A020158

Další informace o Fermatových pseudoprimech k bázím 31 - 100 naleznete v článcích A020159 - A020228 Encyklopedie celočíselných sekvencí [10] .

Důvody, proč je číslo pseudoprvočíslo

Níže je uvedena tabulka všech bází b < n , pro které n je Fermatovo pseudoprvo (všechna složená čísla jsou pseudoprvočísla v bázi 1 a pro b > n je řešení jednoduše posunuto o k * n , kde k > 0), pokud složená číslo n není v tabulce uvedeno, pak je pseudoprvo pouze v základu 1, nebo v základech, které jsou srovnatelné s 1 (mod n ), to znamená, že počet základen b je 1. Tabulka je sestavena pro n < 180 [11] .

Báze b , pro které n je pseudoprvočíslo
n	Báze b , pro které n je pseudojednoduchý Fermat(< n )	Počet bází b (< n ) [12]
9	osmnáct	2
patnáct	1, 4, 11, 14	čtyři
21	1, 8, 13, 20	čtyři
25	1, 7, 18, 24	čtyři
27	1, 26	2
28	1, 9, 25	3
33	1, 10, 23, 32	čtyři
35	1, 6, 29, 34	čtyři
39	1, 14, 25, 38	čtyři
45	1, 8, 17, 19, 26, 28, 37, 44	osm
49	1, 18, 19, 30, 31, 48	6
51	1, 16, 35, 50	čtyři
52	1, 9, 29	3
55	1, 21, 34, 54	čtyři
57	1, 20, 37, 56	čtyři
63	1, 8, 55, 62	čtyři
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	čtyři
70	1, 11, 51	3
75	1, 26, 49, 74	čtyři
76	1, 45, 49	3
77	1, 34, 43, 76	čtyři
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	čtyři
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	čtyři
95	1, 39, 56, 94	čtyři
99	1, 10, 89, 98	čtyři
105	1, 8, 13, 22, 29, 34, 41, 43, 62, 64, 71, 76, 83, 92, 97, 104	16
111	1, 38, 73, 110	čtyři
112	1, 65, 81	3
115	1, 24, 91, 114	čtyři
117	1, 8, 44, 53, 64, 73, 109, 116	osm
119	1, 50, 69, 118	čtyři
121	1, 3, 9, 27, 40, 81, 94, 112, 118, 120	deset
123	1, 40, 83, 122	čtyři
124	1, 5, 25	3
125	1, 57, 68, 124	čtyři
129	1, 44, 85, 128	čtyři
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	čtyři
141	1, 46, 95, 140	čtyři
143	1, 12, 131, 142	čtyři
145	1, 12, 17, 28, 41, 46, 57, 59, 86, 88, 99, 104, 117, 128, 133, 144	16
147	1, 50, 97, 146	čtyři
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	čtyři
159	1, 52, 107, 158	čtyři
161	1, 22, 139, 160	čtyři
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	čtyři
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	čtyři

Je třeba poznamenat, že pokud p je prvočíslo, pak p 2 je Fermatovo pseudoprvo k bázi b právě tehdy, když p je Wieferichovo prvočíslo k bázi b . Například 1093 2 = 1 194 649 je Fermatova pseudojednoduchá báze 2.

Počet bází b pro n (pro prvočíslo n musí být počet bází b roven n-1 , protože všechna b splňují Fermatovu malou větu ):

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, … (sekvence A063994 v OEIS )

Nejmenší báze b > 1, pro kterou n je pseudoprvočíslo (nebo prvočíslo):

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, … (sekvence A105222 v OEIS ).

Slabé pseudojednoduché

Složené číslo n , které vyhovuje srovnání b n = b (mod n ) se nazývá slabé Fermatovo pseudoprvo k bázi b (zde b nemusí být koprimé k n ) [13] . Nejmenší slabá pseudoprima k bázi b jsou:

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, … (sekvence A000790 v OEIS )

Pokud je požadováno, aby n > b , pak:

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 … (sekvence A239293 v OEIS )

Aplikace

Kvůli jejich vzácnosti mají taková pseudoprimes důležité praktické aplikace. Například kryptografické algoritmy s veřejným klíčem, jako je RSA , vyžadují schopnost rychle najít velká prvočísla [14] . Obvyklý algoritmus pro generování prvočísel je generovat náhodná lichá čísla a testovat je na prvočíslost . Testy deterministické primality jsou však pomalé. Pokud jsme ochotni akceptovat libovolně malou pravděpodobnost, že nalezené číslo není prvočíslo, ale pseudoprvo, lze použít mnohem rychlejší a jednodušší Fermatův test .

Poznámky

↑ Desmedt, Yvo. Šifrovací schémata // Příručka Algoritmy a teorie počítání: Speciální témata a techniky (anglicky) / Atallah, Michail J.& Blanton, Marina. - CRC Press , 2010. - S. 10-23. — ISBN 978-1-58488-820-8 .
↑ Weisstein, Eric W. Fermat Pseudoprime na webu Wolfram MathWorld .
↑ Crandall, Pomerance, 2011 , str. 155.
↑ 1 2 Pomerance, Selfridge, Wagstaff 1980 , Věta 1.
↑ W. R. Alford ; Andrew Granville ; Carl Pomerance . Existuje nekonečně mnoho Carmichaelových čísel // Annals of Mathematics : journal . - 1994. - Sv. 139 . - str. 703-722 . - doi : 10.2307/2118576 .
↑ Crandall, Pomerance, 2011 , Věta 3.4.2, str. 154-155.
↑ OEIS sekvence A007535 _
↑ OEIS sekvence A001567 _
↑ W. Sierpinski. Kapitola V.7 // Elementární teorie čísel = Teoria Liczb / Ed. A. Schinzel. - 2 dílčí edice. - Amsterdam: Severní Holandsko, 15. 2. 1988. - S. 232. - 528 s. — (North-Holland Mathematical Library). — ISBN 9780444866622 . Archivováno 8. prosince 2015 na Wayback Machine
↑ Viz také Fermatovu tabulku pseudoprvot pro základy do 150 (německy) ; zde n není definováno jako pseudoprvočíslo v bázích srovnatelných s 1 nebo -1 (mod n ).
↑ Podrobnější informace pro n = 181 ... 5000 jsou v tabulce (německy) ; zde n není definováno jako pseudoprvočíslo v bázích srovnatelných s 1 nebo -1 (mod n ).
↑ OEIS sekvence A063994 _
↑ Crandall, Pomerance, 2011 , Věta 3.4.1, str. 154.
↑ Crandall, Pomerance, 2011 , Algoritmus 8.1.2, s. 438.

Literatura

Richard Crandall, Carl Pomerance. Prvočísla: Kryptografické a výpočetní aspekty. - Dům knihy "LIBROKOM", 2011. - S. 154-158, 438-441.
Carl Pomerance ; John L. Selfridge , Samuel S. Wagstaff, Jr Pseudoprima do 25 10 9 // Matematika počítání : deník. - 1980. - Červenec ( roč. 35 , č. 151 ). - S. 1003-1026 . - doi : 10.1090/S0025-5718-1980-0572872-7 .