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 en Volker Strassen. Het is een probabilistische test die bepaalt of een gegeven getal samengesteld is of waarschijnlijk priem. De test heeft veel betekend voor het 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 Criterium 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

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 Eulerleugenaar voor n.

Voorbeeld

Nagegaan wordt of $n=221$ een priemgetal is. Bepaal eerst $(n-1)/2=110$.

Kies een willekeurige $a<n$, bijvoorbeeld $a=47$. Dan is enerzijds

$a^{(n-1)/2}=47^{110}\equiv -1{\pmod {221}}$

en anderzijds:

$\left({\tfrac {a}{n}}\right)=\left({\tfrac {47}{221}}\right)\equiv -1{\pmod {221}}$.

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 $a$, bijvoorbeeld $a=2$. Dit geeft:

$a^{(n-1)/2}=2^{110}\equiv 30{\pmod {221}}$.

Maar:

$\left({\tfrac {a}{n}}\right)=\left({\tfrac {2}{221}}\right)\equiv -1{\pmod {221}}$.

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 priemfactoren 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: samengesteld als n samengesteld is, anders waarschijnlijk priem
herhaal k keer:
   kies 1 ≤ a ≤ n−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

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 {a₁, a₂, ..., a_m} 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 a_i een getal a·a_i 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

• (en) PlanetMath over Solovay-Strassen

Bronnen, noten en/of referenties