A Solovay-Strassen prímteszt miatt Robert Solovay és Volker Strassen , egy prímteszt , azaz, olyan folyamat, amely meghatározza, hogy egy páratlan szám jelentése vegyület vagy elsődleges . Ez egy valószínűségi teszt , amely csak bizonyos valószínűséggel garantálja a tesztelt szám elsőbbségét (amit olyan közel 1-re tehetünk, amennyit csak akarunk).
A Soloway-Strassen teszt a számelmélet néhány alapjára épül, amelyeket az alábbiakban felidéztünk.
A Legendre szimbólum a p prímre 0, ha p többszöröse , 1, ha a modulo p négyzet, és –1 másképp.
Legyen n lehet egy páratlan egész szám nagyobb, mint 2, és n = annak felbontása prímosztója. Ezután az egész , a szimbóluma Jacobi általánosítása szimbóluma Legendre amelyet érdemes :, ahol a szimbólumai Legendre.
A Legendre szimbólumra, vagyis minden p páratlan prímszámra Euler kritériuma ezt mondja . Ez annál is inkább igaz, ha a Legendre szimbólumát Jacobi szimbólumára cseréljük. A Jacobi szimbólum azonban gyorsan kiszámítható az egészre ( a másodfokú kölcsönösség törvényének egyszerű általánosításával ).
Annak megállapításához, hogy egy adott páratlan egész szám prím-e, nagyszámú véletlenszerű érték esetén tesztelhetjük , hogy a kongruencia
elégedett. Ha hamis egy bizonyos egész számra , akkor tudjuk, hogy ez nem elsődleges.
Ugyanakkor, csakúgy, mint a Fermat-prímtesztnél , vannak „hazugok” is. Egy értéket akkor hívunk Euler hazugnak, ha az egyenlőség teljesül, noha az n összetett. Az Euler-tanú olyan érték, amelynél az egyenlőség nem teljesül, ezért tanúja annak a ténynek, hogy n összetett.
Ellentétben Fermat prímteszt, minden kompozit egész szám n , legalább a fele az összes a jelentése Euler kontrollok. Ezért nincs olyan n érték, amelyre mind hazugok lennének, míg a Fermat tesztben Carmichael számok vannak.
Az algoritmus a következőképpen írható:
Bemenetek : n : páratlan egész szám, amelynek elsődlegességét meg akarjuk tudni; k : a Jacobi szimbólum kiszámításának maximális száma. Kimenet : vegyület, ha n összetett, egyébként valószínűleg elsődleges ismételje meg k- szor: véletlenszerűen válasszon 2 és n - 1 között ha x = 0, vagy úgy adja vissza a vegyületet valószínűleg először tér visszaHasználata gyors moduláris hatványozás algoritmusokat , a legrosszabb esetben időbonyolultsága ezen algoritmus egy O ( k × log 3 n ), ahol k jelentése a maximális számú alkalommal véletlenszerűen húzni egész szám kiszámításához Jacobi szimbólum vele, és n jelentése az az érték, amelynek elsődlegességét meg akarjuk vizsgálni. Annak a valószínűsége, hogy az algoritmus meghibásodik, vagyis annak a valószínűsége, hogy n összeáll annak tudatában, hogy az algoritmus azt mondja, hogy elsődleges, kisebb, mint , -val (és nem 2 -m, mint egyes szerzőknél tapasztalhatjuk, ami valójában annak a valószínűsége, hogy az algoritmus választ, hogy n prím, ha nem. van két nagyságrenddel a két valószínűség tipikus értékei n !)
A kriptográfiai alkalmazásokban , ha kellően nagy k értéket választunk , például 100, akkor valószínűsége, hogy az algoritmus téves, olyan kicsi, hogy a tesztnek ellenálló számot elsődlegesnek tekinthetjük, és aggodalom nélkül használhatjuk a kriptográfiai alkalmazásokban.
1980-tól kezdve a Solovay-Strassen tesztet a gyakorlatban Miller-Rabin prímteszt váltotta fel , amely hatékonyabb, mert hasonló kritériumon alapszik, de csak négyszer ad hamis pozitívat. Amikor n nem prím.
Ha a 2020-ban nem bizonyított általánosított Riemann-hipotézis igaz, akkor bármely összetett szám kevesebb, mint egy Euler-tanút ismer be . A Solovay-Strassen prímteszt ebben az esetben adaptálható a komplexitás determinisztikus tesztjéhez , ezért a polinom a számjegyeinek számában .