Vidi fonton por Primeco-testo de Solovay-Strassen

La '''primeco-testo de Solovay-Strassen''' estas [[primeco-testo]], ellaborita de Robert M. Solovay kaj Volker Strassen. Ĝi estas [[hazardigita algoritmo|probableca]] testo por kontroli, ĉu [[entjero]] estas [[komponita nombro|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 ==

[[Leonhard Euler|Eŭlero]] pruvis ke por [[primo]] ''p'' kaj iu entjero ''a'',

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

kie

:<math>\left(\frac{a}{p}\right)</math>

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

:<math>\left(\frac{a}{n}\right)</math>

kie ''n'' povas esti ĉiu nepara entjero. La jakobia simbolo povas esti komputita en tempo ''O((log n)<sup>2</sup>)'' uzante jakobian ĝeneraligon de [[kvadrata reciprokeco|leĝo de kvadrata reciprokeco]].

Oni povas kontroli ĉu egaleco

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

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 [[entjera faktorigo|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

:<math>a \in (\mathbb{Z}/n\mathbb{Z})^* </math>

estas atestantoj de komponigiteco. Do, ne estas neparaj komponigitaj ''n'' sen atestantoj, do ne ekzistas analogoj de [[nombro de Carmichael|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<sup>(n-1)/2</sup> 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 <math>\mathcal O(k \times \log^3 n)</math>, 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<sup>−k</sup>''. 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]]