Brontekst bekijken van Solovay-Strassen-priemgetaltest

De '''Solovay-Strassen-priemgetaltest''' is een [[algoritme]] dat nagaat of een gegeven getal een [[priemgetal]] is of niet. De test is vergelijkbaar met de [[Miller-Rabin-priemgetaltest]] en de [[priemtest van Fermat]], die net als de Solovay-Strassen-test veelal worden gebruikt in de [[cryptografie]]. De test is opgesteld door [[Robert Solovay (wiskundige)|Robert Solovay]] en [[Volker Strassen]]. Het is een [[probabilisme|probabilistische]] test die bepaalt of een gegeven getal [[samengesteld getal|samengesteld]] is of [[waarschijnlijk priem]]. De test heeft veel betekend voor het [[RSA (cryptografie)|RSA]]-[[cryptosysteem]], maar is in vele opzichten minder goed dan de Miller-Rabin priemgetaltest.

== Theorie ==
Het principe van de Solovay-Strassen-test is hetzelfde als dat van de Miller-Rabin-test en de Fermattest. Er wordt een gelijkheid onderzocht waaraan priemgetallen voldoen, en nagegaan wordt of een gegeven getal hieraan voldoet.

=== Lemma ===
[[Leonhard Euler]] bewees in zijn [[Euler's criterium|Criterium]]<ref>[http://www.libraryofmath.com/euler-criterion.html Bewijs van Euler's criterium] {{en}}</ref> dat voor ''p'' een priemgetal en ''a'' een [[geheel getal]]:
:<math>\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}} \pmod{p}</math>
met <math>\left( \tfrac{a}{p}\right)</math> het [[Legendre-symbool]].

Het [[Jacobi-symbool]], <math>\left( \tfrac{a}{n}\right)</math>, is een algemene versie van het Legendre-symbool; ''n'' is een willekeurig oneven geheel getal groter dan 1. Het Jacobi-symbool kan worden gevonden door gebruik te maken van de [[wet van de kwadratische wederkerigheid]].

=== Het principe van de test ===
De gelijkheid die we controleren voor een te testen getal ''n'' is de volgende:
:<math>\left( \frac{a}{n} \right)\equiv a^{\frac{n-1}{2}} \pmod{n}</math>,
voor verschillende bases ''a''. Als ''n'' priem is, dan geldt de gelijkheid voor ieder geheel getal ''a''. Dus als we ''a'' [[willekeurig]] kiezen en we controleren de equivalentie, en we vinden een ''a'' waarvoor de equivalentie ''niet'' geldt, dan weten we dat ''n'' samengesteld is. Merk op dat dit niet de [[priemfactor|factorisatie]] van ''n'' geeft. Als ''a'' geeft dat ''n'' samengesteld is, dan heet ''a'' een ''Euler getuige'' voor ''n''; het is een getuige voor het feit dat ''n'' samengesteld is. Als ''n'' samengesteld is, maar de equivalentie geldt toch voor een ''a'', dan heet deze ''a'' een ''Eulerleugenaar'' voor ''n''.

== Voorbeeld ==
Nagegaan wordt of <math>n=221</math> een priemgetal is. Bepaal eerst <math>(n-1)/2=110</math>.

Kies een willekeurige <math>a<n</math>, bijvoorbeeld <math>a=47</math>. Dan is enerzijds
:<math>a^{(n-1)/2}=47^{110}\equiv -1 \pmod {221}</math>
en anderzijds:
:<math>\left(\tfrac{a}{n}\right) = \left(\tfrac{47}{221}\right)\equiv -1 \pmod {221}</math>.
Beide zijn dus aan elkaar gelijk, wat betekent dat ofwel 221 priem is, ofwel dat 47 een Eulerleugenaar is voor 221. Probeer daarom nog een andere willekeurige <math>a</math>, bijvoorbeeld <math>a=2</math>. Dit geeft:
:<math>a^{(n-1)/2}=2^{110}\equiv 30 \pmod {221}</math>.
Maar:
:<math>\left( \tfrac{a}{n}\right)=\left( \tfrac{2}{221}\right)\equiv -1 \pmod{221}</math>.
Hieruit volgt dat 2 een Eulergetuige is van het feit dat 221 samengesteld is. 47 was dus inderdaad een Eulerleugenaar voor 221. Merk op dat dit niets zegt over de [[priemfactor]]en van 221 (namelijk 13 en 17).

== Algoritme ==
Het algoritme kan in [[pseudocode]] als volgt worden beschreven:
 '''Invoer''': ''n'', een getal dat getest wordt op primaliteit; ''k'', een geheel getal, dat de nauwkeurigheid van de test bepaalt
 '''Uitvoer''': <u>samengesteld</u> als ''n'' samengesteld is, anders <u>waarschijnlijk priem</u>
 herhaal ''k'' keer:
    kies 1&nbsp;≤&nbsp;''a''&nbsp;≤&nbsp;''n''−1 willekeurig
    ''x'' ← <math>\left( \tfrac{a}{n}\right)</math>
    als ''x''&nbsp;=&nbsp;0 of ''a''<sup>(''n''−1)/2</sup> <math>\not\equiv</math> ''x'' (mod ''n'') dan uitvoer <u>samengesteld</u>
 uitvoer <u>waarschijnlijk priem</u>

== Nauwkeurigheid ==
Wanneer ''n'' een oneven samengesteld getal is, dan geldt dat ten minste de helft van alle ''a'' met ggd(''a'',''n'')&nbsp;=&nbsp;1 een Euler getuige is. Dit is als volgt te bewijzen: laat {''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>''m''</sub>} de Euler leugenaars zijn en ''a'' een Euler getuige. Dan geldt voor ''i''&nbsp;=&nbsp;1,2,...,''m'' dat:

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

Aangezien het volgende geldt:
:<math>\left(\frac{a}{n}\right)\left(\frac{a_i}{n}\right)=\left(\frac{a\cdot a_i}{n}\right),</math>

weten we nu ook dat

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

Hiermee volgt dat elke ''a''<sub>''i''</sub> een getal ''a''·''a''<sub>''i''</sub> geeft, dat ook een Euler getuige is.
Oftewel elke Euler leugenaar geeft een Euler getuige en is het aantal Euler getuigen groter dan of gelijk aan het aantal Euler leugenaars. Dus wanneer ''n'' samengesteld is, dan zijn ten minste de helft van alle ''a'' met ggd(''a'',''n'')&nbsp;=&nbsp;1 Euler getuigen.

== Externe link ==
* {{en}} [http://planetmath.org/encyclopedia/SolovayStrassenTest.html PlanetMath over Solovay-Strassen]

{{Appendix}}

[[Categorie:Priemgetaltest]]