Fermatpseudoprimtal

Inom talteori utgör Fermatpseudoprimtal den viktigaste klassen av pseudoprimtal från Fermats lilla sats.

Definition

Fermats lilla sats säger att om ${\textstyle p}$ är ett primtal samt att ${\textstyle a}$ och ${\textstyle p}$ är relativt prima så är ${\textstyle a^{p-1}}$ delbart med ${\textstyle p}$. För ett heltal $a>1$, om ett sammansatt heltal ${\textstyle x}$ är delbart med ${\textstyle a^{x-1}-1}$, så kallas ${\textstyle x}$ för ett Fermatpseudoprimtal till basen ${\textstyle a}$. Med andra ord är ett sammansatt heltal ett Fermatpseudoprimtal för basen ${\textstyle a}$ om det lyckas passera Fermats primtalstest med basen ${\textstyle a}$.

Egenskaper

Fördelning

Det finns oändligt många pseudoprimtal för en given bas ${\textstyle a>1}$. Cipolla visade 1904 hur man kan skapa ett oändligt antal pseudoprimtal med en bas som är större än 1:

Låt ${\textstyle p}$ vara ett primtal som inte är delbart med ${\textstyle a(a^{2}-1)}$ samt att ${\textstyle A={\tfrac {(a^{p}-1)}{(a-1)}}}$ och ${\textstyle B={\tfrac {(a^{p}+1)}{(a+1)}}}$. Då är ${\textstyle n=AB}$ är ett sammansatt tal och är ett pseudoprimtal för basen ${\textstyle a}$.

I själva verket finns det oändligt många starka pseudoprimtal för alla baser som är större än 1 och oändligt många Carmichaeltal, men de är relativt sällsynta. Det finns 3 stycken pseudoprimtal för bas 2 under 1 000, 245 under 1,0 × 10⁶ och 21 853 mindre än 2,5 × 10¹⁰.

Små pseudoprimtal

De minsta Fermatpseudoprimtalen för varje bas ${\textstyle a\leq 200}$ ges i följande tabell; färgerna markerar antalet primtalsfaktorer. Till skillnad från i definitionen i början av artikeln så utesluts pseudoprimtalen under ${\textstyle a}$ i tabellen nedan.

Tabell över de minsta Fermatpseudoprimtalen (talföljd A007535 i OEIS)
${\textstyle a}$	Minsta pseudoprimtal	${\textstyle a}$	Minsta pseudoprimtal	${\textstyle a}$	Minsta pseudoprimtal	${\textstyle a}$	Minsta pseudoprimtal
1	4 = 22	51	65 = 5 · 13	101	175 = 52 × 7	151	175 = 52 × 7
2	341 = 11 × 31	52	85 = 5 × 17	102	133 = 7 × 19	152	153 = 32 × 17
3	91 = 7 × 13	53	65 = 5 × 13	103	133 = 7 × 19	153	209 = 11 × 19
4	15 = 3 × 5	54	55 = 5 × 11	104	105 = 3 × 5 × 7	154	155 = 5 × 31
5	124 = 22 × 31	55	63 = 32 × 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 = 52	57	65 = 5 × 13	107	133 = 7 × 19	157	186 = 2 × 3 × 31
8	9 = 32	58	133 = 7 × 19	108	341 = 11 × 31	158	159 = 3 × 53
9	28 = 22 × 7	59	87 = 3 · 29	109	117 = 32 × 13	159	247 = 13 × 19
10	33 = 3 × 11	60	341 = 11 × 31	110	111 = 3 × 37	160	161 = 7 × 23
11	15 = 3 × 5	61	91 = 7 × 13	111	190 = 2 × 5 × 19	161	190 = 2 × 5 × 19
12	65 = 5 × 13	62	63 = 32 × 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
14	15 = 3 × 5	64	65 = 5 × 13	114	115 = 5 × 23	164	165 = 3 × 5 × 11
15	341 = 11 × 31	65	112 = 24 × 7	115	133 = 7 × 19	165	172 = 22 × 43
16	51 = 3 × 17	66	91 = 7 × 13	116	117 = 32 × 13	166	301 = 7 × 43
17	45 = 32 × 5	67	85 = 5 × 17	117	145 = 5 × 29	167	231 = 3 × 7 × 11
18	25 = 52	68	69 = 3 × 23	118	119 = 7 × 17	168	169 = 132
19	45 = 32 × 5	69	85 = 5 × 17	119	177 = 3 × 59	169	231 = 3 × 7 × 11
20	21 = 3 × 7	70	169 = 132	120	121 = 112	170	171 = 32 × 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 = 52	74	75 = 3 × 52	124	125 = 53	174	175 = 52 × 7
25	28 = 22 × 7	75	91 = 7 × 13	125	133 = 7 × 19	175	319 = 11 × 19
26	27 = 33	76	77 = 7 × 11	126	247 = 13 × 19	176	177 = 3 × 59
27	65 = 5 × 13	77	247 = 13 × 19	127	153 = 32 × 17	177	196 = 22 × 72
28	45 = 32 × 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
30	49 = 72	80	81 = 34	130	217 = 7 × 31	180	217 = 7 × 31
31	49 = 72	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 = 33 × 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 = 32 × 5	87	91 = 7 × 13	137	148 = 22 × 37	187	217 = 7 × 31
38	39 = 3 × 13	88	91 = 7 × 13	138	259 = 7 × 37	188	189 = 33 × 7
39	95 = 5 × 19	89	99 = 32 × 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 = 22 × 3 × 23
44	45 = 32 × 5	94	95 = 5 × 19	144	145 = 5 × 29	194	195 = 3 × 5 × 13
45	76 = 22 × 19	95	141 = 3 × 47	145	153 = 32 × 17	195	259 = 7 × 37
46	133 = 7 × 19	96	133 = 7 × 19	146	147 = 3 × 72	196	205 = 5 × 41
47	65 = 5 × 13	97	105 = 3 × 5 × 7	147	169 = 132	197	231 = 3 × 7 × 11
48	49 = 72	98	99 = 32 × 11	148	231 = 3 × 7 × 11	198	247 = 13 × 19
49	66 = 2 × 3 × 11	99	145 = 5 × 29	149	175 = 52 × 7	199	225 = 32 × 52
50	51 = 3 × 17	100	153 = 32 × 17	150	169 = 132	200	201 = 3 × 67

Tillämpningar

Rariten hos dessa pseudoprimtal har viktiga tillämpningar inom kryptografi. Exempelvis behöver vissa asymmetriska krypteringsalgoritmer hitta stora primtal snabbt. En av dessa algoritmer är RSA. Den vanligaste algoritmen för att generera ett primtal på är att generera slumpmässiga udda tal och testa om dem är ett primtal eller inte. Deterministiska primitetstester är emellertid väldigt långsamma. Om man är villig att tolerera en godtyckligt liten chans att det hittade talet inte är ett primtal utan ett pseudoprimtal så är det möjligt att använda Fermats primtalstest som är mycket snabbare och enklare.

Externa länkar

• Tabell över pseudoprimtal och övrig data av William Galway och Jan Feitsma
• Slutgiltiga svar om pseudoprimtal av Gérard Michon