Primeco-testo de Fermat

La primeco-testo de Fermat estas probableca testo por kontroli ĉu entjero estas verŝajna primo.

Koncepto

Malgranda 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

La 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 

Estas 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 
La ĉ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.

Kategorio:Modula aritmetiko
Kategorio:Primeco-testoj
Kategorio:Kvazaŭprimoj