Primeco-testo
Primeca provo estas algoritmo por kontroli ĉu eniga nombro estas primo aŭ komponigita.
Noto ke estas grava diferenco inter provo de primeco kaj entjera faktorigo. Kiel en 2008, faktorigo estas kompute peza problemo, sed primeca provo estas kompare facila.
Simpla maniero
La plej simpla primeca provo estas jena: estu donita eniga nombro n, oni kontrolu ĉiun entjeron m ekde 2 ĝis n-1, ĉu ĝi dividas na n. Se n estas dividebla per iu m tiam n estas komponigita, alie ĝi estas primo.
La algoritmo povas esti plirapidigita per testado de m nur pli malgrandaj ol √n. Ankaŭ eblas testi nur neparajn nombrojn m kune kun nombro 2; aŭ nur nombrojn m de formo 6k±1 kune kun nombroj 2 kaj 3.
La rula tempo estas O(√n), aŭ O(2b/2), kie b estas kvanto de bitoj en la nombro. Ĉi tio estas eksponenta tempo de kvanto de bitoj (pli ĝenerale kvanto de ciferoj) en la nombro.
Ĉi ĉiuj simplaj algoritmoj estas tro malrapidaj en praktiko por grandaj nombroj, kompare kun sube donitaj manieroj.
Probablecaj testoj
Plej popularaj primecaj provoj estas probablecaj testoj. Ĉi tiuj testoj uzas, krom la testata nombro n, iujn aliajn nombrojn a kiuj estas elektataj je hazarde de iu aro. Kutima hazardigitaj primecaj provoj neniam pri reale primo diras ke ĝi estas komponigita, sed eblas ke la algoritmo pri reale komponigita nombro diras ke ĝi estas primo. La probablo de eraro povas reduktiĝas per ripetado de la provo kun multaj sendepende elektitaj a; por du kutime uzataj testoj, por ĉiu komponigita n almenaŭ duono de la a detektas komponigitecon de n (tiam a estas nomata kiel atestanto por la komponigiteco). Tiel k ripetadoj reduktas la eraran probablon al maksimume 2-k, kiu povas esti farita sufiĉe malgranda per pligrandiĝo de k.
La baza strukturo de hazardigita primeca provo estas jena:
- Ripeti certan kvanton da fojoj:
- Hazarde preni nombron a.
- Kontroli iun egaleco kun a kaj la donita nombro n. Se la egaleco ne veras, do n estas komponigita nombro, kaj la provo haltiĝas.
- Se la provo ankoraŭ ne haltiĝis kun rezulto ke n estas komponigita, do nun rezultigi ke n estas primo.
n, kiu ne aperis kiel komponigita nombro en ĉi tia testo povas esti deklarita kiel verŝajna primo.
La plej simpla probableca primeca provo estas la primeca provo de Fermat. Ĝi estas nur heŭristika provo; iuj komponigitaj nombroj (nombroj de Carmichael) estas deklarataj kiel "verŝajne primo" por ĉiu a. Tamen, nombroj de Carmichael estas sufiĉe malmultaj kaj la testo estas iam uzata se rapida elekto de nombroj estas bezonata, ekzemple en kreo de ŝlosiloj de la RSA.
La primeca provo de Miller-Rabin kaj primeca provo de Solovay-Strassen estas pli malnaivaj variantoj kiu detektas ĉiujn komponigitajn nombrojn (por ili ne ekzistas analogo de nombroj de Carmichael). Por ĉiu komponigita nombro n, almenaŭ 3/4 (por primeca provo de Miller-Rabin) aŭ 1/2 (por primeca provo de Solovay-Strassen) de nombroj a estas atestantoj de komponigiteco de n). Ili estas ofte la manieroj de elekto, ĉar ili estas multe pli rapidaj ol la aliaj ĝeneralaj primecaj provoj. Por alta fido, la pseŭdoprimeca provo de Frobenius detektas almenaŭ na 99.987% de komponigitaj, kvankam ĝia rula tempo estas tipe trifoje pli granda ol tempo de primeca provo de Miller-Rabin kaj primeca provo de Solovay-Strassen.
Leonard Adleman kaj Huang prezentis seneraran (sed kun atendita polinoma tempo) varianton de la elipsa kurba primeca provo. Malsimile al la aliaj probablecaj testoj, ĉi tiu algoritmo produktas ateston por primeco, kaj tial povas esti uzata por pruvi ke nombro estas primo. La algoritmo estas tro malrapida en praktiko.
Rapidaj determinismaj testoj
La unua determinisma primeca provo grave pli rapida ol la simplaj manieroj estis la primeca provo de Adleman-Pomerance-Rumely; ĝia tempo povas esti pruvita al esti O((log n)c log log log n), kie n estas la testata nombro kaj c estas konstanto sendependa de n.
La elipsa kurba primeca provo povas estas pruvita al ruliĝi en O((log n)6), sed nur se iuj ankoraŭ nepruvitaj (sed larĝe alprenita al esti vera) propozicioj de analitika nombroteorio estas uzataj. Ĝi estas unu el la plej ofte uzataj determinismaj testoj en praktiko.
La realigo de ĉi tiuj du manieroj estas iom malfacila, kreanta riskon de programadaj eraroj, ĉi tio estas unu kaŭzoj de tio ke ili estas ne preferataj.
Se la ĝeneraligita Rimana hipotezo estas alprenita, la primeca provo de Miller-Rabin povas esti ŝanĝita en determinisman version kun tempo Õ((log n)4). En praktiko, ĉi tiu algoritmo estas pli malrapida ol la alia du por ampleksoj de nombroj kiuj povas esti prilaboritaj per la ajna.
La primeca provo AKS, estas pruvita al ruliĝi en Õ((log n)12), poste plibonigita al Õ((log n)6) [1]. Ĉi tiu estis la unua determinisma primeca provo kun pruvita polinoma tempo. En praktiko, ĉi tiu algoritmo estas pli malrapida ol probablecaj manieroj.
Referencoj
Eksteraj ligiloj
greke Manindra Agrawal, Neeraj Kayal, Nitin Saxena], Primoj estas en P, Analoj de Matematiko 160 (2004), ne. 2, pp. 781-793, pri la primeca provo AKS. greke Distingo de primoj de komponigitaj nombroj, D.J. Bernstein greke La primaj paĝoj greke Datumbazo de grandaj primoj greke Primeca provo de Lucas kun faktorigita N-1 je MathPages