Test jednoduchosti pomocí eliptických křivek

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 2. ledna 2020; kontroly vyžadují 3 úpravy .

V matematice jsou metody testování primality pomocí eliptických křivek (angl. - Elliptic Curve Primality Proving , zkr. ECPP ) jednou z nejrychlejších a nejpoužívanějších metod pro testování primality [1] . Tuto myšlenku předložili Shafi Goldwasser a Joe Kilian v roce 1986; byl přeměněn na algoritmus A.O.L. Atkin ve stejném roce. Následně byl algoritmus několikrát upraven a vylepšen, zejména Atkinem a Françoisem Morainem v roce 1993 [2] . Koncept použití faktorizace eliptické křivky byl vyvinut Hendrikem Lenstrou v roce 1985 a brzy následovalo jeho použití k testování a dokazování čísel pro primálnost.

Test primality existuje od dob Fermata , kdy většina algoritmů byla založena na faktorizaci , což se stává nepraktickým, když je vstup velký. Moderní algoritmy individuálně řeší problémy určování zda je číslo prvočíslo a jaké jsou jeho faktory . S příchodem moderního období rozvoje kryptografie to začalo mít značný praktický význam. Ačkoli mnoho moderních testů poskytuje pouze pravděpodobnostní výsledek (nebo ukazuje, že N je složené nebo pravděpodobně prvočíslo , jako například Miller-Rabinův test ), test eliptické křivky ukazuje, že číslo je prvočíslo (nebo složené) pomocí rychle ověřeného osvědčení [3] ( anglicky ).

Test primality eliptické křivky poskytuje alternativu (mimo jiné) k Pocklingtonovu testu, který může být v praxi obtížně proveditelný. Test eliptické křivky je založen na kritériích podobných Pocklingtonově testu , na kterém je založen odpovídající test [4] . Nyní formulujeme návrh, na jehož základě náš test, který je podobný Pocklingtonovu kritériu, dává vznik Goldwasser-Kilian-Atkinově testu testu eliptické křivky primality.

Důkaz jednoduchosti s eliptickými křivkami

Je to obecný algoritmus , což znamená, že nezávisí na číslech speciálních formulářů. V současné době je ECPP v praxi nejrychlejším známým algoritmem pro kontrolu primality čísel, ale není známa doba provádění v nejhorším případě (maximální doba, za kterou lze úlohu na konkrétní hardwarové platformě dokončit). ESRR funguje v čase: [5]

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

pro některé . Z heuristických důvodů lze tento ukazatel v některých případech redukovat na. ECPP funguje stejně jako většina ostatních testů primality , najde skupinu a ukáže, že její velikost je taková, že je prvočíslo. Pro ECPP je skupina eliptickou křivkou nad konečnou množinou kvadratických forem, která je triviální s ohledem na skupinový faktor*(?). $\varepsilon >0$ $4+\varepsilon$ $p$ $p-1$

ECPP vygeneruje certifikát primality Atkin-Goldwaser-Kilian-Morain pomocí rekurze a poté se pokusí certifikát ověřit. Krok, který zabírá nejvíce času CPU , je generování certifikátu, protože faktorizace musí být provedena na poli třídy . Certifikát lze ověřit rychle, takže prodleva pro tuto operaci je velmi krátká.

Od září 2015 je největším prvočíslem [6] , které bylo nalezeno metodou ECPP, 30950-místná hodnota, která je z hlediska Lucasovy sekvence označena jako:

$V(148091).$

Paulu Underwoodovi trvalo 9 měsíců, než jej získal certifikací Primo (software Marcela Martina).

Prohlášení

Nechť N je kladné celé číslo a E množina, která je určena vzorcem . Uvažujme E přes , s použitím obvyklého zákona sčítání na E , a napište 0 jako neutrální prvek na E . $y^{2}=x^{3}+ax+b{\pmod {N))$ $\mathbb {Z} /N\mathbb {Z}$

Nechť m je celé číslo. Pokud existuje prvočíslo q , které je dělitelem m a je větší než a na E je bod P takový, že $(N^{1/4}+1)^{2}$

