Yksinkertaisuustesti

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 21.5.2020 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Kysymys siitä, onko luonnollinen luku alkuluku , tunnetaan primaalisuusongelmana. $N$

Primaliteettitesti (tai primaalitesti) on algoritmi , joka ottaa luvun syötteeksi sallii joko olla vahvistamatta oletusta luvun koostumuksesta tai vahvistaa tarkasti sen yksinkertaisuuden. Toisessa tapauksessa sitä kutsutaan todelliseksi primaalisuustestiksi. Ensisijaisuustesti on siis vain hypoteesi , että jos algoritmi ei vahvista oletusta, että luku on yhdistelmä , niin tämä luku voi olla alkuluku tietyllä todennäköisyydellä . Tämä määritelmä merkitsee vähemmän luottamusta testituloksen yhteensopivuuteen todellisen asioiden kanssa kuin todellinen primaalisuustesti, joka antaa matemaattisesti varmennetun tuloksen. $N$ $N$

Johdanto

Diskreetin matematiikan ongelmat ovat matemaattisesti monimutkaisimpia . Yksi niistä on tekijöiden jakamisen ongelma , joka koostuu luvun tekijöiden jakamisen löytämisestä alkutekijöiksi. Sen ratkaisemiseksi sinun on löydettävä alkuluvut, mikä johtaa yksinkertaisuusongelmaan. Primaalisuustestitehtävä kuuluu monimutkaisuusluokkaan P , eli sen ratkaisemiseen tarvittavien algoritmien ajoaika riippuu polynomiaalisesti syötetietojen koosta, mikä todistettiin vuonna 2002 . Tekijöintiongelmalle on olemassa samanlainen, mutta todistamaton lausunto .

Jotkut matematiikan sovellukset, joissa käytetään kertoimia, vaativat sarjan erittäin suuria satunnaisesti valittuja alkulukuja. Algoritmi niiden saamiseksi Bertrandin postulaatin perusteella :

Algoritmi:

Syöttö : luonnollinen luku $N$
Ratkaisu (etsi satunnaista alkulukua P)
1. $P\gets$ Funktio , jolla generoidaan mielivaltainen luonnollinen luku segmentille $[N,2N]$
2. Jos komposiitti, niin $P$
  1. $P\vasen \,P+1$
  2. Jos sitten $P = 2N$
    1. $P\leftarrow \,N$
3. Palauttaa " - satunnainen alkuluku" $P$

Aikaa ongelman ratkaisemiseen tällä algoritmilla ei ole määritelty, mutta on suuri todennäköisyys, että se on aina polynomi, kunhan alkulukuja on tarpeeksi ja ne jakautuvat enemmän tai vähemmän tasaisesti . Yksinkertaisten satunnaislukujen osalta nämä ehdot täyttyvät.

Tiedetään ( Eukleideen lause ), että alkulukujen joukko on ääretön. Dirichlet'n lause ( 1837 ) sanoo, että jos gcd , niin modulon kanssa yhteneviä alkulukuja on äärettömän monta . Toisin sanoen alkuluvut jakautuvat tasaisesti jäännösluokkiin Euler - funktion [1] mukaisesti mille tahansa arvolle . Jos alkuluvut ovat kuitenkin jakautuneet tasaisesti, mutta niitä on hyvin vähän, haku ei välttämättä ole käytännössä mahdollista. Tämän toisen ongelman ratkaisemiseksi käytämme alkulukulausetta ( 1896 ), jonka mukaan alkulukujen määrä välissä kasvaa . Tämä luku pyrkii äärettömään melko nopeasti, mistä voimme päätellä, että suurillakin arvoilla on melko suuri todennäköisyys ( ) löytää satunnainen alkuluku. Tästä voimme päätellä, että edellä kuvattu algoritmi voi antaa vastauksen polynomiajassa, jos on olemassa polynomialgoritmi, jonka avulla voimme varmistaa mielivaltaisen suuren luvun yksinkertaisuuden , mikä johtaa primaalisuusongelmaan. $(a,n) = 1$ $a$ $n$ $modn$ $\varphi (n)$ $n$ $[2,n]$ $n$ $n/log(n)$ $n$ $1/ln(n)$ $n$

Historiallista tietoa

