Primeca provo de Solovay-Strassen

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

La primeca provo de Solovay-Strassen estas primeca provo, ellaborita de Robert M. Solovay kaj Volker Strassen. Ĝi estas probableca provo por kontroli ĉu entjero estas komponitaverŝajne primo. Ĝi estas plejparte anstataŭigita en uzado per primeca provo de Miller-Rabin, sed havas grandan historian gravecon en montrado de praktika uzebleco de ĉifrosistemo RSA.

Konceptoj[redakti | redakti fonton]

Eŭlero pruvis ke por primo p kaj iu entjero a,

a^{(p-1)/2} \equiv \left(\frac{a}{p}\right) \pmod p

kie

\left(\frac{a}{p}\right)

estas la simbolo de Legendre. La jakobia simbolo estas ĝeneraligo de la simbolo de Legendre al

\left(\frac{a}{n}\right)

kie n povas esti ĉiu nepara entjero. La jakobia simbolo povas esti komputita en tempo O((log n)2) uzante jakobian ĝeneraligon de leĝo de kvadrata reciprokeco.

Oni povas kontroli ĉu egaleco

 a^{(n-1)/2} \equiv \left(\frac{a}{n}\right) \pmod n

veras por diversaj valoroj de a. Se n estas primo tiam ĉi tiu kongrueco estas veras por ĉiuj a. Tiel, se oni prenas valorojn de a hazarde kaj provas la egalecon, tiam tuj kiam oni trovas valoron a kiu malverigas la egalkongruecon oni povas konkludi ke n estas ne primo (sed ĉi tio ne donas faktorigon de n).

Valoro a estas la eŭlera atestanto se la pli supre donita egaleco kun la jakobia simbolo ne veras je a, do la valoro a estas atestanto de komponigiteco de n. Malsimile al primeca provo de Fermat, por ĉiu komponigita nepara n almenaŭ duono de ĉiuj

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

estas atestantoj de komponigiteco. Do, ne estas neparaj komponigitaj n sen atestantoj, do ne ekzistas analogoj de nombroj de Carmichael por primeca provo de Fermat.

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]
x ← (a/n)
se x = 0 aŭ a(n-1)/2 mod n ≠ x tiam redoni rezulton "komponigita"
redoni rezulton "verŝajne primo"

Uzante rapidajn algoritmojn por modula potencigo, la rula tempo de ĉi tiu algoritmo estas \mathcal O(k \times \log^3 n), kie k estas la kvanto de provoj de hazardaj a, kaj n estas la testata nombro. La probablo de malsukceso de la algoritmo detekti komponigitan nombron estas 2-k. Por celoj de ĉifrado se oni prenas sufiĉe grandan valoron de k, ekzemple 100, la ŝanco de uzo de komponigita nombro anstataŭ primo estas sufiĉe malgranda.