Primeco-testo aŭ testo je primeco estas algoritmo por kontroli, ĉu enigita nombro estas primo aŭ komponita. La rezulto de la testo indikas, ke estas verŝajne, ke la enigita nombro estas primo, kvankam ne garantias tion. Tial nombron, kiu pasas teston je primeco oni nomas pseŭdoprimo, kutime aldonante, pri kiu primeco-testo temas.
Ekzistas grava diferenco inter tia testado pri primeco kaj entjera faktorigo. Faktorigo estas kompute peza problemo, sed primeco-testado povas esti relative facila.
Simpla maniero
La plej rekta primeco-testo estas jena: estu donita nombro n, kaj oni kontrolu ĉiun entjeron m ekde 2 ĝis n-1, ĉu ĝi dividas la nombron n. Se n estas dividebla per iu m, tiam n estas komponita, alie ĝi estas primo.
Tiu ĉi algoritmo povas esti plirapidigita per testado de m nur malpli randaj 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.
Tiaj simplaj algoritmoj estas tro malrapidaj en praktiko por grandaj nombroj, kompare kun sube donitaj manieroj.
Probablecaj testoj
Plej popularaj primecaj testoj estas probablecaj testoj. Ĉi tiuj testoj uzas, krom la testata nombro n, iujn aliajn nombrojn a kiuj estas elektataj hazarde de iu aro. Kutimaj hazardigitaj primeco-testoj neniam diras pri primo, ke ĝi estas komponita, sed eblas pozitiva rezulto de la algoritmo pri reale komponita nombro. La probablo de eraro povas reduktiĝas per ripetado de la testo kun multaj sendepende elektitaj a; por du kutime uzataj testoj, por ĉiu komponita n almenaŭ duono de la a detektas komponitecon de n (tiam a estas nomata kiel atestanto por la komponiteco). 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 testo 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 komponita nombro, kaj la testo haltiĝas.
- Se la testo ankoraŭ ne haltiĝis kun rezulto ke n estas komponita, do nun rezultigi ke n estas primo.
n, kiu ne aperis kiel komponita nombro en ĉi tia testo povas esti deklarita kiel pseŭdoprimo.
La plej simpla probableca primeca testo estas la primeco-testo de Fermat. Ĝi estas nur heŭristika testo; iuj komponitaj nombroj (nombroj de Carmichael) estas deklarataj kiel pseŭdoprimoj 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 primeco-testo de Miller-Rabin kaj primeco-testo de Solovay-Strassen estas pli malnaivaj variantoj kiu detektas ĉiujn komponitajn nombrojn (por ili ne ekzistas analogo de nombroj de Carmichael). Por ĉiu komponita nombro n, almenaŭ 3/4 (por primeca testo de Miller-Rabin) aŭ 1/2 (por primeca testo de Solovay-Strassen) de nombroj a estas atestantoj de komponiteco de n). Ili estas ofte la manieroj de elekto, ĉar ili estas multe pli rapidaj ol la aliaj ĝeneralaj primecaj testoj. Por alta fido, la primeco-testo de Frobenius detektas almenaŭ 99.987 procentojn de komponitaj nombroj, kvankam ĝia rula tempo estas tipe trifoje pli granda ol tempo de primeca testo de Miller-Rabin kaj primeca testo de Solovay-Strassen.
Leonard Adleman kaj Huang prezentis seneraran (sed kun atendita polinoma tempo) varianton de la elipsakurba primeco-testo. 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 testo grave pli rapida ol la simplaj manieroj estis la primeco-testo 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 elipso-kurba primeco-testo 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 primeco-testo 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 primeco-testo AKS, havas pruvitan ruliĝotempon Õ((log n)12), poste plibonigita al Õ((log n)6) [1]. Ĉi tiu estis la unua determinisma primeca testo kun pruvita polinoma tempo. En praktiko, ĉi tiu algoritmo estas pli malrapida ol probablecaj testo-manieroj.
Referencoj
Eksteraj ligiloj
- Manindra Agrawal, Neeraj Kayal, Nitin Saxena], Primoj estas en P Arkivigite je 2006-07-16 per la retarkivo Wayback Machine, Analoj de Matematiko 160 (2004), ne. 2, pp. 781–793, pri la primeca testo AKS.
- Distingo de primoj de komponitaj nombroj, D.J. Bernstein
- La primaj paĝoj
- Datumbazo de grandaj primoj
- Primeca testo de Lucas kun faktorigita N-1 je MathPages