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,

$a^{(p-1)/2}\equiv \left(\frac{a}{p}\right)(\mathrm{mod}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)²) uzante jakobian ĝeneraligon de leĝo de kvadrata reciprokeco.

Oni povas kontroli ĉu egaleco

$a^{(n-1)/2}\equiv \left(\frac{a}{n}\right)(\mathrm{mod}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 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

$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 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 $𝒪(k\times {\log }^{3}n)$, 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.