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 a^p-1-1 estas dividebla per p aŭ per la alia skribmaniero

$a^{p-1}\equiv 1{\pmod {p}}$

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

$a^{n-1}\equiv 1{\pmod {n}}$

kiam n estas komponita estas sciata kiel neatestanto de Fermat. Se a estas tia ke

$a^{n-1}\not \equiv 1{\pmod {n}}$

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 a^n-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 × log²n × 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

$a\in (\mathbb {Z} /n\mathbb {Z} )^{*}$

estas atestantoj de Fermat. Por pruvo de ĉi tio estu a atestanto de Fermat kaj a₁, a₂, ..., a_s estu neatestantoj de Fermat. Tiam

$(a\cdot a_{i})^{n-1}\equiv a^{n-1}\cdot a_{i}^{n-1}\equiv a^{n-1}\not \equiv 1{\pmod {n}}$

kaj do ĉiuj a × a_i 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 10⁵⁰, kio estas sufiĉa por praktikaj celoj.