Fermat pszeudoprímek

A Fermat-féle pszeudoprímek olyan összetett számok , amelyek megfelelnek a Fermat-teszten . Nevét Pierre de Fermat francia matematikusról kapta . A számelméletben a Fermat-féle pszeudoprímek alkotják az álprímek legfontosabb osztályát .

Definíció

Pseudoprímek

Egy összetett számot akkor nevezünk pszeudoprímnek , ha eleget tesz valamilyen szükséges (de nem elégséges ) feltételnek , hogy a szám prím legyen, vagyis ha rendelkezik egy prímszám tulajdonságaival .

Fermat kis tétele

Fermat kis tétele azt mondja, hogy ha n egy prímszám, akkor minden számra n -re írt koprím , a kongruencia teljesül . $a^{n-1} \equiv 1 \pmod n$

Pseudosimple Farms

Az n összetett számot Fermat pszeudoprímnek nevezzük az a bázisban ( n -re koprím ), ha összehasonlítás történik . Más szavakkal, egy összetett számot pszeudoprímnek mondunk, ha megfelel a Fermat-teszten , és egy [1] -et alapoz meg . Azt a számot, amely Fermat pszeudoprímje minden másodprím-alapban, Carmichael-számnak nevezzük . $a^{n-1} \equiv 1 \pmod n$

Változatok

A meghatározásnak van néhány változata:

Egyes források megkövetelik, hogy a pszeudoprím páratlan legyen [2] , mivel a páros szám nyilvánvalóan összetett.
Minden páratlan szám kielégíti a számot , így ebben az esetben nem kapunk új információt a számról. Ezt a Crandall és Pomerance [3] által adott definíció kizárja : Az összetett szám egy Fermat pszeudoprím az alaphoz , ha és $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.$

Tulajdonságok

Elosztás

Egy adott bázisban végtelen sok pszeudoprím található (sőt, végtelenül sok erős pszeudoprím [4] és végtelenül sok Carmichael-szám [5] ), de ezek meglehetősen ritkák [6] . Csak három 2. bázisú Fermat pszeudoprím van 1000-nél, 245 egymilliónál kevesebb, és csak 21853 kisebb 25 milliárdnál [4] .

Táblázatok néhány Fermat pszeudoprímmel

Fermat legkisebb álegyszerűsége

A legkisebb Fermat-pszeudo-egyszerűség minden bázishoz a ≤ 200 az alábbi táblázatban találhatók; a színek megkülönböztetik a számokat a különböző prímosztók száma alapján [7] .

Fermat legkisebb álegyszerűsége
a	A legkisebb p-pF	a	A legkisebb p-pF	a	A legkisebb p-pF	a	A legkisebb p-pF
egy	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
négy	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
nyolc	9 = 3²	58	133 = 7 19	108	341 = 11 31	158	159 = 353
9	28 = 2² 7	59	87 = 3 29	109	117 = 3² 13	159	247 = 13 19
tíz	33 = 3 11	60	341 = 11 31	110	111 = 3 37	160	161 = 7 23
tizenegy	15 = 3 5	61	91 = 7 13	111	190 = 2519	161	190=2519
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
tizennégy	15 = 3 5	64	65 = 5 13	114	115 = 5 23	164	165 = 3 5 11
tizenöt	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
tizennyolc	25 = 5²	68	69 = 3 23	118	119 = 7 17	168	169 = 13²
19	45 = 3² 5	69	85 = 5 17	119	177 = 359	169	231 = 3 7 11
húsz	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 = 359
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
harminc	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 = 571	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 = 371	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²
ötven	51 = 3 17	100	153 = 3² 17	150	169 = 13²	200	201 = 3 67

Poole számok

A 2. bázishoz tartozó Fermat pszeudoegyszerűsítéseket Paul Poulet belga matematikus [8] után Poulet-számoknak nevezik . A hatvanegyedik Poolet-szám faktorizálása, beleértve a tizenhárom Carmichael-számot (félkövérrel kiemelve), az alábbi táblázatban található.

Poole számok
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

A Poole-számot, amelynek minden d osztója osztja a 2 d − 2 számot is, szuperpoolszámnak nevezzük . Végtelenül sok olyan Poulet-szám van, amely nem szuper-Poulet-szám [9] .

Fermat első pszeudoprímjai (10000-ig) a

