Solovay-Strassen-priemgetaltest

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

De Solovay-Strassen-priemgetaltest is een priemgetaltest: een algoritme dat bepaalt of een gegeven getal priem is of niet. Het 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 en Volker Strassen. Het is een probabilistische test die bepaalt of een gegeven getal samengesteld is of waarschijnlijk priem. De test is in vele opzichten minder goed dan de Miller-Rabin priemgetaltest, hoewel het veel heeft betekend voor het RSA-cryptosysteem.

Theorie[bewerken]

Het principe van de Solovay-Strassen-test is hetzelfde als die van de Miller-Rabin-test en de Fermattest: we beschouwen een gelijkheid waarvan we weten dat priemgetallen eraan voldoen, en we controleren of een gegeven getal hier ook aan voldoet.

Lemma[bewerken]

Leonhard Euler bewees in zijn Criterium[1] dat voor p een priemgetal en a een geheel getal:

\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}} \pmod{p}

met \left( \tfrac{a}{p}\right) het Legendre-symbool.

Het Jacobi-symbool, \left( \tfrac{a}{n}\right), 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[bewerken]

De gelijkheid die we controleren voor een te testen getal n is de volgende:

\left( \frac{a}{n} \right)\equiv a^{\frac{n-1}{2}} \pmod{n},

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 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 Euler leugenaar voor n.

Voorbeeld[bewerken]

Stel dat we willen bepalen of n = 221 priem is. Allereerst is (n−1)/2 = 110.

Kies een willekeurige a < n, bijvoorbeeld a = 47. Controleer de equivalentie:

  • a(n−1)/2 (mod n) = 47110 (mod 221) = −1 (mod 221)
  • \left( \tfrac{a}{n}\right)  = \left( \tfrac{47}{221}\right)  = −1 (mod 221).

Dit betekent ofwel dat 221 priem is, ofwel dat 47 een Euler leugenaar is voor 221. Daarom proberen we nog een willekeurige a, bijvoorbeeld a = 2. Dit geeft:

  • a(n−1)/2 (mod n) = 2110 (mod 221) =  30 (mod 221)
  • \left( \tfrac{a}{n}\right)  = \left( \tfrac{2}{221}\right)  =  −1 (mod 221).

Hieruit volgt dat 2 een Euler getuige is van het feit dat 221 samengesteld is. 47 was dus inderdaad een Euler leugenaar voor 221. Merk op dat dit niets zegt over de priemfactoren van 221 (namelijk 13 en 17).

Algoritme[bewerken]

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: samengesteld als n samengesteld is, anders waarschijnlijk priem
herhaal k keer:
   kies 1 ≤ an−1 willekeurig
   x\left( \tfrac{a}{n}\right)
   als x = 0 of a(n−1)/2 \not\equiv x (mod n) dan uitvoer samengesteld
uitvoer waarschijnlijk priem

Nauwkeurigheid[bewerken]

Wanneer n een oneven samengesteld getal is, dan geldt dat ten minste de helft van alle a met ggd(a,n) = 1 een Euler getuige is. Dit is als volgt te bewijzen: laat {a1, a2, ..., am} de Euler leugenaars zijn en a een Euler getuige. Dan geldt voor i = 1,2,...,m dat:

(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}.

Aangezien het volgende geldt:

\left(\frac{a}{n}\right)\left(\frac{a_i}{n}\right)=\left(\frac{a\cdot a_i}{n}\right),

weten we nu ook dat

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

Hiermee volgt dat elke ai een getal a·ai 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) = 1 Euler getuigen.

Externe link[bewerken]

Bronnen, noten en/of referenties