Egyszerűségvizsgálat elliptikus görbékkel

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. január 2-án felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

A matematikában az elliptikus görbéket alkalmazó primalitás-vizsgálati módszerek (eng. - Elliptic Curve Primality Proving , röv. ECPP ) az egyik leggyorsabb és legszélesebb körben használt módszer a primalitás vizsgálatára [1] . Ezt az ötletet Shafi Goldwasser és Joe Kilian terjesztette elő 1986-ban; A.O.L algoritmussá alakították át . Atkin ugyanabban az évben. Ezt követően az algoritmust többször módosították és javították, leginkább Atkin és François Morain 1993-ban [2] . Az elliptikus görbe-faktorizáció alkalmazásának koncepcióját Hendrik Lenstra dolgozta ki 1985-ben, és hamarosan ezt követte a számok elsődlegességének tesztelésére és bizonyítására való alkalmazása.

A primalitásteszt Fermat kora óta létezik , amikor a legtöbb algoritmus faktorizáción alapult , ami nehézkessé válik, ha nagy a bemenet. A modern algoritmusok egyenként oldják meg annak meghatározását, hogy egy szám prím-e, és melyek a tényezői . A kriptográfia fejlődésének modern korszakának beköszöntével ez jelentős gyakorlati jelentőséggel bírt. Bár sok modern teszt csak valószínűségi eredményt ad (vagy azt mutatja, hogy N összetett, vagy valószínűleg prím , mint például a Miller-Rabin teszt ), az elliptikus görbe teszt azt mutatja, hogy egy szám prím (vagy összetett) egy gyorsan ellenőrzött tanúsítvány [3] ( angol ).

Az elliptikus görbe primalitási teszt alternatívája (többek között) a Pocklington-tesztnek, amelyet a gyakorlatban nehéz lehet megvalósítani. Az elliptikus görbe teszt a Pocklington-teszthez hasonló kritériumokon alapul , amelyen a megfelelő teszt is alapul [4] . Most megfogalmazunk egy javaslatot, amely alapján a Pocklington-kritériumhoz hasonló tesztünk az elliptikus primalitásgörbe teszt Goldwasser-Kilian-Atkin tesztjét eredményezi.

Az egyszerűség bizonyítéka elliptikus görbékkel

Ez egy általános algoritmus , ami azt jelenti, hogy nem függ speciális űrlapszámoktól. Jelenleg az ECPP a gyakorlatban a leggyorsabb ismert algoritmus a számok elsődlegességének ellenőrzésére, de a legrosszabb eset végrehajtási ideje (az a maximális idő, ameddig egy feladat egy adott hardverplatformon elvégezhető) nem ismert. Az ESRR időben működik: [5]

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

egyesek számára . Heurisztikai okokból ez a mutató bizonyos esetekben csökkenthető. Az ECPP ugyanúgy működik, mint a legtöbb más elsődlegességi teszt , megkeres egy csoportot , és megmutatja, hogy annak mérete akkora, hogy elsődleges. Az ECPP esetében a csoport egy elliptikus görbe a másodfokú formák véges halmazán, amely triviális a csoporttényező*(?) szempontjából. $\varepsilon >0$ $4+\varepsilon$ $p$ $p-1$

Az ECPP rekurzió segítségével létrehoz egy Atkin-Goldwaser-Kilian-Morain elsődlegességi tanúsítványt, majd megpróbálja ellenőrizni a tanúsítványt. A legtöbb CPU -időt igénylő lépés a tanúsítvány generálása, mivel a faktorizációt az osztálymezőn kell végrehajtani . A tanúsítvány gyorsan érvényesíthető, így a művelet késleltetése nagyon rövid.

2015 szeptemberében az ECPP módszerrel talált legnagyobb prímszám [6] 30950 jegyű érték, amelyet a Lucas-szekvencia szempontjából a következőképpen jelölünk :

$V(148091).$

Paul Underwoodnak 9 hónapba telt, mire megszerezte a Primo tanúsítványt (Marcel Martin szoftvere).

Nyilatkozat

Legyen N pozitív egész szám, E pedig halmaz, amelyet a képlet határoz meg . Tekintsük E - t a szokásos összeadási törvényt használva E -n , és írjunk 0-t semleges elemnek E -re . $y^{2}=x^{3}+ax+b{\pmod {N))$ $\mathbb {Z} /N\mathbb {Z}$

Legyen m egész szám. Ha van egy q prímszám , amely osztója m -nek és nagyobb, mint , és van egy P pont E -n , $(N^{1/4}+1)^{2}$