Fermat első pszeudoprímjei (10000-ig) a bázisban
a	Fermat pszeudoprímek (10 000-ig)	OEIS sorozat (külső hivatkozás)
egy	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, … minden összetett szám)	A002808
2	341 561 645 1105 1387 1729 1905 2047 2465 2701 2821 3277 4033 4369 4371 4681 5461 6601 7957 8318 1729	A001567
3	91 121 286 671 703 949 1105 1541 1729 1891 2465 2665 2701 2821 3281 3367 3751 4961 5551 6601 4018	A005935
négy	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 4369 4371 4371 4371 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, 78213, 8913, 891	A005936
6	35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3565, 3589, 3913, 3565, 3589, 3913, 3565, 3589, 3913, 3913, 3913, 3913, 57, 13, 1333	A005937
7	6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321	A005938
nyolc	9 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, 8481, 8911, 9265, 97, 97, 97, 97	A020137
9	4, 8, 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1036, 1105, 1288, 1036, 1105, 1288, 1288, 13, 49 2501, 2665, 2701, 2806, 2821, 2926, 3052, 3281, 3367, 3751, 4376, 4636, 4961, 5356, 5551, 6364, 6601, 6643, 7081, 7381, 7913, 8401, 8695. 8911	A020138
tíz	9., 33., 91., 99., 259., 451., 481., 561., 657., 703., 909., 1233., 1729., 2409., 2821., 2981., 3333., 3367., 3333., 3367., 3333., 3367., 3333., 3367., 3333., 3367., 3333., 3367., 3333., 3367., 3333., 3367., 3333. , 7777, 8149, 8401, 8911	A005939
tizenegy	10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257, 2465, 2257, 2465, 2257, 2465, 2821, 40, 58, 58, 59, 58 , 9730	A020139
12	65, 91, 133, 143, 145, 247, 377, 385, 703, 1045, 1099, 1105, 1649, 1729, 1885, 1891, 2041, 1891, 2041, 1891, 2041, 1891, 2041, 1891, 2041, 2261, 1891, 2041, 2261, 1891, 2041, 2261, 35, 35, 25, 25, 23, 25, 25, 25 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, 2806, 3605, 2806, 3605, 5006, 3605, 2806, 3605, 2806, 3605, 5006, 85, 81, 5145 , 9577, 9637	A020141
tizennégy	15., 39., 65., 195., 481., 561., 781., 793., 841., 985., 1105., 1111., 1541., 1891., 2257., 2465., 2561., 2465., 2561., 2465., 2561., 2465., 2561., 2465., 2561., 2465., 2561., 2465., 2561., 2465., 2561., 2465., 2561., 2465., 2561., 2465., 2561., 2465., 2561., 2465., 2561., 2465., 2561. 7449, 7543, 7585, 8321, 9073	A020142
tizenöt	14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 801, 871, 871	A020143
16	51 , 2431, 2465, 2701, 2821, 3133, 3277, 3367, 3655, 3683, 4033, 4369, 4371, 4681, 4795, 4859, 5083, 5151, 5461, 55551, 66601, 66643, 7471, 7735, 7735, 7735, 7735, 7735, 7735, 7735. , 7735, 7735, 7735. 7957, 8119, 8227, 8245, 8321, 8481, 8695, 8749, 8911, 9061, 9131, 9211, 9915	A020144
17	4 , 8481, 8911	A020145
tizennyolc	25, 49, 65, 85, 133, 221, 323, 325, 343, 425, 451, 637, 931, 1105, 1225, 1369, 1387, 1649, 1387, 1649, 1729, 1387, 1649, 1729, 1387, 1649, 1729, 1387, 1649, 1729, 20, 25, 7, 25, 25, 25 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, 1661, 1849, 1849, 1661, 1849, 1849, 1661, 1849, 1849, 20, 25, 25, 25, 25, 25, 25, 21 , 4033, 4681, 5461, 5466, 5713, 6223, 6541, 6601, 6697, 7957, 8145, 8281, 8401, 8869, 9211, 9997	A020147
húsz	21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501, 2761, 2501, 2761, 2501, 2761, 2501, 2761, 2501, 2761, 2821, 2501, 2761, 2821, 2501, 2761, 2821, 2501, 2761, 2821, 2501, 2761, 2827, 31, 30, 30, 30, 36, 30 , 6817, 7999, 8421, 8911	A020148
21	4	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, 55551, 55565, 5963, 6019, 6601, 6693, 6693, 6693, 6693, 6693, 6693, 6693, 6693, 6693, 6693, 6693, 6693, 6693, 6693, 703. 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., 1045., 1065., 1045., 1065., 1105., 1045., 1065., 1105., 1045., 1065., 1105., 1045., 1065., 1105., 1045., 1065. 2465, 2501, 2701, 2821, 2926, 3097, 3445, 4033, 4081, 4345, 4371, 4681, 5005, 5149, 6253, 6369, 6533, 6541, 7189, 7267, 7957, 8321, 8365, 8651 8911, 8965, 9805	A020151
24	25, 115, 175, 325, 553, 575, 805, 949, 1105, 1541, 1729, 1771, 1825, 1975, 2413, 2425, 2465, 2425, 2465, 2413, 2425, 2465, 28, 8, 28, 28, 28, 28, 28, 28, 246, 28. , 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, 616, 703, 781, 88, 1,4,2 1288, 1541, 1729, 1891, 2047. 5662, 5731, 5963, 6601, 7449, 7588, 7813, 8029, 8646, 8911, 9881,	A020153
26	9, 15, 25, 27, 45, 75, 133, 135, 153, 175, 217, 225, 259, 425, 475, 561, 589, 675, 703, 775, 675, 703, 775, 675, 703, 775, 675, 703, 775, 675, 703, 775, 903, 13, 135, 135,15 3145, 3325, 3385, 3565, 3825, 4123, 4525, 4741, 4921, 5041, 5425, 6093, 6475, 6525, 6601, 6697, 801, 801	A020154
27	26, 65, 91, 121, 133, 247, 259, 286, 341, 365, 481, 671, 703, 949, 1001, 1105, 1541, 1649, 1541, 1649, 1721, 1541, 1649, 1721, 1541, 1649, 1721, 21, 25, 25, 25, 25, 25, 25, 28, 286 2993, 3146, 3281, 3367, 3605, 3751, 4033, 4745, 4921, 4961, 5299, 5461, 5551, 5611, 5621, 6305, 6533, 6601, 7381, 7585, 7957, 8227, 8321, 8401 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, 1431, 1885, 2041, 2461, 1885, 2041, 2461, 1885, 2041, 2461, 1885, 2041, 2461, 1885, 2041, 2461, 1885, 2041; , 5365, 7065, 8149, 8321, 8401, 9841	A020156
29	4 2821, 3484, 3523, 4069, 4371, 4411, 5149, 5185, 5356, 5473, 5565, 5611, 6097, 6601, 7161, 6601, 7161, 7291, 7161, 7294, 1, 83, 841, 84, 84	A020157
harminc	49, 91, 133, 217, 247, 341, 403, 469, 493, 589, 637, 703, 871, 899, 901, 931, 1273, 1519, 1531, 1273, 1519, 1537, 1273, 1519, 1537, 273, 37, 27, 27, 37, 203 , 3367, 3577, 4081, 4097, 4123, 5729, 6031, 6061, 6097, 6409, 6601, 6817, 7657, 8023, 8029, 8981,9	A020158

