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:

met  het Legendre-symbool.

Het Jacobi-symbool, , 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:
,
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  een priemgetal is. Bepaal eerst .

Kies een willekeurige , bijvoorbeeld . Dan is enerzijds

en anderzijds:
.
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 , bijvoorbeeld . Dit geeft:
.
Maar:
.
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 ← 
    als x = 0 of a(n−1)/2  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 {a1, a2, ..., am} de Euler leugenaars zijn en a een Euler getuige. Dan geldt voor i = 1,2,...,m dat:

Aangezien het volgende geldt:

weten we nu ook dat

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 
  PlanetMath over Solovay-Strassen

Priemgetaltest