Ensimmäinen maininta alkuluvuista tunnetaan Eukleideesta ( 3. vuosisadalla eKr .). Samaan aikaan Eratosthenes ( II vuosisadalla eKr. ) keksi ensimmäisen algoritmin alkulukujen löytämiseksi, ja se tunnetaan nykyään Eratosthenesin seulana . Sen olemus on "seulan" jo löytämien muiden alkulukujen peräkkäinen poissulkeminen kokonaislukujen luettelosta moninkertaisiin [ 2] . Paljon myöhemmin arabimatemaatikko Ibn al-Banna ehdotti kokonaislukujen luettelemista aina , vaan asti , mikä mahdollisti operaatioiden määrän vähentämisen. Tämän menetelmän haittana on, että sen sijaan, että se tarkastaisi tietyn luvun yksinkertaisuuden vuoksi, se tarjoaa peräkkäisen luettelon [3] kaikista kokonaisluvuista aina , ja on siksi tehoton ja vaatii huomattavaa laskentatehoa . $yksi$ $n$ $2,3,5$ $n$ ${\sqrt {n}}$ $n$ ${\sqrt {n}}$

1200- luvun alussa Leonardo Pisalainen , joka tunnetaan nimellä Fibonacci, ehdotti numerosarjaa (nimetty hänen mukaansa), jonka yksi ominaisuuksista on, että -. Fibonacci - luku voi olla vain alkuluku alkulukuja lukuun ottamatta . Tätä ominaisuutta voidaan käyttää testattaessa Fibonacci-lukujen ensisijaisuutta. Hän myös, ibn al-Bannasta riippumatta, ehdotti menetelmää numeroiden tarkistamiseksi yksinkertaisuuden vuoksi. Tämä algoritmi on tosi (tai epätodennäköinen), koska vastaus saadaan aina, mutta se on erittäin tehoton. $n$ $F_{n}$ $n$ $n = 4$

Ensimmäinen, joka käytti numeroiden välisiä suhteita primaalisuuden määrittämiseen, oli Pietro Antonio Cataldi työssään täydellisistä numeroista. Täydellisiä lukuja ovat ne, jotka ovat yhtä suuria kuin omien jakajiensa summa. Ensimmäiset seitsemän täydellistä lukua ovat 6, 28, 496, 8128, 33550336, 8589869056 ja 137438691328. Cataldi totesi, että jos luku on alkuluku ja luku on myös alkuluku, niin luku on täydellinen. $n$ $2^{n}-1$ $2^{{n-1}}(2^{n}-1)$

Ranskalainen matemaatikko Marin Mersenne tutki 1600-luvulla muotoa [4] , joka myöhemmin nimettiin Mersennen numeroiksi hänen kunniakseen . Mersenne havaitsi, että ensimmäisistä 257 Mersennen luvusta vain 11 on alkulukua (n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 ja 257). Näin tehdessään hän teki useita virheitä ( ei ole alkuluku p = 67 tai 257, ja on p = 61, 89 ja 107). Alkulukujen etsiminen Mersennen lukujen joukosta on melko yksinkertaista Luc-Lehmer-testin ansiosta, jonka avulla voit löytää ratkaisun suhteellisen nopeasti. Tästä syystä Mersennen luvut ovat suurimmat tällä hetkellä tunnetuista alkuluvuista. Mersennen ja Fermat'n välisessä kirjeenvaihdossa esitettiin useita muita alkulukuja koskevia ajatuksia [4] . $2^{n}-1$ $2^{n}-1$

Joten Fermat havaitsi, että jos kokonaisluku ei ole jaollinen alkuluvulla , niin luku on aina jaollinen ( Fermatin pieni lause ). Euler yleisti myöhemmin lauseen . Useat primaalisuustestit perustuvat Fermatin pieneen lauseeseen. Fermat ehdotti myös, että kaikkien luonnollisten lukujen muodon numerot ovat alkulukuja . Tämä pätee todellakin . Euler löysi vastaesimerkin tälle väitteelle . Fermat-lukujen primaalisuuden testaamiseksi on olemassa tehokas Pepin-testi . Tähän mennessä uusia Fermat-alkulukuja ei ole löydetty. $a$ $s$ $a^{{p-1}}-1$ $s$ $2^{2^{k}}+1$ $k$ $k=0,1,2,3,4$ $2^{2^{5}}+1=4294967297=641\cdot 6700417$

Muiden tiedemiesten joukossa Euler, Legendre , Gauss käsittelivät numeroiden yksinkertaisuutta . Merkittäviä tuloksia primaalisuuden ongelman ratkaisemisessa saavutti ranskalainen matemaatikko Édouard Lucas työssään Fermat- ja Mersennen numeroista. Se on hänen antamiensa Mersennen lukujen yksinkertaisuuden kriteeri, joka tunnetaan nykyään Lucas-Lehmerin testinä.

