Yksinkertaisuustesti elliptisiä käyriä käyttäen

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

Matematiikassa elliptisiä käyriä käyttävät primaalisuustestausmenetelmät (eng. - Elliptic Curve Primality Proving , lyhenne ECPP ) ovat yksi nopeimmista ja laajimmin käytetyistä primaalisuuden testausmenetelmistä [1] . Tämän idean esittivät Shafi Goldwasser ja Joe Kilian vuonna 1986; se muutettiin A.O.L- algoritmiksi. Atkin samana vuonna. Myöhemmin algoritmia on muokattu ja parannettu useita kertoja, erityisesti Atkin ja François Morain vuonna 1993 [2] . Hendrik Lenstra kehitti elliptisen käyrän tekijöiden käyttökonseptin vuonna 1985, ja sitä seurasi pian sen käyttö lukujen primaalisuuden testaamiseen ja todistamiseen.

Primaliteettitesti on ollut olemassa Fermatin ajoista lähtien , jolloin useimmat algoritmit perustuivat tekijöihin jakamiseen , mikä tulee raskaaksi, kun syöte on suuri. Nykyaikaiset algoritmit ratkaisevat yksilöllisesti ongelmat, jotka liittyvät sen määrittämiseen, onko luku alkuluku ja mitkä ovat sen tekijät . Nykyaikaisen kryptografian kehityskauden tullessa tällä alkoi olla merkittävää käytännön merkitystä. Vaikka monet nykyaikaiset testit antavat vain todennäköisyyspohjaisen tuloksen (tai osoittavat, että N on komposiitti tai luultavasti alkuluku , kuten esimerkiksi Miller-Rabin-testissä ), elliptisen käyrän testi osoittaa, että luku on alkuluku (tai yhdistelmä) käyttämällä nopeasti varmennettua todistus [3] ( englanti ).

Elliptisen käyrän primaalisuustesti tarjoaa (muun muassa) vaihtoehdon Pocklingtonin testille, jota voi olla vaikea toteuttaa käytännössä. Elliptisen käyrän testi perustuu samanlaisiin kriteereihin kuin Pocklingtonin testi , johon vastaava testi perustuu [4] . Muotoilemme nyt ehdotuksen, jonka perusteella Pocklingtonin kriteeriä muistuttava testimme johtaa elliptisen primaalisuuskäyrän testin Goldwasser-Kilian-Atkin-testiin.

Todiste yksinkertaisuudesta elliptisten käyrien avulla

Se on yleinen algoritmi , mikä tarkoittaa, että se ei ole riippuvainen erityisistä lomakenumeroista. Tällä hetkellä ECPP on käytännössä nopein tunnettu algoritmi lukujen primaalisuuden tarkistamiseen, mutta pahimman tapauksen suoritusaikaa (maksimiaikaa, jonka kuluessa tehtävä voidaan suorittaa tietyllä laitteistoalustalla) ei tunneta. ESRR toimii ajallaan: [5]

$O((\log n)^{5+\varepsilon })$

joillekin . Heuristisista syistä tämä indikaattori voidaan pienentää joissakin tapauksissa. ECPP toimii samalla tavalla kuin useimmat muut primaalisuustestit , löytää ryhmän ja osoittaa, että sen koko on sellainen, että se on primaali. ECPP:ssä ryhmä on elliptinen käyrä, joka ylittää rajallisen joukon neliömuotoja, joka on triviaali suhteessa ryhmätekijään*(?). $\varepsilon >0$ $4+\varepsilon$ $s$ $p-1$

ECPP luo Atkin-Goldwaser-Kilian-Morain-primaliteettivarmenteen rekursiolla ja yrittää sitten varmistaa varmenteen. Eniten suoritinaikaa vievä vaihe on varmenteen luominen, koska tekijöiden jakaminen on suoritettava luokkakentässä . Varmenne voidaan vahvistaa nopeasti, jolloin tämän toiminnon viive on erittäin lyhyt.