(1) mP = 0

2) ( m / q ) P definiált, és nem egyenlő 0-val

Ekkor N egy prímszám.

Bizonyítás

Ha N összetett, akkor van egy prímszám , amely osztja N -t. Elliptikus görbeként definiáljuk ugyanazzal az egyenlettel, mint E , de modulo p definiáljuk , nem modulo N. Határozzuk meg a csoport sorrendjét . Hasse elliptikus görbékről szóló tétele alapján tudjuk $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$

és így gcd , és van egy u egész szám a tulajdonsággal ${(q,m_{p})}=1$

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

Legyen egy P pont becsült modulo p. Így van nálunk $P_{p}$ $E_{p}$

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

(1), mert ugyanazokkal a módszerekkel számítjuk ki, mint mP , kivéve a p modulusát, nem pedig az N (és ) modulusát. $mP_{p}$ $p\mid N$

Ez ellentmond (2-nek), mert ha ( m/q ) P definiálva van, és nem egyenlő 0-val (mod N ), akkor ugyanaz a modulo p metódus adja a mod N helyett

$(m/q)P_{p}\neq 0$ [7]

A Goldwasser-Kilian algoritmus

Ebből az állításból egy algoritmus készíthető annak bizonyítására, hogy az N egész szám prím. Ez a következő módon történik:

Válasszunk ki három véletlenszerű egész számot : a, x, y és halmazt

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

Legyen most P = ( x , y ) egy E - hez tartozó pont , ahol E : . Ezután szükségünk van egy algoritmusra, amely megszámolja az E pontok számát . E - re alkalmazva ez az algoritmus (Koblitz és mások Schuf algoritmusát javasolják [egy véges mező feletti elliptikus görbe pontjainak számlálására szolgáló algoritmus]) egy m számot ad, amely kifejezi az E görbe pontjainak számát F N felett , feltéve, hogy N az elsődleges. Ezután van egy kritériumunk annak eldöntésére, hogy az E görbénk elfogadható-e. $y^{2}=x^{3}+ax+b$

Ha felírhatjuk m -t úgy, hogy ahol egy kis egész szám, és q valószínűleg prímszám (például átment néhány korábbi valószínűségi primalitási teszten ) , akkor E -t nem hagyjuk el . Ha nem lehet m -et ebben a formában felírni, akkor eldobjuk a görbét, és véletlenszerűen választunk egy másik hármast ( a, x, y ) az újrakezdéshez. $m=kq$ $k\geq 2$

Tegyük fel, hogy találtunk egy görbét, amely átmegy a kritérium alatt, akkor folytatjuk az mP és kP kiszámítását . Ha a számítás bármely szakaszában definiálatlan kifejezéssel találkozunk (a P számításából vagy a pontszámláló algoritmusból), akkor egy nem triviális N tényezőt kapunk.

Ha , akkor világossá válik, hogy N nem prím, mert ha N prím lenne, akkor E -nek m rendje lenne , és E bármely eleme 0 lesz, ha megszorozzuk m -rel . Ha Kp = 0, akkor zsákutcába kerülünk, és újra kell kezdenünk egy másik triplával. $mP\neq 0$

Nos, ha és , akkor az előző állításunk azt mondja, hogy N prím. Van azonban egy lehetséges probléma, ez a q egyszerűsége . Ezt ugyanazzal az algoritmussal kell ellenőrizni. Így leírtunk egy lépésről lépésre történő eljárást, ahol N prímsége q prímszámával és kis valószínűségi prímszámokkal igazolható, addig ismételve, amíg el nem érünk bizonyos prímeket, és befejezzük. [8] [9] $mP=0$ $kP\neq 0$

Problémák az algoritmussal

Atkin és Moraine azt mondta, hogy "a Goldwasser-Kilian algoritmus problémája az, hogy a Schouf-algoritmust szinte lehetetlen megvalósítani." [10] Nagyon lassú és körülményes az E -n lévő összes pont kiszámítása a Schuf algoritmussal, amely a Goldwasser-Kilian algoritmus előnyben részesített algoritmusa. Schoof eredeti algoritmusa azonban nem elég hatékony ahhoz, hogy rövid időn belül kiszámolja a pontok számát. [11] Ezeket a megjegyzéseket történelmi kontextusban kell szemlélni, mielőtt Elkis és Atkin javította a Schuf-módszert.

Elliptikus görbe egyszerűségi teszt (ECPP) Atkin-Morain

