Nightingale-Strassenin testi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 3. tammikuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 4 muokkausta .

Nightingale-Strassen-testi on todennäköisyyspohjainen primaalisuustesti, jonka Robert Martin Nightingale löysi 1970-luvulla yhdessä Volker Strassenin kanssa. [1] Testi määrittää aina oikein, että alkuluku on alkuluku, mutta yhdistelmäluvuille se voi jollain todennäköisyydellä antaa väärän vastauksen. Testin tärkein etu on, että toisin kuin Fermatin testi , se tunnistaa Carmichael-luvut yhdistelmälukuina.

Historia

1600-luvulla Fermat todisti lausunnon, jota myöhemmin kutsuttiin Fermatin pieneksi lauseeksi ja joka toimii Fermatin primaalisuustestin perustana :

Jos n on alkuluku ja a ei ole jaollinen n :llä , niin .

a^{n-1} \equiv 1\pmod{n}

Tämä tietyn n :n tarkistus ei vaadi paljon laskentaa, mutta päinvastoin ei pidä paikkaansa. Siten on olemassa Carmichael-lukuja, jotka ovat yhdistelmälukuja, joille Fermatin pienessä lauseessa annettu lause pätee kaikille tietyn luvun koprime-kokonaisluvuille. Vuonna 1994 osoitettiin, että tällaisia lukuja on äärettömän paljon. [2] Fermat-testin havaitun puutteen yhteydessä on tullut ajankohtaiseksi ongelma todennäköisyystestien luotettavuuden lisäämisestä. Lehmann ehdotti ensimmäisenä testiä, joka seuloa Carmichael-luvut yhdistelmänä. Tämä puute puuttuu myös Solovey-Strassenin ja Miller-Rabinin testeistä johtuen vahvemmasta poistumiskriteeristä kuin Fermatin pieni lause. Riippumatta toisistaan, D. Lemaire vuonna 1976 ja R. Nightingale yhdessä F. Strassenin kanssa vuonna 1977 osoittivat, että Carmichaelin luvuille, jotka ovat komposiittisia ja samalla pseudoyksinkertaisia, ei ole analogia. [3] Tämän perusteella ehdotettiin Solovay-Strassenin primaalisuustestiä, joka julkaistiin vuonna 1977, lisäyksiä siihen vuonna 1978.

Perustelut

Solovay-Strassenin testi perustuu Fermatin pieneen lauseeseen ja Jacobi-symbolin ominaisuuksiin [4] :

Jos n on pariton yhdistelmäluku , niin vertailun tyydyttävien kokonaislukujen a määrä , jotka vastaavat n :ää ja pienempiä kuin n , ei ylitä . $\textstyle a^{{(n-1)/2}}\equiv \left({\frac {a}{n}}\right){\pmod {n}}$ ${\frac {n}{2))$

Tämän vertailun toteuttavia yhdistelmälukuja n kutsutaan Euler-Jacobin pseudoalkuluvuiksi kannassa a .

Todiste [5]

Osoitetaan, että vertailu on välttämätön ja riittävä, jotta luku n olisi alkuluku. $a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}$

Välttämättömyys seuraa Eulerin kriteeristä Legendre - symbolille . Riittävyyden todistamiseksi käytämme ristiriitamenetelmää. Oletetaan, että n on komposiitti ja samalla tehdään vertailu . Tämä tarkoittaa , että n on Carmichaelin luku, joten missä on alkuluku i = 1,2, ...k

\forall a\in \mathbf {Z_{n}}

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

a^{n-1}=(a^{(n-1)/2})^{2}=\left({\frac {a}{n}}\right)^{2}

\left({\frac {a}{n}}\right)^{2}=1

a^{n-1}=1(modn)

{\displaystyle n=p_{1}p_{2}..p_{k))

{\displaystyle p_{i))

Oletetaan b sellainen, että Etsitään sellainen a , että: Sellainen on olemassa kiinalaisen jäännöslauseen mukaan ja kuuluu ryhmään , koska se on koprime n :lle . Tästä johtuu ristiriita sen tosiasian kanssa, että Olettamuksemme, että n on komposiitti, on siis väärä.

\left({\frac {b}{p_{1}}}\right)=-1(modn)

a={\begin{cases}b(mod{p_{1))),&{\mbox{if }}i{\mbox{= 1}}\\1(mod{p_{i}} ),&{\mbox{if }}i{\mbox{ = 2,...,k}}\end{cases}}

Z_{n}

\left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)\left({\frac {a}{p_ {2}}}\oikea)....\left({\frac {a}{p_{k}}}\right)=\left({\frac {a}{p_{1}}}\oikea )=\left({\frac {b}{p_{1}}}\right)=-1

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

\left({\frac {a}{n}}\right)=-1

a^{(n-1)/2}\equiv \ -1(modn)