Syyskuusta 2015 lähtien suurin ECPP-menetelmällä löydetty alkuluku [6] on 30950-numeroinen arvo, joka on merkitty Lucas-sekvenssillä seuraavasti:

$V(148091).$

Paul Underwoodilla kesti 9 kuukautta saada se Primo-sertifiointiin (Marcel Martinin ohjelmisto).

Lausunto

Olkoon N positiivinen kokonaisluku ja E joukko, joka määritetään kaavalla . Harkitse E : tä käyttämällä tavallista E :n summauslakia ja kirjoita 0 E:n neutraaliksi elementiksi . $y^{2}=x^{3}+ax+b{\pmod {N))$ $\mathbb {Z} /N\mathbb {Z}$

Olkoon m kokonaisluku. Jos on alkuluku q , joka on luvun m jakaja ja suurempi kuin , ja E :ssä on piste P siten, että $(N^{1/4}+1)^{2}$

(1) mP = 0

2) ( m / q ) P on määritelty, eikä se ole 0

Silloin N on alkuluku.

Todiste

Jos N on yhdistelmä, on alkuluku , joka jakaa N. Määrittelemme sen elliptiseksi käyräksi, jonka määrittelee sama yhtälö kuin E , mutta määrittelemme sen modulo p , ei modulo N. Määritellään ryhmän järjestykseksi . Hassen elliptisiä käyriä koskevan lauseen perusteella tiedämme $p\leq {\sqrt {N))$ $E_{p}$ $m_{p}$ $E_{p}$

$m_{p}\leq p+1+2{\sqrt {p}}=({\sqrt {p}}+1)^{2}\leq (N^{1/4}+1) ^{2}<q$

ja siten gcd , ja ominaisuuden kanssa on kokonaisluku u ${(q,m_{p})}=1$

${\displaystyle uq\equiv 1{\pmod {m_{p))))$

Olkoon piste P estimoitu modulo p. Näin ollen meillä on $P_{p}$ $E_{p}$

$(m/q)P_{p}=uq(m/q)P_{p}=umP_{p}=0$

käyttämällä (1), koska laskettu käyttäen samoja menetelmiä kuin mP , paitsi p :n moduulin sijaan N :n (ja ) moduulin avulla. $mP_{p}$ $p\mid N$

Tämä on ristiriidassa (2), koska jos ( m/q ) P on määritelty eikä se ole yhtä suuri kuin 0 (mod N ), niin sama menetelmä modulo p kuin mod N antaa

${\näyttötyyli (m/q)P_{p}\neq 0}$ [7]

Goldwasser-Kilian-algoritmi

Tästä lauseesta voidaan rakentaa algoritmi, joka todistaa, että kokonaisluku N on alkuluku. Tämä tehdään seuraavalla tavalla:

Valitsemme kolme satunnaista kokonaislukua a, x, y ja joukko

$b\equiv y^{2}-x^{3}-ax{\pmod {N))$

Olkoon nyt P = ( x , y ) E : hen kuuluva piste , jossa E määritellään muodossa . Seuraavaksi tarvitsemme algoritmin E :n pisteiden määrän laskemiseen . Sovellettaessa E :tä tämä algoritmi (Koblitz ja muut ehdottavat Schufin algoritmia [algoritmi elliptisen käyrän pisteiden laskemiseen äärellisen kentän yli]) antaa luvun m , joka ilmaisee pisteiden lukumäärää käyrällä E yli F N , edellyttäen että N on ensiluokkainen. Seuraavaksi meillä on kriteeri, jolla päätetään, onko käyrämme E hyväksyttävä. $y^{2}=x^{3}+ax+b$

Jos voimme kirjoittaa m :ksi missä on pieni kokonaisluku ja q on luultavasti alkuluku (esimerkiksi se läpäisi joitain aiempia todennäköisyyspohjaisia primaalisuustestejä ) , emme hylkää E :tä. Jos m ei ole mahdollista kirjoittaa tähän muotoon, hylkäämme käyrämme ja valitsemme satunnaisesti toisen kolmion ( a, x, y ) aloittaaksesi alusta. $m=kq$ $k\geq 2$