Egy 1993-as cikkében Atkin és Moraine leírt egy ECPP algoritmust, amely elkerüli a nehézkes pontszámláláson alapuló algoritmus (Schoof-algoritmus) használatának nehézségeit. Az algoritmus továbbra is a fenti állításokra támaszkodik, de ahelyett, hogy véletlenszerűen generálnának elliptikus görbéket, majd megtalálnák a megfelelő m -t, ötletük egy olyan E görbe felépítése , amelyen könnyen kiszámítható a pontok száma. A komplex szorzás kulcsfontosságú a görbe felépítésében.

Most egy bizonyos N , amelynek egyszerűségét igazolni kell, megfelelő m -t és q -t kell találnunk , akárcsak a Goldwasser-Kilian algoritmusban, amely kielégíti a tételt és bizonyítja N egyszerűségét . (természetesen meg kell találni a P pontot és magát az E görbét is )

Az ECPP komplex szorzást használ az E görbe felépítéséhez , ezzel a módszerrel könnyen kiszámítható m (pontok száma az E -n ). Most írjuk le ezt a módszert:

A komplex szorzás használatához szükség van egy negatív diszkriminánsra , D, így D felírható két elem szorzataként , vagy teljesen ekvivalensként felírhatjuk az egyenletet: $D=\pi {\bar {\pi }}$

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

Néhány a, b . Ha N - t le tudjuk írni ezen formák bármelyikével, akkor komplex szorzással E on elliptikus görbét készíthetünk (lásd alább), és a pontok számát a következőképpen adjuk meg: $\mathbb {Z} /N\mathbb {Z}$

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

Ahhoz, hogy N -t két elemre osszuk, szükségünk van (ahol a Legendre szimbólumot jelöli ). Ez szükséges feltétel, és akkor érjük el az elégségességet, ha a h (D) csoport sorrendje 1. Ez csak a D 13 értékére történik, amelyek a {-3, -4, -7 elemek. , -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)))$

Jegyzetek

↑ Az elliptikus és hiperelliptikus görbe kriptográfia kézikönyve / Henri Cohen, Gerhard Frey. – Boca Raton: Chapman & Hall/CRC, 2006.
↑ Top, Jaap, Elliptic Curve Primality Proving , http://www.math.rug.nl/~top/atkin.pdf Archiválva : 2014. január 25. a Wayback Machine -nél
↑ Frank Lee. Az elliptikus görbe elsődlegességének bizonyításának áttekintése (2011. december 15.). Letöltve: 2015. november 17. Az eredetiből archiválva : 2017. július 5.. (határozatlan)
↑ Washington, Lawrence C. , Elliptikus görbék: Számelmélet és kriptográfia , Chapman és Hall/CRC, 2003
↑ Lenstra, Jr., A.K.; Lenstra, Jr., HW Algorithms in number theory // Theoretical Computer Science. - Amszterdam és New York: The MIT Press, 1990. - Vol. A. _ - P. 673-715 .
↑ Caldwell, Chris. A Top Twenty: Elliptic Curve Primality Proof archiválva 2008. december 10-én a Wayback Machine -nél a Prime Pagesről .
↑ Koblitz, Neal, Bevezetés a számelméletbe és a kriptográfiába , 2. kiadás, Springer, 1994
↑ Archivált másolat (a hivatkozás nem elérhető) . Hozzáférés dátuma: 2015. november 17. Az eredetiből archiválva : 2016. március 4. (határozatlan)
↑ Blake, Ian F., Seroussi, Gadiel, Smart, Nigel Paul, Elliptic Curves in Cryptography , Cambridge University Press, 1999
↑ Atkin, AOL, Morain, F., Elliptic Curves and Primality Proving , Archivált másolat . Hozzáférés dátuma: 2010. január 27. Az eredetiből archiválva : 2011. július 18. (határozatlan)
↑ Lenstra, Hendrik W., Efficient Algorithms in Number Theory , https://openaccess.leidenuniv.nl/bitstream/1887/2141/1/346_081.pdf Archiválva : 2007. július 26. a Wayback Machine -nél

Irodalom

Elliptikus görbék és elsődlegesség-bizonyítás , Atkin és Morain.
Weisstein, Eric W. Elliptikus görbe elsődlegességének bizonyítása (angolul) a Wolfram MathWorld webhelyén .
Chris Caldwell, "Primality Proving 4.2: Elliptic curves and the ECPP test" a Prime Pages -en .
François Morain, "Az ECPP honlapja" (egyes architektúrákhoz tartalmaz régi ECPP szoftvert).
Marcel Martin, "Primo" (bináris 64 bites Linuxhoz)
GMP-ECPP , egy ingyenes ECPP megvalósítás