A 31–100. bázisig terjedő Fermat-pszeudoprímekkel kapcsolatos további információkért lásd az Encyclopedia of Integer Sequences [10] A020159 – A020228 cikkeit .

Okok, amiért egy szám pszeudoprím

Az alábbiakban egy táblázat látható az összes b < n bázisról , amelyre n egy Fermat pszeudoprím (minden összetett szám pszeudoprím az 1. bázisban, és b > n esetén a megoldást egyszerűen eltoljuk k * n -nel , ahol k > 0), ha az összetett n szám nincs feltüntetve a táblázatban, akkor csak 1-es bázisban, vagy 1-hez hasonló bázisokban (mod n ) pszeudoprím, azaz a b bázisok száma 1. A táblázat n < 180 -ra van összeállítva [11] .

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

Meg kell jegyezni, hogy ha p prím, akkor p 2 akkor és csak akkor a Fermat-féle pszeudoprím b bázishoz , ha p Wieferich prím a b bázishoz . Például 1093 2 = 1 194 649 Fermat pszeudoegyszerű bázisa 2.

A b bázisok száma n -re ( n prím esetén a b bázisok számának n-1- nek kell lennie , mivel minden b kielégíti Fermat kis tételét ):

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, … ( A063994 sorozat az OEIS -ben )