a^{(n-1)/2}\equiv \ -1(modp_{1})

a^{(n-1)/2}\equiv \ -1(modp_{2})

a\equiv \ 1(modp_{i})

Todiste siitä, että tällaisten lukujen määrä ei ylitä n/2, löytyy mistä tahansa lukuteoreettisten algoritmien oppikirjasta. [neljä]

Solovay-Strassen-algoritmi

Solovay-Strassen-algoritmi [6] parametroidaan kierrosten lukumäärällä k . Jokaisella kierroksella valitaan satunnaisesti numero a < n . Jos gcd ( a , n ) > 1, niin päätetään, että n on komposiitti. Muussa tapauksessa vertailun oikeellisuus tarkistetaan . Jos se ei täyty, päätetään, että n on yhdistelmä. Jos tämä vertailu pitää paikkansa, a todistaa , että n on prime . Sitten valitaan toinen satunnainen a ja toimenpide toistetaan. Kun on löydetty k alkulukua k kierrokselta, päätellään, että n on alkuluku, jonka todennäköisyys on . $\textstyle a^{(n-1)/2}\equiv \left({a \over n}\right){\pmod {n))$ ${\displaystyle \textstyle 1-2^{-k))$

Pseudokoodissa algoritmi voidaan kirjoittaa seuraavasti:

Syöte : > 2, testaa pariton luonnollinen luku; , parametri, joka määrittää testin tarkkuuden. Tulos : komposiitti , tarkoittaa täsmälleen komposiittia; luultavasti prime tarkoittaa, että se on luultavasti prime.

n

k

n

n

i = 1, 2, ..., : = satunnainen kokonaisluku välillä 2 - , mukaan lukien; jos gcd (a, n) > 1, niin : print , joka on yhdistelmä, ja stop . if , then : tulos , joka on yhdistelmä , ja stop .

k

a

n-1

n

a^{(n-1)/2}\not \equiv \left({a \over n}\right){\pmod {n))

n

muuten johtaa , joka on prime todennäköisyydellä , ja lopeta .

n

{\displaystyle \textstyle 1-2^{-k))

Esimerkki algoritmin

Tarkistetaan yksinkertaisuuden vuoksi luku n = 19. Valitsemme tarkkuusparametriksi k = 2.

k = 1 Valitsemme satunnaisluvun a = 11; 2 < a < n - 1 Tarkista ehto gcd(a,n)>1 gcd(11,19)=1; sitten tarkistamme vertailun . Saimme sen, joten siirrymme seuraavaan iteraatioon

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

r=\left({\frac {a}{n}}\right)=\left({\frac {11}{19}}\right)=1

\textstyle s=a^{(n-1)/2}=11^{(19-1)/2}{\pmod {19}}=1

\textstyle r=s

k = 2 Valitsemme satunnaisluvun a = 5; 2 < a < n - 1 Tarkista ehto gcd(a,n)>1 gcd(5,19)=1; joten tarkistamme vertailun ja tämä oli viimeinen iteraatio, joten päätämme, että 19 on alkuluku, jolla on todennäköisyys

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

r=\left({\frac {a}{n}}\right)=\left({\frac {5}{19}}\right)=1

\textstyle s=a^{(n-1)/2}=5^{(19-1)/2}{\pmod {19}}=1

\textstyle r=s

{\näyttötyyli 1-2^{-2}}

Laskennallinen monimutkaisuus ja tarkkuus

Tarkkuus verrattuna muihin todennäköisyyspohjaisiin primaalisuustesteihin (tässä k on riippumattomien kierrosten lukumäärä)

testin nimi	todennäköisyys( että luku on yhdistelmä ) [7]	muistiinpanoja
Maatila	${\näyttötyyli 2^{-k))$	ei tunnista Carmichael-lukuja yhdistelmälukuina
Lehmann	${\näyttötyyli 2^{-k))$
Nightingale - Strassen	${\näyttötyyli 2^{-k))$

Kaikkien taulukossa annettujen testien laskelmien teoreettinen monimutkaisuus on arvioitu . [3] $O(\log^3n)$
Algoritmi vaatii operaatioita pitkillä kokonaisluvuilla . [yksi] $O(k\log _{2}m)$
Algoritmia toteutettaessa valitaan laskennan monimutkaisuuden vähentämiseksi luvut a väliltä 0 < a < c < n , missä c on vakio, joka on yhtä suuri kuin yhteen prosessorirekisteriin sopivan luonnollisen luvun suurin mahdollinen arvo. [6]

Sovellus

Todennäköisyystestejä käytetään faktorointiongelmaan perustuvissa järjestelmissä , kuten RSA tai Rabinin kaava . Käytännössä Solovey-Strassen-testin luotettavuusaste ei kuitenkaan ole riittävä, vaan käytetään Miller-Rabin-testiä . Lisäksi käyttämällä yhdistettyjä algoritmeja, kuten kokeilujakoa ja Miller-Rabin-testiä, oikealla parametrivalinnalla voit saada parempia tuloksia kuin käyttämällä jokaista testiä erikseen. [7]