(1) mP = 0

2) ( m / q ) P je definováno a nerovná se 0

Pak N je prvočíslo.

Důkaz

Pokud je N složené, pak existuje prvočíslo , které dělí N. Definujeme ji jako eliptickou křivku definovanou stejnou rovnicí jako E , ale definujeme ji modulo p , nikoli modulo N. Definujme jako pořadí skupiny . Podle Hasseovy věty o eliptických křivkách víme $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$

a tedy gcd a je zde celé číslo u s vlastností ${(q,m_{p})}=1$

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

Nechť existuje bod P odhadnutý modulo p. Tak, na máme $P_{p}$ $E_{p}$

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

pomocí (1), protože vypočteno za použití stejných metod jako mP , s výjimkou modulu p spíše než modulu N (a ). $mP_{p}$ $p\mid N$

To je v rozporu s (2), protože pokud ( m/q ) P je definováno a není rovno 0 (mod N ), pak stejná metoda modulo p spíše než mod N dá

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

Goldwasser-Kilianův algoritmus

Z tohoto tvrzení lze sestavit algoritmus, který dokáže, že celé číslo N je prvočíslo. To se provádí následujícím způsobem:

Vybereme tři náhodná celá čísla a, x, y a množinu

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

Nechť nyní P = ( x , y ) je bod patřící do E , kde E je definováno jako . Dále potřebujeme algoritmus pro počítání počtu bodů na E. Při aplikaci na E tento algoritmus (Koblitz a další navrhují Schufův algoritmus [algoritmus pro počítání bodů eliptické křivky nad konečným polem]) dá číslo m vyjadřující počet bodů na křivce E nad F N za předpokladu, že N je prvotřídní. Dále máme kritérium pro rozhodnutí, zda je naše křivka E přijatelná. $y^{2}=x^{3}+ax+b$

Pokud můžeme napsat m jako kde je malé celé číslo a q je pravděpodobně prvočíslo (například prošlo některými předchozími testy pravděpodobnosti primality ) , pak E nezahodíme . Pokud není možné zapsat m v tomto tvaru, pak naši křivku zahodíme a náhodně vybereme jinou trojici ( a, x, y ), abychom začali znovu. $m=kq$ $k\geq 2$

Předpokládejme, že jsme našli křivku, která pod kritériem přechází, pak přistoupíme k výpočtu mP a kP . Pokud se v některé fázi výpočtu setkáme s nedefinovaným výrazem (z výpočtu P nebo v algoritmu pro počítání počtu bodů), dostaneme netriviální faktor N.

Jestliže , pak je jasné, že N není prvočíslo, protože kdyby N bylo prvočíslo, pak by E mělo řád m a jakýkoli prvek E by se stal 0, když by byl vynásoben m . Pokud Kp = 0, pak se dostaneme do slepé uličky a musíme začít znovu s další trojicí. $mP\neq 0$

Nyní, jestliže a , pak naše předchozí tvrzení nám říká, že N je prvočíslo. Existuje však jeden možný problém, kterým je jednoduchost q . To musí být ověřeno pomocí stejného algoritmu. Popsali jsme tedy postup krok za krokem, kdy lze prvočíslost N dokázat pomocí prvočísla q a malých pravděpodobných prvočísel, opakovat, dokud nedosáhneme určitých prvočísel a skončíme. [8] [9] $mP=0$ $kP\neq 0$

Problémy s algoritmem

Atkin a Moraine řekli, že "problém s Goldwasser-Kilianovým algoritmem je v tom, že Schoufův algoritmus je téměř nemožné implementovat." [10] Je velmi pomalé a těžkopádné vypočítat všechny body na E pomocí Schufova algoritmu, což je preferovaný algoritmus pro Goldwasser-Kilianův algoritmus. Původní Schoofův algoritmus však není dostatečně účinný, aby poskytl výpočet počtu bodů v krátkém časovém období. [11] Tyto komentáře je třeba vidět v historickém kontextu, před tím, než Elkis a Atkin zlepšili Schufovu metodu.

Test jednoduchosti eliptické křivky (ECPP) Atkin-Morain

