Test de simplitate folosind curbe eliptice

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 2 ianuarie 2020; verificările necesită 3 modificări .

În matematică , metodele de testare a primalității care folosesc curbe eliptice (ing. - Elliptic Curve Primality Proving , prescurtare ECPP ) sunt una dintre cele mai rapide și mai utilizate metode de testare a primalității [1] . Această idee a fost prezentată de Shafi Goldwasser și Joe Kilian în 1986; a fost transformat în algoritmul A.O.L. Atkin în același an. Ulterior, algoritmul a fost modificat și îmbunătățit de mai multe ori, mai ales de către Atkin și François Morain în 1993 [2] . Conceptul de utilizare a factorizării cu curbe eliptice a fost dezvoltat de Hendrik Lenstraîn 1985 și a fost în curând urmată de utilizarea sa pentru testarea și demonstrarea numerelor prime.

Testul de primalitate a existat încă de pe vremea lui Fermat , când majoritatea algoritmilor se bazau pe factorizare , care devine greoaie atunci când intrarea este mare. Algoritmii moderni rezolvă individual problemele de a determina dacă un număr este prim și care sunt factorii săi . Odată cu apariția perioadei moderne de dezvoltare a criptografiei, aceasta a început să aibă o semnificație practică semnificativă. Deși multe teste moderne dau doar un rezultat probabilist (sau arată că N este compus, sau probabil prim , ca de exemplu în cazul testului Miller-Rabin ), testul curbei eliptice arată că un număr este prim (sau compus) folosind o verificare rapidă. certificat [3] ( engleză ).

Testul de primalitate al curbei eliptice oferă o alternativă (printre altele) la testul Pocklington, care poate fi dificil de implementat în practică. Testul curbei eliptice se bazează pe criterii similare testului Pocklington , pe care se bazează testul corespunzător [4] . Formulăm acum o propunere pe baza căreia testul nostru, care este similar cu criteriul Pocklington, și dă naștere testului Goldwasser-Kilian-Atkin al testului curbei de primalitate eliptică.

Dovada de simplitate cu curbe eliptice

Este un algoritm general , ceea ce înseamnă că nu depinde de numere de formă speciale. În prezent, ECPP este, în practică, cel mai rapid algoritm cunoscut pentru verificarea primarității numerelor, dar timpul de execuție în cel mai rău caz (timpul maxim în care o sarcină poate fi finalizată pe o anumită platformă hardware) nu este cunoscut. ESRR funcționează în timp: [5]

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

pentru unii . Din motive euristice, acest indicator poate fi redus la pentru unele cazuri. ECPP funcționează la fel ca majoritatea celorlalte teste de primalitate , găsește un grup și arată că dimensiunea acestuia este de așa natură încât este primă. Pentru ECPP, un grup este o curbă eliptică peste un set finit de forme pătratice, astfel încât este trivială în raport cu factorul de grup*(?). $\varepsilon >0$ $4+\varepsilon$ $p$ $p-1$

ECPP generează un certificat de primalitate Atkin-Goldwaser-Kilian-Morain folosind recursiunea și apoi încearcă să verifice certificatul. Pasul care durează cel mai mult timp CPU este generarea certificatului, deoarece factorizarea trebuie efectuată în câmpul clasei . Certificatul poate fi validat rapid, ceea ce face ca întârzierea acestei operațiuni să fie foarte scurtă.

Din septembrie 2015, cel mai mare număr prim [6] care a fost găsit prin metoda ECPP este valoarea de 30950 de cifre, care este notat în termeni de secvența Lucas ca:

$V(148091).$

Paul Underwood i-a luat 9 luni pentru a-l obține certificat cu Primo (software-ul lui Marcel Martin).

Declarație

Fie N un întreg pozitiv, iar E o mulțime, care este determinată de formula . Luați în considerare E peste , folosind legea obișnuită de adunare pe E și scrieți 0 ca element neutru pe E . $y^{2}=x^{3}+ax+b{\pmod {N)}$ $\mathbb {Z} /N\mathbb {Z}$

Fie m un număr întreg. Dacă există un număr prim q care este un divizor al lui m și mai mare decât și există un punct P pe E astfel încât $(N^{1/4}+1)^{2}$