Testaa parannusta

Vuonna 2005 kansainvälisessä Bit+-konferenssissa "Informational Technologies -2005" A. A. Balabanov, A. F. Agafonov, V. A. Ryku ehdottivat modernisoitua Solovay-Strassen-testiä. Nightingale-Strassen-testi perustuu Jacobi-symbolin laskemiseen, joka vie aikaa, joka vastaa . Parantamisen idea on, että Gaussin toisen asteen vastavuoroisuuslauseen mukaisesti siirrytään Jacobi-symbolin käänteisarvon laskemiseen, mikä on yksinkertaisempi menettely. [8] . $\log _{2}n$ $\left({\frac {n}{a))\right)$

Katso myös

Pseudoprime

Muistiinpanot

↑ 1 2 Solovay, Robert M. ja Volker Strassen. Nopea Monte-Carlo-testi primaalisuudelle // SIAM Journal on Computing : päiväkirja. - 1977, jätetty vuonna 1974. - Voi. 6 , ei. 1 . - s. 84-85 . - doi : 10.1137/0206006 .
↑ WR Alford, A. Granville, C. Pomerance. Carmichael-lukuja on äärettömän monta // Annals of Mathematics : Journal . - 1994. - Voi. 139 . - s. 703-722 . - doi : 10.2307/2118576 . Arkistoitu alkuperäisestä 4. toukokuuta 2012.
↑ 1 2 Cheryomushkin, 2001 , s. 48.
↑ 1 2 Nesterenko, 2011 , s. 82.
↑ N.Yu. Kultainen . Luentoja tietokonealgebrasta. Luento 6. Carmichaelin lause Nightingale - Strassen testi. Arkistoitu 4. marraskuuta 2014 Wayback Machinessa
↑ 1 2 Nesterenko, 2011 , s. 84.
↑ 1 2 B. Schneier Sovellettu kryptografia - M.: TRIUMPH, 2002. — Luku 11.
↑ Balabanov A. A., Agafonov A. F., Ryku V. A. Algoritmi nopeaan avainten luomiseen RSA-salausjärjestelmässä. Arkistokopio , päivätty 5. marraskuuta 2014, Wayback Machine - Bulletin of Scientific and Technical Development, 2009 nro 7(23). - S. 11.

Kirjallisuus

Koblitz N. Numeroteorian ja kryptografian kurssi . - 2. - M . : TVP Scientific Publishing House, 2001. - S. 149 - 160. - 254 s. — ISBN 5-94057-103-4 .
Nesterenko A. Johdatus nykyaikaiseen kryptografiaan, lukuteoreettiset algoritmit . - 2011. - S. 79 - 90. - 190 s. - ISBN 978-5-94506-320-4 .
Cheremushkin AV Luennot aritmeettisista algoritmeista kryptografiassa . - M. : MTSNMO , 2001. - S. 42 - 59. - 104 s. — ISBN 5-94057-060-7 . Arkistoitu 31. toukokuuta 2013 Wayback Machinessa
Salomaa A. Julkisen avaimen salaus / Per. englannista. I.A. Vihljantsev. - M .: Mir, 1995. - S. 176 - 184. - 318 s. — ISBN 5-03-001991-X . Arkistoitu 19. marraskuuta 2011 Wayback Machinessa

Lukuteoreettiset algoritmit
Yksinkertaisuustestit	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saksi Nightingale - Strassen
Alkulukujen löytäminen	Iterointi jakajien yli Eratosthenesin seula Atkinin seula Seula Sundarama
Faktorisointi	Iterointi jakajien yli Fermat menetelmä p −1 Pollardin menetelmä Pollardin ρ-algoritmi Lehmannin menetelmä Elliptisen käyrän menetelmä (Lenstran algoritmi) Dixonin algoritmi Neliömäinen seula
Diskreetti logaritmi	Gelfond-Shanks -algoritmi Polig-Hellman-algoritmi Pollardin ρ-menetelmä Pollardin kenguru-algoritmi Adlemanin algoritmi COS-algoritmi
GCD:n löytäminen	Eukleideen algoritmi Kehittynyt algoritmi Binäärinen algoritmi
Modulo-aritmetiikka	Montgomeryn algoritmi Kiinan jäännöslause
Lukujen kerto- ja jakolasku	Karatsuba-algoritmi Toom-Cook-algoritmi Schönhage-Strassen-algoritmi Fuhrer-algoritmi Harvey-van der Hoeven-algoritmi Burnickel-Ziegler-algoritmi
Neliöjuuren laskeminen	Tonelli-Shanks-algoritmi Berlekamp-Rabin-algoritmi