Primeco-testo 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 komponita aŭ verŝ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 

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 

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.

Kategorio:Modula aritmetiko
Kategorio:Primeco-testoj