V článku z roku 1993 Atkin a Moraine popsali algoritmus ECPP, který se vyhýbá potížím s používáním algoritmu, který se opírá o těžkopádný výpočet počtu bodů (Schoofův algoritmus). Algoritmus stále spoléhá na výše uvedená tvrzení, ale namísto náhodného generování eliptických křivek a následného hledání správného m je jejich myšlenkou sestavit křivku E , na které je snadné vypočítat počet bodů. Při konstrukci křivek je klíčové komplexní násobení.

Nyní, když máme určité N , jehož jednoduchost je třeba dokázat, musíme najít vhodné m a q , stejně jako v Goldwasser-Kilianově algoritmu, který splní větu a dokáže jednoduchost N . (samozřejmě musí být nalezen i bod P a samotná křivka E )

ECPP používá komplexní násobení k sestavení křivky E , tato metoda usnadňuje výpočet m (počet bodů na E ). Nyní si tuto metodu popíšeme:

Použití komplexního násobení vyžaduje negativní diskriminant D, takže D lze zapsat jako součin dvou prvků , nebo, plně ekvivalentní, můžeme napsat rovnici: $D=\pi {\bar {\pi }}$

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

Pro některé a, b . Pokud dokážeme popsat N pomocí kterékoli z těchto forem, můžeme vytvořit eliptickou křivku E on s komplexním násobením (podrobně níže) a počet bodů je dán vztahem: $\mathbb {Z} /N\mathbb {Z}$

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

Abychom N rozdělil na dva prvky, potřebujeme (kde označuje Legendreův symbol ). Toto je nezbytná podmínka a dostatečnosti dosáhneme, pokud je řád skupiny h (D) in 1. To se děje pouze pro 13 hodnot D, což jsou prvky {-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)))$

Poznámky

↑ Příručka kryptografie eliptické a hyperelliptické křivky / Henri Cohen, Gerhard Frey. — Boca Raton: Chapman & Hall/CRC, 2006.
↑ Top, Jaap, Elliptic Curve Primality Proving , http://www.math.rug.nl/~top/atkin.pdf Archivováno 25. ledna 2014 na Wayback Machine
↑ Frank Lee. Přehled dokazování primality eliptické křivky (15. prosince 2011). Získáno 17. listopadu 2015. Archivováno z originálu 5. července 2017. (neurčitý)
↑ Washington, Lawrence C. , Elliptic Curves: Number Theory and Cryptography , Chapman & Hall/CRC, 2003
↑ Lenstra, Jr., A.K.; Lenstra, Jr., HW Algoritmy v teorii čísel // Teoretická informatika. - Amsterdam a New York: The MIT Press, 1990. - Sv. A. _ - str. 673-715 .
↑ Caldwell, Chris. Top Twenty: Elliptic Curve Primality Proof Archivováno 10. prosince 2008 na Wayback Machine z Prime Pages .
↑ Koblitz, Neal, Úvod do teorie čísel a kryptografie , 2. vydání, Springer, 1994
↑ Archivovaná kopie (odkaz není dostupný) . Datum přístupu: 17. listopadu 2015. Archivováno z originálu 4. března 2016. (neurčitý)
↑ 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 , Archivovaná kopie . Datum přístupu: 27. ledna 2010. Archivováno z originálu 18. července 2011. (neurčitý)
↑ Lenstra, Hendrik W., Efficient Algorithms in Number Theory , https://openaccess.leidenuniv.nl/bitstream/1887/2141/1/346_081.pdf Archivováno 26. července 2007 na Wayback Machine

Literatura

Eliptické křivky a dokazování primality od Atkina a Moraina.
Weisstein, Eric W. Elliptic Curve Primality Proving (anglicky) na webových stránkách Wolfram MathWorld .
Chris Caldwell, „Primality Proving 4.2: Eliptické křivky a test ECPP“ na Prime Pages .
François Morain, „Domovská stránka ECPP“ (obsahuje starý software ECPP pro některé architektury).
Marcel Martin, "Primo" (binární pro Linux 64-bit)
GMP-ECPP , bezplatná implementace ECPP