Vuonna 2002 kehitettiin deterministinen polynomiprimaalisuustesti, Agrawal-Kayal-Saxena testi . Sen ilmestymisen ennusti polynomisten ensisijaisuusvarmenteiden olemassaolo ja sen seurauksena se tosiasia, että numeron primaalisuuden tarkistamisen ongelma kuului samanaikaisesti NP- ja co -NP- luokkiin .

Todelliset primaalisuustestit

Olemassa olevat algoritmit luvun primaalisuuden testaamiseksi voidaan jakaa kahteen luokkaan: todellisen primaalisuuden testit ja todennäköisyyspohjaisuustestit. Tositestit laskelmien tuloksena paljastavat aina luvun yksinkertaisuuden tai koostumuksen tosiasian, todennäköisyystesti antaa vastauksen luvun koostumuksesta tai sen koostumattomuudesta jollain todennäköisyydellä [2] [4] . Yksinkertaisesti sanottuna todennäköisyyspohjainen algoritmi sanoo, että luku ei todennäköisesti ole yhdistelmä, mutta lopulta se voi osoittautua joko alkulukuksi tai yhdistelmäksi. Luvut, jotka täyttävät todennäköisyyspohjaisen primaalisuustestin, mutta ovat yhdistelmänä, kutsutaan pseudoalkuluvuiksi [1] . Yksi esimerkki tällaisista luvuista ovat Carmichael-luvut [3] . Voit myös nimetä Euler-Jacobi-luvut Solovay-Strassen-testille ja Lucasin pseudoalkuluvuille. $\epsilon$

Yksi esimerkki todellisista primaalisuustesteistä on Luc - Lehmerin testi Mersennen numeroille . Tämän testin ilmeinen haittapuoli on, että se koskee vain tiettyjä lukuja. Muita esimerkkejä ovat ne, jotka perustuvat Fermatin pieneen lauseeseen :

Pepinin testi Fermat - luvuille .
Prothin lause Prothin luvuille .
Agrawal-Kayala-Saxene testi , ensimmäinen polynomin primaalisuustesti.
Luc-Lehmer-Riesel-testi .

Yhtä hyvin kuin:

jakajan iterointimenetelmä .
Wilsonin lause .
Pocklingtonin kriteeri .
Millerin testi .
Adleman-Pomerans-Rumeli testi , parannettu [5] Cohenin ja Lenstroyn toimesta
Primaalisuustesti elliptisiä käyriä käyttäen .

Todennäköisyyspohjaiset primaalisuustestit

Tämä luokka sisältää:

Yksinkertaisuustestit kryptografiassa

Tällä hetkellä alkulukuja käytetään laajalti tietoturvan alalla. Ensinnäkin tämä johtuu julkisen avaimen salausmenetelmän keksimisestä, jota käytetään tiedon salauksessa ja sähköisissä digitaalisissa allekirjoitusalgoritmeissa . Tällä hetkellä elliptisiä käyriä käyttävän digitaalisen allekirjoituksen muodostamisessa käytettyjen alkulukujen koko on standardien mukaan GOST R 34.10-2012 mukaisesti vähintään 254 bittiä. Tällaisille suurille luvuille kysymys luvun alkuasteen määrittämisestä on erittäin vaikeaa. Yksinkertaiset menetelmät, kuten laskentamenetelmä, eivät sovellu käyttöön, koska ne vaativat erittäin paljon laskentaresursseja ja paljon aikaa [6] .

Myös luvun ensisijaisuuden määrittäminen on välttämätöntä, kun murretaan RSA-algoritmilla salattua tai allekirjoitettua tietoa . Tällaisen viestin avaamiseksi on välttämätöntä pystyä hajottamaan luku kahdeksi alkutekijäksi, mikä on ei-triviaali tehtävä suurille luvuille.

Toisaalta, kun luodaan avaimia julkisen avaimen salausjärjestelmille , sähköisille allekirjoitusjärjestelmille jne., käytetään suuria näennäissatunnaisia alkulukuja. Esimerkiksi Diffie-Hellman-protokollaa käytettäessä on oltava alkuluku, joka määrittää lopullisen kentän . Siksi tehokkaan primaalisuustestin käyttö mahdollistaa tällaisten avainten generointialgoritmien luotettavuuden lisäämisen.

Katso myös

Muistiinpanot

