Primeca provo de Fermat

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

La primeca provo de Fermat estas probableca provo por kontroli ĉu entjero estas verŝajna primo.

Koncepto[redakti | redakti fonton]

Malgranda teoremo de Fermat diras ke se p estas primo kaj a estas interprimo al p, 1≤a<p, do ap-1-1 estas dividebla per p aŭ per la alia skribmaniero

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

Se oni bezonas provi ĉ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 komponigita 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 komponigiteco de n.

Algoritmo kaj rula tempo[redakti | redakti fonton]

La algoritmo povas esti skribita kiel sekvas:

Enigoj: n: valoro por provo por primeco; k: parametro kiu difinas la kvanton de fojoj de provo por primeco
Eligo: "komponigita" se n estas komponigita, 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 "komponigita"
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 kvanto de fojoj de provoj de hazardaj a, kaj n estas la valoro kiun oni testas por primeco.

Problemoj[redakti | redakti fonton]

Estas certaj valoroj de n sciataj kiel nombroj de Carmichael por kiuj ĉiuj valoroj de a interprimaj al n estas neatestantoj. Kvankam nombroj de Carmichael estas maloftaj, estas sufiĉa kvanto de ili por ke primeca provo de Fermat estas ofte ne uzata, anstataŭe de ĝi estas uzataj ekzemple primeca provo de Miller-Rabin kaj primeca provo 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 a1, a2, ..., as 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 × ai por i = 1, 2 ... s estas atestantoj de Fermat.

Uzado[redakti | redakti fonton]

La ĉifrada programo PGP uzas ĉi tiun primecan provon. La ŝanco de tio ke PGP generas nombron de Carmichael estas malpli ol 1 el 1050, kio estas sufiĉa por praktikaj celoj.