Primeco-testo de Fermat
La primeco-testo de Fermat estas probableca testo por kontroli ĉu entjero estas verŝajna primo.
Koncepto
redaktiMalgranda teoremo de Fermat diras ke se p estas primo kaj a estas reciproke prima kun p, 1≤a<p, do ap-1-1 estas dividebla per p aŭ per la alia skribmaniero
Se oni bezonas kontroli, ĉu p estas primo, tiam oni povas preni hazardajn a en la intervalo kaj konroli ĉu la egaleco veras. Se la egaleco ne veras por iu a, tiam p estas ne primo. Se la egaleco veras por multaj valoroj de a, tiam oni povas diri ke p estas verŝajna primo, aŭ pseŭdoprimo.
Povas okazi en la testoj ke oni ne prenis iun a tian ke la egaleco malveras. Ĉiu a tia ke
kiam n estas komponita estas sciata kiel neatestanto de Fermat. Se a estas tia ke
tiam a estas atestanto de Fermat por la komponiteco de n.
Algoritmo kaj rula tempo
redaktiLa algoritmo povas esti skribita kiel sekvas:
- Enigoj: n: valoro testota por primeco; k: parametro, kiu difinas la nombron de fojoj de testado por primeco
- Eligo: "komponita" se n estas komponita, alie "verŝajne primo"
- ripeti k fojojn:
- preni valoron a hazarde en la limigo (1, n-1]
- se an-1 mod n ≠ 1 tiam redoni rezulton "komponita"
- redoni rezulton "verŝajne primo"
Uzante rapidajn algoritmojn por modula potencigo, la rula tempo de ĉi tiu algoritmo estas O(k × log2n × log log n × log log log n), kie k estas la nombro de provoj por hazardaj a, kaj n estas la valoro kiun oni testas por primeco.
Problemoj
redaktiEstas certaj valoroj de n konataj kiel nombroj de Carmichael, por kiuj ĉiuj valoroj de a estas reciproke primaj kun n estas neatestantoj. Kvankam nombroj de Carmichael estas maloftaj, estas sufiĉa nombro da ili, por ke primeco-testo de Fermat estas ofte ne uzata, anstataŭe estas uzataj, ekzemple, primeco-testo de Miller-Rabin kaj primeco-testo de Solovay-Strassen.
Ĝenerale, se n ne estas nombro de Carmichael tiam almenaŭ duono de ĉiuj
estas atestantoj de Fermat. Por pruvo de ĉi tio estu a atestanto de Fermat kaj a1, a2, ..., as estu neatestantoj de Fermat. Tiam
kaj do ĉiuj a × ai por i = 1, 2 ... s estas atestantoj de Fermat.
Uzado
redaktiLa ĉifrada programo Pretty Good Privacy (PGP) uzas ĉi tiun primeco-teston. La ŝanco de tio ke PGP generas nombron de Carmichael estas malpli ol 1 el 1050, kio estas sufiĉa por praktikaj celoj.