Testul Nightingale-Strassen este un test de primalitate probabilistic descoperit în anii 1970 de Robert Martin Nightingale împreună cu Volker Strassen. [1] Testul determină întotdeauna corect că un număr prim este prim, dar pentru numerele compuse cu o anumită probabilitate poate da un răspuns incorect. Principalul avantaj al testului este că, spre deosebire de testul lui Fermat , recunoaște numerele Carmichael ca fiind compuse.
În secolul al XVII-lea, Fermat a dovedit o afirmație numită mai târziu Mica Teoremă a lui Fermat , care servește drept bază pentru testul de primalitate al lui Fermat:
Dacă n este prim și a nu este divizibil cu n , atunci .Această verificare pentru un n dat nu necesită mult calcul, dar invers nu este adevărat. Astfel, există numere Carmichael, care sunt compuse, pentru care afirmația dată în teorema mică a lui Fermat este valabilă pentru toate numerele întregi coprime cu un număr dat. În 1994, s-a demonstrat că există o infinitate de astfel de numere. [2] În legătură cu deficiența descoperită a testului Fermat, problema creșterii fiabilității testelor probabilistice a devenit de actualitate. Lehmann a fost primul care a propus un test care exclude numerele Carmichael ca fiind compuse. Acest neajuns este, de asemenea, absent în testele Solovey-Strassen și Miller-Rabin din cauza unui criteriu de abandon mai puternic decât teorema mică a lui Fermat. Independent unul de celălalt, D. Lemaire în 1976 și R. Nightingale, împreună cu F. Strassen în 1977, au demonstrat că nu există un analog al numerelor Carmichael, care sunt compuse și în același timp Euler pseudosimple. [3] Pe baza acestui fapt, a fost propus testul Solovay-Strassen pentru primalitate, a fost publicat în 1977, completări la acesta în 1978.
Testul Solovay-Strassen se bazează pe mica teoremă a lui Fermat și pe proprietățile simbolului Jacobi [4] :
Numerele compuse n care satisfac această comparație se numesc pseudoprime Euler-Jacobi în baza a .
Dovada [5]Algoritmul Solovay-Strassen [6] este parametrizat de numărul de runde k . În fiecare rundă, un număr a < n este ales aleatoriu . Dacă mcd ( a , n ) > 1, atunci se decide că n este compus. În caz contrar, se verifică validitatea comparației . Dacă nu este satisfăcut, atunci se ia decizia că n este compus. Dacă această comparație este valabilă, atunci a martor n este prim . Apoi se alege un alt a aleatoriu și se repetă procedura. După găsirea k martori de primalitate în k runde, se ajunge la concluzia că n este un număr prim cu probabilitate .
În pseudocod , algoritmul poate fi scris după cum urmează:
Intrare : > 2, testează numărul natural impar; , un parametru care determină acuratețea testului. Ieșire : compozit , înseamnă exact compus; probabil prim înseamnă că este probabil prim. pentru i = 1, 2, ..., : = întreg aleatoriu de la 2 la , inclusiv; dacă gcd (a, n) > 1, atunci : print , care este compus, și stop . if , then : ieșire care este un compus și stop . în caz contrar, derivă , care este prim cu probabilitate , și stop .Să verificăm numărul n = 19 pentru simplitate. Alegem parametrul de precizie k = 2.
k = 1 Alegem un număr aleatoriu a = 11; 2 < a < n - 1 Verificați starea gcd(a,n)>1 mcd(11,19)=1; apoi verificăm comparația . Am obținut că, prin urmare, trecem la următoarea iterație k = 2 Alegem un număr aleatoriu a = 5; 2 < a < n - 1 Verificați starea gcd(a,n)>1 mcd(5,19)=1; deci verificăm comparația și aceasta a fost ultima iterație, prin urmare concluzionăm că 19 este un număr prim cu o probabilitatenumele testului | probabilitate ( ca numărul să fie compus ) [7] | note |
---|---|---|
Fermă | nu recunoaște numerele Carmichael ca fiind compuse | |
Lehmann | ||
Privighetoarea - Strassen |
Testele probabilistice sunt utilizate în sisteme bazate pe problema de factorizare , cum ar fi RSA sau schema lui Rabin . Cu toate acestea, în practică, gradul de fiabilitate al testului Solovey-Strassen nu este suficient; în schimb, se utilizează testul Miller-Rabin . Mai mult, folosind algoritmi combinați, cum ar fi diviziunea de încercare și testul Miller-Rabin, cu alegerea corectă a parametrilor, puteți obține rezultate mai bune decât utilizarea fiecărui test separat. [7]
În 2005, la Conferința Internațională Bit+ „Tehnologii Informaționale -2005” A. A. Balabanov, A. F. Agafonov, V. A. Ryku au propus un test Solovay-Strassen modernizat. Testul Nightingale-Strassen se bazează pe calcularea simbolului Jacobi, care necesită timp echivalent cu . Ideea de îmbunătățire este că, în conformitate cu teorema de reciprocitate pătratică Gaussiană , mergeți la calculul valorii care este reciproca simbolului Jacobi, care este o procedură mai simplă. [8] .
Algoritmi teoretici numerelor | |
---|---|
Teste de simplitate | |
Găsirea numerelor prime | |
Factorizarea | |
Logaritm discret | |
Găsirea GCD | |
Modul de aritmetică | |
Înmulțirea și împărțirea numerelor | |
Calcularea rădăcinii pătrate |