Vikipedio:Projekto matematiko/Verŝajna primo

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
Verŝajna primo
(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.

En nombroteorio, verŝajna primo (_PRP_) estas entjero (tiu, ke, kiu) (verigas, kontentigas) specifa kondiĉo ankaŭ kontentigita per ĉiuj primoj. Malsama (klavas, tipoj) de verŝajnaj primoj havi malsamaj specifaj kondiĉoj. Dum tie (majo, povas) esti verŝajnaj primoj (tiu, ke, kiu) estas _composite_ ((nomita, vokis) (pseŭdoprimoj, pseŭdoprimas)), la kondiĉo estas ĝenerale elektita por ke fari tia (esceptoj, esceptas) malofta.

Fermat-a's provo por _compositeness_, kiu estas bazita sur Malgranda teoremo de Fermat, (laboroj, laboras) kiel sekvas: donita entjero n, elekti iu entjero a interprimo al n kaj kalkuli a^{n − 1} module n. Se la rezulto estas malsama de 1, n estas _composite_. Se ĝi estas 1, n (majo, povas) aŭ (majo, povas) ne esti primo; n estas tiam (nomita, vokis) (malforta) verŝajna primo al bazo a.

Eŭlera verŝajna primo al bazo a estas entjera tio estas indikita primo per la io pli forta teoremo (tiu, ke, kiu) por (ĉiu, iu) primo p, a^{(p − 1)/2} egalas (a/p) module p, kie (a/p) estas la _Legendre_ simbolo. Eŭlera verŝajna primo kiu estas _composite_ estas (nomita, vokis) Eŭlero-jakobia kvazaŭprimo al bazo a.

Ĉi tiu provo (majo, povas) esti plibonigita per uzanta la fakto (tiu, ke, kiu) la nur kvadrataj radikoj de 1 module primo estas 1 kaj −1. Skribi n = d · 2^s + 1, kie d estas nepara. La nombro n estas forta verŝajna primo (_SPRP_) al bazo a se unu de jenaj kondiĉoj tenas:

$a^d\equiv 1\mod n$

$a^{d\cdot 2^r}\equiv -1\mod n\quad\mbox{ for some }0\leq r\leq(s-1)$

Forta verŝajna primo al bazo a estas (nomita, vokis) forta kvazaŭprimo al bazo a. Ĉiu forta verŝajna primo al bazo a estas ankaŭ Eŭlera verŝajna primo al la sama bazo, sed ne (malvirto, ŝraŭbtenilo) _versa_.

Verŝajna (primeco, plejparte) estas bazo por kompetenta (primeco, plejparte) (testante, testado) (algoritmoj, algoritmas), kiu trovi apliko en ĉifriko. Ĉi tiuj (algoritmoj, algoritmas) estas kutime probableca en naturo. La ideo estas (tiu, ke, kiu) dum estas _composite_ verŝajnaj primoj al bazo a por (ĉiu, iu) (fiksis, neŝanĝebligita) a, ni (majo, povas) dorsflanko la (roloj, rolas): por (ĉiu, iu) (fiksis, neŝanĝebligita) _composite_ n kaj hazarde elektita a, ni povas esperi (tiu, ke, kiu) n estas ne pseŭdoprimo al bazo a, kun alta probablo.

Ĉi tiu estas bedaŭrinde malvera por malfortaj verŝajnaj primoj, ĉar tie ekzisti _Carmichael_ nombroj; sed ĝi estas vera por pli rafinita (komprenaĵoj, nocioj, nocias) de verŝajna (primeco, plejparte), kiel fortaj verŝajnaj primoj (ni preni la Muelisto-_Rabin_ algoritmo), aŭ Eŭleraj verŝajnaj primoj (_Solovay_-_Strassen_ algoritmo).

(Eĉ, Ebena, Para) kiam (determinisma, determina) (primeco, plejparte) pruvo estas postulita, utila unua (ŝtupo, paŝi) estas al provo por verŝajna (primeco, plejparte). Ĉi tiu povas rapide elimini (kun certeco) plej _composites_.

_PRP_ provo estas iam kombinita kun (baremo, tabelo, tablo) de malgranda (pseŭdoprimoj, pseŭdoprimas) al rapide fondi la (primeco, plejparte) de donita nombro (pli minuskla, pli malgranda) ol iu sojlo.