A legkisebb b > 1 bázis, amelyre n pszeudoprím (vagy prím):

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, … ( A105222 sorozat az OEIS -ben ).

Gyenge pszeudoegyszerű

Az n összetett számot , amely kielégíti a b n = b (mod n ) összehasonlítást , gyenge Fermat-pszeudoprímnek nevezzük b bázishoz (itt b -nek nem kell koprímének lennie n -hez ) [13] . A b bázis legkisebb gyenge pszeudoprímjai a következők:

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, … ( A000790 sorozat az OEIS -ben )

Ha szükséges, hogy n > b , akkor:

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, 5 … ( A239293 sorozat az OEIS -ben )

Alkalmazások

Ritkaságuk miatt az ilyen pszeudoprímeknek fontos gyakorlati alkalmazásaik vannak. Például a nyilvános kulcsú kriptográfiai algoritmusok, mint például az RSA , megkövetelik a nagy prímszámok gyors megtalálásának képességét [14] . A prímszámok generálásának szokásos algoritmusa véletlenszerű páratlan számok generálása és prímszám tesztelése . A determinisztikus primalitástesztek azonban lassúak. Ha hajlandóak vagyunk elfogadni egy tetszőlegesen kis valószínűséget, hogy a talált szám nem prím, hanem pszeudoprím, akkor sokkal gyorsabb és egyszerűbb Fermat-teszt használható .

Jegyzetek

↑ Desmedt, Yvo. Titkosítási sémák // Számítási algoritmusok és elméletek kézikönyve: Speciális témák és technikák (angol) / Atallah, Mikhail J.és Blanton, Marina. - CRC Press , 2010. - P. 10-23. — ISBN 978-1-58488-820-8 .
↑ Weisstein, Eric W. Fermat Pseudoprime a Wolfram MathWorld webhelyén .
↑ Crandall, Pomerance, 2011 , p. 155.
↑ 1 2 Pomerance, Selfridge, Wagstaff 1980 , 1. tétel.
↑ W. R. Alford ; Andrew Granville ; Carl Pomerance . Végtelenül sok Carmichael-szám van // Annals of Mathematics : folyóirat . - 1994. - 1. évf. 139 . - P. 703-722 . - doi : 10.2307/2118576 .
↑ Crandall, Pomerance, 2011 , 3.4.2. tétel, p. 154-155.
↑ OEIS szekvencia A007535 _
↑ OEIS szekvencia A001567 _
↑ W. Sierpinski. V.7. fejezet // Elemi számelmélet = Teoria Liczb / Szerk. A. Schinzel. - 2 alkiadás. - Amszterdam: Észak-Hollandia, 1988.02.15. - S. 232. - 528 p. — (Észak-Holland Matematikai Könyvtár). — ISBN 9780444866622 . Archiválva : 2015. december 8. a Wayback Machine -nál
↑ Lásd még Fermat pszeudoprímtáblázatát 150 bázisig (német) ; itt n nem pszeudoprimként van definiálva 1-hez vagy -1-hez hasonló bázisokban (mod n ).
↑ Az n = 181 ... 5000-re vonatkozó részletesebb információk a táblázatban találhatók (német) ; itt n nem pszeudoprimként van definiálva 1-hez vagy -1-hez hasonló bázisokban (mod n ).
↑ OEIS szekvencia A063994 _
↑ Crandall, Pomerance, 2011 , 3.4.1. tétel, p. 154.
↑ Crandall, Pomerance, 2011 , Algoritmus 8.1.2, p. 438.

Irodalom

Richard Crandall, Carl Pomerance. Prímszámok: kriptográfiai és számítási szempontok. - Könyvház "LIBROKOM", 2011. - P. 154-158, 438-441.
Carl Pomerance ; John L. Selfridge , Samuel S. Wagstaff, Jr A pszeudoprímek 25 10 9 -hez // Számítási matematika : folyóirat. - 1980. - július ( 35. évf. , 151. sz.). - P. 1003-1026 . - doi : 10.1090/S0025-5718-1980-0572872-7 .