Primeco-testo de Solovay-Strassen

(Alidirektita el Primeca provo de Solovay-Strassen)

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

Konceptoj

redakti

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

 

kie

 

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

 

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

 

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 kontrolas 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 primeco-testo de Fermat, por ĉiu komponigita nepara n almenaŭ duono de ĉiuj

 

estas atestantoj de komponigiteco. Do, ne estas neparaj komponigitaj n sen atestantoj, do ne ekzistas analogoj de nombroj de Carmichael por primeco-testo de Fermat.

Algoritmo kaj rula tempo

redakti

La algoritmo povas esti skribita kiel sekvas:

Enigoj: n: valoro por testi primecon; 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  , kie k estas la kvanto de provoj por 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.