Oletetaan, että olemme löytäneet käyrän, joka läpäisee kriteerin, sitten lasketaan mP ja kP . Jos jossain laskennan vaiheessa kohtaamme määrittelemättömän lausekkeen ( P :n laskelmasta tai pisteiden lukumäärän laskenta-algoritmista), tämä antaa meille ei -triviaalin tekijän N.

Jos , niin käy selväksi, että N ei ole alkuluku, sillä jos N olisi alkuluku, niin E :llä olisi kertaluku m , ja mistä tahansa E :n alkiosta tulisi 0 kerrottuna m :llä . Jos Kp = 0, osumme umpikujaan ja on aloitettava uudestaan toisella kolmiosalla. $mP\neq 0$

Nyt, jos ja , Edellinen lauseemme kertoo, että N on alkuluku. On kuitenkin yksi mahdollinen ongelma, joka on q :n yksinkertaisuus . Tämä on tarkistettava samalla algoritmilla. Näin ollen olemme kuvanneet vaiheittaisen menettelyn, jossa N :n alkuluku voidaan todistaa käyttämällä q :n alkulukua ja pieniä todennäköisiä alkulukuja, toistaen, kunnes saavutamme tietyt alkuluvut ja lopetamme. [8] [9] $mP=0$ $kP\neq 0$

Ongelmia algoritmin kanssa

Atkin ja Moraine sanoivat, että "Goldwasser-Kilian-algoritmin ongelma on, että Schouf-algoritmia on lähes mahdoton toteuttaa." [10] On erittäin hidasta ja hankalaa laskea kaikki E :n pisteet käyttämällä Schuf-algoritmia, joka on Goldwasser-Kilian-algoritmin suositeltava algoritmi. Schoofin alkuperäinen algoritmi ei kuitenkaan ole tarpeeksi tehokas tarjoamaan pisteiden määrän laskemista lyhyessä ajassa. [11] Nämä kommentit on nähtävä historiallisessa kontekstissa, ennen kuin Elkis ja Atkin paransivat Schuf-menetelmää.

Elliptisen käyrän yksinkertaisuustesti (ECPP) Atkin-Morain

Vuonna 1993 julkaistussa artikkelissa Atkin ja Moraine kuvasivat ECPP-algoritmin, joka välttää vaikeudet käyttää algoritmia, joka perustuu hankalaan pistemäärän laskemiseen (Schoofin algoritmi). Algoritmi luottaa edelleen yllä oleviin väittämiin, mutta sen sijaan, että generoisivat satunnaisesti elliptisiä käyriä ja sitten löydettäisiin oikea m , niiden ideana on rakentaa käyrä E , josta on helppo laskea pisteiden lukumäärä. Monimutkainen kertolasku on avainkäyrän rakentamisessa.

Nyt kun annetaan tietty N , jonka yksinkertaisuus on todistettava, meidän on löydettävä sopivat m ja q , aivan kuten Goldwasser-Kilian-algoritmissa, jotka täyttävät lauseen ja todistavat N :n yksinkertaisuuden . (tietenkin piste P ja itse käyrä E , täytyy myös löytää)

ECPP käyttää kompleksista kertolaskua käyrän E rakentamiseen. Tällä menetelmällä m (pisteiden määrä E :llä) on helppo laskea . Kuvataan nyt tätä menetelmää:

Kompleksisen kertolaskun käyttö vaatii negatiivisen erottimen D, jolloin D voidaan kirjoittaa kahden alkion tulona , tai täysin vastaavana, voimme kirjoittaa yhtälön: $D=\pi {\bar {\pi }}$

$a^{2}+|D|b^{2}=4N$