(1) mP = 0

2) ( m / q ) P este definit și nu este egal cu 0

Atunci N este un număr prim.

Dovada

Dacă N este compus, atunci există un număr prim care împarte N. O definim ca o curbă eliptică definită de aceeași ecuație ca E , dar o definim modulo p , nu modulo N. Să definim ca ordinea grupului . După teorema lui Hasse asupra curbelor eliptice, știm $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$

și astfel gcd și există un întreg u cu proprietatea ${(q,m_{p})}=1$

$uq\equiv 1{\pmod {m_{p}}}$

Fie un punct P estimat modulo p. Astfel, pe avem $P_{p}$ $E_{p}$

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

folosind (1), deoarece calculat folosind aceleași metode ca mP , cu excepția modulului lui p , mai degrabă decât a modulului lui N (și ). $mP_{p}$ $p\mid N$

Acest lucru contrazice (2), deoarece dacă ( m/q ) P este definit și nu este egal cu 0 (mod N ), atunci aceeași metodă modulo p mai degrabă decât mod N va da

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

Algoritmul Goldwasser-Kilian

Din această afirmație, se poate construi un algoritm pentru a demonstra că întregul N este prim. Acest lucru se face în felul următor:

Alegem trei numere întregi aleatorii a, x, y și mulțimea

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

Fie acum P = ( x , y ) un punct aparținând lui E , unde E este definit ca . În continuare, avem nevoie de un algoritm pentru a număra numărul de puncte pe E. Aplicat lui E , acest algoritm (Koblitz și alții propun algoritmul lui Schuf [un algoritm pentru numărarea punctelor unei curbe eliptice peste un câmp finit]) va da un număr m care exprimă numărul de puncte de pe curba E peste F N , cu condiția ca N este prim. În continuare, avem un criteriu pentru a decide dacă curba noastră E este acceptabilă. $y^{2}=x^{3}+ax+b$

Dacă putem scrie m unde este un număr întreg mic și q este probabil prim (de exemplu, a trecut unele teste de primalitate probabilistică anterioare) , atunci nu aruncăm E. Dacă nu este posibil să scriem m în această formă, atunci ne aruncăm curba și alegem aleatoriu un alt triplu ( a, x, y ) pentru a începe de la capăt. $m=kq$ $k\geq 2$

Să presupunem că am găsit o curbă care trece sub criteriu, apoi procedăm la calcularea mP și kP . Dacă în orice stadiu al calculului întâlnim o expresie nedefinită (din calculul lui P sau în algoritmul de numărare a numărului de puncte), aceasta ne oferă un factor netrivial N.

Dacă , atunci devine clar că N nu este prim, deoarece dacă N ar fi prim, atunci E ar avea ordinul m , iar orice element al lui E ar deveni 0 atunci când este înmulțit cu m . Dacă Kp = 0, atunci ajungem într-o fundătură și trebuie să începem din nou cu un alt triplu. $mP\neq 0$

Acum, dacă și , atunci afirmația noastră anterioară ne spune că N este prim. Cu toate acestea, există o problemă posibilă, care este simplitatea lui q . Acest lucru trebuie verificat folosind același algoritm. Astfel, am descris o procedură pas cu pas în care primătatea lui N poate fi dovedită folosind primătatea lui q și numerele prime mici probabile, repetând până ajungem la anumite prime și terminăm. [8] [9] $mP=0$ $kP\neq 0$

Probleme cu algoritmul

Atkin și Moraine au spus că „problema cu algoritmul Goldwasser-Kilian este că algoritmul Schouf este aproape imposibil de implementat”. [10] Este foarte lent și greoi să se calculeze toate punctele de pe E folosind algoritmul Schuf, care este algoritmul preferat pentru algoritmul Goldwasser-Kilian. Cu toate acestea, algoritmul original al lui Schoof nu este suficient de eficient pentru a oferi calculul numărului de puncte într-o perioadă scurtă de timp. [11] Aceste comentarii trebuie privite într-un context istoric, înainte de îmbunătățirea de către Elkis și Atkin a metodei Schuf.

Testul de simplitate a curbei eliptice (ECPP) Atkin-Morain