↑ 1 2 Kormen T., Leiser C. Algoritmit. Rakentaminen ja analyysi. - M .: MTSNMO, 2002. - S. 765-772.
↑ 1 2 Vasilenko O. N. Lukuteoreettiset algoritmit kryptografiassa. - M .: MTSNMO, 2003. - 328 s.
↑ 1 2 Crandall R., Pomerance C. Alkuluvut : laskennallinen näkökulma. - Springer, 2005.
↑ 1 2 3 Donald Knuth . Ohjelmoinnin taito, osa 2. Johdetut algoritmit. - M . : "Williams" , 2007.
↑ Nesterenko Yu. V. Johdatus kryptografiaan. - Peter, 2001. - 288 s.
↑ B. Schneier. Sovellettu kryptografia. - S. 296-300.

Kirjallisuus

Vasilenko O. N. Luku 1. Numeroiden testaus primaalisuuden varalta ja suurten alkulukujen muodostaminen // Lukuteoreettiset algoritmit kryptografiassa . - M. : MTSNMO, 2003. - S. 12-56. — 328 s. — ISBN 5-94057-103-4 . Arkistoitu 27. tammikuuta 2007 Wayback Machinessa
Nesterenko Yu. V. Luku 4.6. Kuinka tarkistaa suuri määrä yksinkertaisuuden vuoksi // Johdatus kryptografiaan / Toim. V. V. Jaštšenko. - Peter, 2001. - 288 s. - ISBN 5-318-00443-1 . Arkistoitu 25. helmikuuta 2008 Wayback Machinessa
Schneier B. Osa 3. Salausalgoritmit. Luku 11 11.5. Alkulukujen luominen // Sovellettu kryptografia. Protokollat, algoritmit, lähdekoodi C-kielellä = Applied Cryptography. Protokollat, algoritmit ja lähdekoodi julkaisussa C. - M . : Triumph, 2002. - S. 296-300. — 816 s. - 3000 kappaletta. - ISBN 5-89392-055-4 .
Kormen T., Leiser C. Luku 33.8. Numeroiden tarkistaminen yksinkertaisuuden vuoksi // Algoritmit. Rakentaminen ja analyysi . - M .: MTSNMO, 2002. - S. 765-772. - ISBN 5-900916-37-5 .
Crandall R., Pomerance C. Luku 3. Primesien ja komposiittien tunnistaminen. Luku 4. "Primaalisuuden todistaminen" // Alkuluvut : Laskennallinen näkökulma . - Springer, 2005. - S. 117-224. — ISBN 0-387-25282-7 .
Donald Knuth . Luku 4.5.4. Prime Factorization // Ohjelmoinnin taito, osa 2. Tuloksena olevat algoritmit = The Art of Computer Programming, voi. 2. Puolinumeeriset algoritmit. - 3. painos - M .: "Williams" , 2007. - S. 832. - ISBN 0-201-89684-2 .

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

Lukuteoriaalgoritmit _
Yksinkertaisuustestit	AKC testi APR testi Bailey-PSU Elliptinen käyrä Pocklingtonin kriteeri Maatilan testi Luken testi Luc-Lehmerin testi Luc-Lehmer-Riesel testi Protin lause Pepin testi Neliöllinen Frobenius-testi Nightingale-Strassenin testi Miller-Rabinin testi
Alkuluvun sukupolvi	Atkinin seula Eratosthenesin seula Seula Sundarama Decay Wheel
Kokonaislukujen faktorointi	Jatketaan murtolukumenetelmää Dixonin algoritmi Elliptisen käyrän menetelmä Eulerin menetelmä Pollardin ρ-algoritmi p −1 Pollardin menetelmä p +1-Williamsin menetelmä Neliömäinen seula Yleinen lukukenttäseulamenetelmä Erikoisnumerokenttäseulamenetelmä Rationaalinen seula Fermat menetelmä Quadratic Shanks -muodot Iterointi jakajien yli Shorin algoritmi
Kertominen	Muinainen egyptiläinen Kertominen sarakkeella Karatsuba Toom-Cook-algoritmi Schönhage - Strassen Fuhrer
Diskreetti logaritmi	Gelfond-Shanks -algoritmi ρ-algoritmi "Kenguru" Polyga - Hellman tilauslaskenta Toimintokenttäseula
Suurin yhteinen jakaja	Binäärinen algoritmi Eukleideen algoritmi Laajennettu Eukleideen algoritmi Lemairen GCD-algoritmi
Modulaarinen neliöjuuri	Cipolla-algoritmi Pocklingtonin algoritmi Gelfond-Shanks -algoritmi
Muut algoritmit	Chakrawala menetelmä Kornakkiyan algoritmi LLL kokonaisluvun neliöjuuri Eksponenttio modulo Shufin algoritmi
Kursivoitu fontti tarkoittaa, että algoritmi on suunniteltu erityisille numeroille