Joillekin a, b . Jos voimme kuvata N :tä millä tahansa näistä muodoista, voimme luoda elliptisen käyrän E on kompleksisella kertolaskulla (yksityiskohtaisesti alla), ja pisteiden lukumäärä saadaan seuraavasti: $\mathbb {Z} /N\mathbb {Z}$

$|E(\mathbb {Z} /N\mathbb {Z} )|=N+1-\pi -{\bar {\pi }}=N+1-a.$

Jotta voimme jakaa N kahdeksi elementiksi, meidän on (jossa tarkoittaa Legendre-symbolia ). Tämä on välttämätön ehto, ja saavutamme riittävyyden, jos ryhmän h (D) järjestys on 1. Tämä tapahtuu vain D:n 13 arvolle, jotka ovat alkioita {-3, -4, -7 , -8, -11, -12 , -16, -19, -27, -28, -43, -67, -163} $\left({\frac {D}{N}}\right)=1$ $\left({\frac {D}{N}}\right)$ $\mathbb {Q} ({\sqrt {D)))$

Muistiinpanot

↑ Elliptisen ja hyperelliptisen käyrän kryptografian käsikirja / Henri Cohen, Gerhard Frey. - Boca Raton: Chapman & Hall/CRC, 2006.
↑ Top, Jaap, Elliptic Curve Primality Proving , http://www.math.rug.nl/~top/atkin.pdf Arkistoitu 25. tammikuuta 2014 Wayback Machinessa
↑ Frank Lee. Yleiskatsaus elliptisen käyrän primaalisuuden todistamiseen (15. joulukuuta 2011). Haettu 17. marraskuuta 2015. Arkistoitu alkuperäisestä 5. heinäkuuta 2017. (määrätön)
↑ Washington, Lawrence C. , Elliptiset käyrät: numeroteoria ja kryptografia , Chapman & Hall/CRC, 2003
↑ Lenstra, Jr., A.K.; Lenstra, Jr., HW Algoritmit lukuteoriassa // Teoreettinen tietojenkäsittelytiede. - Amsterdam ja New York: The MIT Press, 1990. - Voi. A. _ - s. 673-715 .
↑ Caldwell, Chris. Top Twenty: Elliptic Curve Primality Proof Arkistoitu 10. joulukuuta 2008 Wayback Machinessa Prime Pagesista .
↑ Koblitz, Neal, Johdatus numeroteoriaan ja kryptografiaan , 2. painos, Springer, 1994
↑ Arkistoitu kopio (linkki ei saatavilla) . Käyttöpäivä: 17. marraskuuta 2015. Arkistoitu alkuperäisestä 4. maaliskuuta 2016. (määrätön)
↑ Blake, Ian F., Seroussi, Gadiel, Smart, Nigel Paul, Elliptic Curves in Cryptography , Cambridge University Press, 1999
↑ Atkin, AOL, Morain, F., Elliptiset käyrät ja primaalisuuden todistaminen , Arkistoitu kopio . Käyttöpäivä: 27. tammikuuta 2010. Arkistoitu alkuperäisestä 18. heinäkuuta 2011. (määrätön)
↑ Lenstra, Hendrik W., Efficient Algorithms in Number Theory , https://openaccess.leidenuniv.nl/bitstream/1887/2141/1/346_081.pdf Arkistoitu 26. heinäkuuta 2007 Wayback Machinessa

Kirjallisuus

Elliptiset käyrät ja primaalisuuden todistaminen , Atkin ja Morain.
Weisstein, Eric W. Elliptic Curve Primality Proving (englanniksi) Wolfram MathWorld -verkkosivustolla .
Chris Caldwell, "Primality Proving 4.2: Elliptic curves and the ECPP-test" Prime Pagesissa .
François Morain, "ECPP-kotisivu" (sisältää vanhan ECPP-ohjelmiston joillekin arkkitehtuureille).
Marcel Martin, "Primo" (binaari 64-bittiselle Linuxille)
GMP-ECPP , ilmainen ECPP-toteutus