Într-o lucrare din 1993, Atkin și Moraine au descris un algoritm ECPP care evită dificultățile de utilizare a unui algoritm care se bazează pe un calcul greoi a numărului de puncte (algoritmul lui Schoof). Algoritmul se bazează în continuare pe afirmațiile de mai sus, dar în loc să genereze curbe eliptice la întâmplare și apoi să găsească m corect , ideea lor este să construiască o curbă E pe care să fie ușor de calculat numărul de puncte. Înmulțirea complexă este cheia în construcția curbei.

Acum, dat un anumit N , a cărui simplitate trebuie demonstrată, trebuie să găsim m și q potrivite , la fel ca în algoritmul Goldwasser-Kilian, care vor satisface teorema și vor demonstra simplitatea lui N . (desigur , trebuie găsite și punctul P și curba în sine, E )

ECPP folosește înmulțirea complexă pentru a construi curba E , această metodă ușurează calcularea m (numărul de puncte pe E ). Acum să descriem această metodă:

Utilizarea înmulțirii complexe necesită un discriminant negativ , D, astfel încât D poate fi scris ca produs a două elemente , sau, complet echivalent, putem scrie ecuația: $D=\pi {\bar {\pi }}$

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

Pentru unii a, b . Dacă putem descrie N în termenii oricăreia dintre aceste forme, putem crea o curbă eliptică E pe cu înmulțire complexă (detaliată mai jos), iar numărul de puncte este dat de: $\mathbb {Z} /N\mathbb {Z}$

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

Pentru a împărți N în două elemente, trebuie să (unde denotă simbolul Legendre ). Aceasta este o condiție necesară și vom atinge suficiența dacă ordinea grupului h (D) în este 1. Acest lucru se întâmplă numai pentru cele 13 valori ale lui D, care sunt elementele {-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))}$

Note

↑ Manual de criptografie cu curbe eliptice și hipereliptice / Henri Cohen, Gerhard Frey. — Boca Raton: Chapman & Hall/CRC, 2006.
↑ Top, Jaap, Elliptic Curve Primality Proving , http://www.math.rug.nl/~top/atkin.pdf Arhivat la 25 ianuarie 2014 la Wayback Machine
↑ Frank Lee. O privire de ansamblu asupra dovezirii primalității curbei eliptice (15 decembrie 2011). Consultat la 17 noiembrie 2015. Arhivat din original la 5 iulie 2017. (nedefinit)
↑ Washington, Lawrence C. , Curbe eliptice: Teoria numerelor și criptografia , Chapman & Hall/CRC, 2003
↑ Lenstra, Jr., A.K.; Lenstra, Jr., HW Algoritmi în teoria numerelor // Informatică teoretică. - Amsterdam și New York: The MIT Press, 1990. - Vol. A. _ - P. 673-715 .
↑ Caldwell, Chris. Top Twenty: Elliptic Curve Primality Proof Arhivat la 10 decembrie 2008 la Wayback Machine din Prime Pages .
↑ Koblitz, Neal, Introduction to Number Theory and Cryptography , Ed. a II-a, Springer, 1994
↑ Copie arhivată (link nu este disponibil) . Data accesului: 17 noiembrie 2015. Arhivat din original pe 4 martie 2016. (nedefinit)
↑ 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 , copie arhivată . Data accesului: 27 ianuarie 2010. Arhivat din original la 18 iulie 2011. (nedefinit)
↑ Lenstra, Hendrik W., Efficient Algorithms in Number Theory , https://openaccess.leidenuniv.nl/bitstream/1887/2141/1/346_081.pdf Arhivat la 26 iulie 2007 la Wayback Machine

Literatură

Curbele eliptice și demonstrarea primarității de către Atkin și Morain.
Weisstein, Eric W. Elliptic Curve Primality Proving (engleză) pe site-ul Wolfram MathWorld .
Chris Caldwell, „Primality Proving 4.2: Elliptic curves and the ECPP test” la Prime Pages .
François Morain, „Pagina de pornire ECPP” (include software-ul ECPP vechi pentru unele arhitecturi).
Marcel Martin, „Primo” (binar pentru Linux pe 64 de biți)
GMP-ECPP , o implementare ECPP gratuită