Vikipedio:Projekto matematiko/Pseŭdoprimo

El Vikipedio

Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al
Pseŭdoprimo
(eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi.

pseŭdoprimo estas verŝajna primo (entjero kiu (kotizoj, kotizas, kvotoj, kvotas, akcioj, akcias, komunigas, partoj, partas) propraĵo komuna al ĉiuj primoj) kiu estas ne reale primo. (Pseŭdoprimoj, Pseŭdoprimas) povas esti (klasifikita, klasigita) laŭ kiuj propraĵaj ili kontentigi.

La plej grava klaso de (pseŭdoprimoj, pseŭdoprimas) veni de Malgranda teoremo de Fermat kaj de ĉi tie estas (nomita, vokis) Fermat-a (pseŭdoprimoj, pseŭdoprimas). Ĉi tiuj teoremaj ŝtatoj (tiu, ke, kiu) se p estas primo kaj a estas interprimo al p, tiam a^p-1 - 1 estas dividebla per p. Se nombro x estas ne primo, a estas interprimo al x kaj x (akvodislimoj, akvodislimas, divizoras, dividas) a^x-1 - 1, tiam x estas (nomita, vokis) pseŭdoprimo al bazo a. Nombro x tio estas pseŭdoprimo por ĉiuj (valoroj, valoras) de a (tiu, ke, kiu) estas interprimo al x estas (nomita, vokis) _Carmichael_ nombro.

La (plej minuskla, plej malgranda) Fermat-a pseŭdoprimo por la bazo 2 estas 341. Ĝi estas ne primo, ekde ĝi egalas 11 · 31, sed ĝi (verigas, kontentigas) Malgranda teoremo de Fermat: 2³⁴¹=2 (_mod_ 341).

La raraĵo de tia (pseŭdoprimoj, pseŭdoprimas) havas gravaj praktikaj implikacioj. Ekzemple, publik-ŝlosila chifriko (algoritmoj, algoritmas) kiel RSA postuli la ebleco al rapide trovi granda (primoj, primas). La kutima algoritmo al generi primoj estas al generi hazardaj neparaj nombroj kaj provaj ilin por (primeco, plejparte). Tamen, (determinisma, determina) plejparte provoj estas malfrua. Se la uzanto estas (volanta, testamentanta, kompleza, komplezema) al toleri tre malgranda ŝanco (tiu, ke, kiu) la nombro fundamenti estas ne primo sed pseŭdoprimo, ĝi estas ebla al uzi la multa pli rapida kaj pli simpla Fermat-a provo de primeco.

Alia (maniero, proksimiĝi, proksimiĝo) estas al uzi pli rafinita (komprenaĵoj, nocioj, nocias) de _pseudoprimality_, e.g. fortaj kvazaŭprimoj aŭ Eŭlero-jakobiaj kvazaŭprimoj, por kiu estas ne _analogues_ de _Carmichael_ nombroj. Ĉi tiu (plumboj, plumbas, kondukas) al probablecaj algoritmoj kiel la _Solovay_-_Strassen_ plejparte provo kaj la Muelisto-_Rabin_ plejparte provo, kiu estas vera plejparte provoj en la (senso, senco) (tiu, ke, kiu) ili ne bedaŭri (ĉiu, iu) _composites_.

Estas malfinie multaj (pseŭdoprimoj, pseŭdoprimas) al donita bazo (fakte, malfinie multaj _Carmichael_ nombroj), sed ili estas iom malofta. Estas nur 3 pseŭda-(primoj, primas) al bazo 2 pli sube 1000, kaj pli sube miliono estas nur 245. (Pseŭdoprimoj, Pseŭdoprimas) al bazo 2 estas (nomita, vokis) _Poulet_ nombroj aŭ iam _Sarrus_ nombroj aŭ _Fermatians_ . La _Poulet_ nombroj kaj _Carmichael_ nombroj (en kuraĝa) supren al 41041 estas:

n		n		n		n		n
1	341 = 11 · 31	11	2821 = 7 · 13 · 31	21	8481 = 3 · 11 · 257	31	15709 = 23 · 683	41	30121 = 7 · 13 · 331
2	561 = 3 · 11 · 17	12	3277 = 29 · 112	22	8911 = 7 · 19 · 67	32	15841 = 7 · 31 · 73	42	30889 = 17 · 23 · 79
3	645 = 3 · 5 · 43	13	4033 = 37 · 109	23	10261 = 31 · 331	33	16705 = 5 · 13 · 257	43	31417 = 89 · 353
4	1105 = 5 · 13 · 17	14	4369 = 17 · 257	24	10585 = 5 · 29 · 73	34	18705 = 3 · 5 · 29 · 43	44	31609 = 73 · 433
5	1387 = 19 · 73	15	4371 = 3 · 31 · 47	25	11305 = 5 · 7 · 17 · 19	35	18721 = 97 · 193	45	31621 = 103 · 307
6	1729 = 7 · 13 · 19	16	4681 = 31 · 151	26	12801 = 3 · 17 · 251	36	19951 = 71 · 281	46	33153 = 3 · 43 · 257
7	1905 = 3 · 5 · 127	17	5461 = 43 · 127	27	13741 = 7 · 13 · 151	37	23001 = 3 · 11 · 17 · 41	47	34945 = 5 · 29 · 241
8	2047 = 23 · 89	18	6601 = 7 · 23 · 41	28	13747 = 59 · 233	38	23377 = 97 · 241	48	35333 = 89 · 397
9	2465 = 5 · 17 · 29	19	7957 = 73 · 109	29	13981 = 11 · 31 · 41	39	25761 = 3 · 31 · 277	49	39865 = 5 · 7 · 17 · 67
10	2701 = 37 · 73	20	8321 = 53 · 157	30	14491 = 43 · 337	40	29341 = 13 · 37 · 61	50	41041 = 7 · 11 · 13 · 41

_Poulet_ nombro ĉiuj de kies divizoroj d dividi 2^d - 2 estas (nomita, vokis) super-_Poulet_ nombro. Estas malfinie multaj _Poulet_ nombroj kiu estas ne super-_Poulet_ Nombroj.

La unua (plej minuskla, plej malgranda) (pseŭdoprimoj, pseŭdoprimas) por (bazas, bazoj) a ≤ 200 estas donita en jeno (baremo, tabelo, tablo); la (koloroj, koloras, kolorigas) marko la nombro de primaj faktoroj.

a	(plej minuskla, plej malgranda) p-p	a	(plej minuskla, plej malgranda) p-p	a	(plej minuskla, plej malgranda) p-p	a	(plej minuskla, plej malgranda) p-p
		51	65 = 5 · 13	101	175 = 5² · 7	151	175 = 5² · 7
2	341 = 11 · 13	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
4	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
8	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
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 = 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
14	15 = 3 · 5	64	65 = 5 · 13	114	115 = 5 · 23	164	165 = 3 · 5 · 11
15	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
18	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
20	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 = 3³	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
30	49 = 7²	80	81 = 3⁴	130	217 = 7 · 31	180	217 = 7 · 31
31	49 = 7²	81 = 3⁴	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²
50	51 = 3 · 17	100	153 = 3² · 17	150	169 = 13²	200	201 = 3 · 67

[redaktu] Vidi ankaŭ

Eŭlera kvazaŭprimo
- bazo-2 Eŭleraj kvazaŭprimoj (vico _A006970_ en _OEIS_)
Eŭlero-jakobia kvazaŭprimo
- bazo-2 Eŭlero-jakobiaj kvazaŭprimoj (vico _A047713_ en _OEIS_)
- bazo-3 Eŭlero-jakobiaj kvazaŭprimoj (vico _A048950_ en _OEIS_)
Superflua forta _Lucas_ pseŭdoprimo
Fibonacci-a kvazaŭprimo
_Lucas_ pseŭdoprimo
_Perrin_ pseŭdoprimo
_Somer_-_Lucas_ pseŭdoprimo
Forta frobenius-a pseŭdoprimo
Forta _Lucas_ pseŭdoprimo
Forta kvazaŭprimo
- bazo-2 fortaj kvazaŭprimoj (vico _A001262_ en _OEIS_)