Enkelhetstest med elliptiska kurvor

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 2 januari 2020; kontroller kräver 3 redigeringar .

Inom matematik är primalitetstestmetoder som använder elliptiska kurvor (eng. - Elliptic Curve Primality Proving , förkortning ECPP ) en av de snabbaste och mest använda metoderna för att testa för primat [1] . Denna idé lades fram av Shafi Goldwasser och Joe Kilian 1986; den förvandlades till A.O.L- algoritmen. Atkin samma år. Därefter har algoritmen modifierats och förbättrats flera gånger, framför allt av Atkin och François Morain 1993 [2] . Konceptet med att använda elliptisk kurvfaktorisering utvecklades av Hendrik Lenstra 1985 och följdes snart av dess användning för att testa och bevisa siffror för primalitet.

Primalitetstestet har funnits sedan Fermats tid , då de flesta algoritmer baserades på faktorisering , vilket blir otympligt när inputen är stor. Moderna algoritmer löser individuellt problemen med att avgöra om ett tal är primtal och vilka är dess faktorer . Med tillkomsten av den moderna utvecklingsperioden för kryptografi började detta få betydande praktisk betydelse. Även om många moderna test bara ger ett probabilistiskt resultat (eller visar att N är sammansatt, eller förmodligen primtal , som till exempel med Miller-Rabin-testet ), visar den elliptiska kurva-testet att ett tal är primtal (eller sammansatt) med hjälp av en snabbt verifierad certifikat [3] ( engelska ).

Primalitetstestet för elliptiska kurvor ger ett alternativ (bland annat) till Pocklington-testet, vilket kan vara svårt att implementera i praktiken. Det elliptiska kurvtestet baseras på kriterier som liknar Pocklington-testet , på vilket motsvarande test baseras [4] . Vi formulerar nu ett förslag på grundval av vilket vårt test, som liknar Pocklington-kriteriet, och ger upphov till Goldwasser-Kilian-Atkin-testet av det elliptiska primalitetskurvatestet.

Bevis på enkelhet med elliptiska kurvor

Det är en allmän algoritm , vilket innebär att den inte är beroende av speciella formnummer. För närvarande är ECPP, i praktiken, den snabbaste kända algoritmen för att kontrollera primaliteten hos siffror, men den värsta exekveringstiden (den maximala tiden under vilken en uppgift kan slutföras på en viss hårdvaruplattform) är inte känd. ESRR fungerar i tid: [5]

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

för vissa . Av heuristiska skäl kan denna indikator reduceras till i vissa fall. ECPP fungerar på samma sätt som de flesta andra primatitetstester , hittar en grupp och visar att dess storlek är sådan att den är prime. För ECPP är en grupp en elliptisk kurva över en ändlig uppsättning kvadratiska former som är trivial med avseende på gruppfaktorn*(?). $\varepsilon >0$ $4+\varepsilon$ $sid$ $p-1$

ECPP genererar ett Atkin-Goldwaser-Kilian-Morain-primalitetscertifikat med hjälp av rekursion och försöker sedan verifiera certifikatet. Det steg som tar mest CPU- tid är att generera certifikatet, eftersom faktoriseringen måste utföras på klassfältet . Certifikatet kan valideras snabbt, vilket gör fördröjningen för denna operation mycket kort.

Från och med september 2015 är det största primtal [6] som hittades med ECPP-metoden ett värde på 30950 siffror, vilket betecknas i termer av Lucas-sekvensen som:

$V(148091).$

Det tog Paul Underwood 9 månader att få den certifierad med Primo (Marcel Martins mjukvara).

Uttalande

Låt N vara ett positivt heltal och E en mängd, som bestäms av formeln . Betrakta E över , med den vanliga additionslagen på E , och skriv 0 som det neutrala elementet på E . $y^{2}=x^{3}+ax+b{\pmod {N))$ $\mathbb {Z} /N\mathbb {Z}$

Låt m vara ett heltal. Om det finns ett primtal q som är en divisor av m och större än och det finns en punkt P på E så att $(N^{1/4}+1)^{2}$

(1) mP = 0

2) ( m / q ) P är definierat och inte lika med 0

Då är N ett primtal.

Bevis

Om N är sammansatt, så finns det ett primtal som delar N. Vi definierar det som en elliptisk kurva definierad av samma ekvation som E , men vi definierar den modulo p , inte modulo N. Låt oss definiera som gruppens ordning . Genom Hasses sats om elliptiska kurvor vet vi $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$

och alltså gcd , och det finns ett heltal u med egenskapen ${(q,m_{p})}=1$

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

Låt det finnas en punkt P uppskattad modulo p. Alltså på vi har $P_{p}$ $E_{p}$

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

använder (1), eftersom beräknas med samma metoder som mP , förutom modulen för p snarare än modulen för N (och ). $mP_{p}$ $p\mid N$

Detta motsäger (2), eftersom om ( m/q ) P är definierad och inte är lika med 0 (mod N ), så kommer samma metod modulo p snarare än mod N att ge

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

Goldwasser-Kilian-algoritmen

Från detta påstående kan en algoritm konstrueras för att bevisa att heltal N är primtal. Detta görs på följande sätt:

Vi väljer tre slumpmässiga heltal a, x, y och mängd

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

Låt nu P = ( x , y ) vara en punkt som hör till E , där E definieras som . Därefter behöver vi en algoritm för att räkna antalet poäng på E. Tillämpad på E kommer denna algoritm (Koblitz och andra föreslår Schufs algoritm [en algoritm för att räkna punkter i en elliptisk kurva över ett ändligt fält]) ge ett tal m som uttrycker antalet punkter på kurvan E över F N , förutsatt att N är prime. Därefter har vi ett kriterium för att avgöra om vår kurva E är acceptabel. $y^{2}=x^{3}+ax+b$

Om vi kan skriva m som där är ett litet heltal och q antagligen är primtal (till exempel klarade den några tidigare probabilistiska primalitetstester ) , så kasserar vi inte E. Om det inte går att skriva m i det här formuläret, kasserar vi vår kurva och väljer slumpmässigt en annan trippel ( a, x, y ) för att börja om. $m=kq$ $k\geq 2$

Anta att vi har hittat en kurva som passerar under kriteriet, sedan fortsätter vi med att beräkna mP och kP . Om vi i något skede av beräkningen stöter på ett odefinierat uttryck (från beräkningen av P eller i algoritmen för att räkna antalet poäng), ger detta oss en icke-trivial faktor N.

Om , då blir det tydligt att N inte är primtal, för om N var primtal skulle E ha ordningen m , och vilket element av E som helst skulle bli 0 när det multipliceras med m . Om Kp = 0, så hamnar vi i en återvändsgränd och måste börja om med ytterligare en trippel. $mP\neq 0$

Nu, om och , då vårt tidigare uttalande säger oss att N är primtal. Det finns dock ett möjligt problem, vilket är enkelheten i q . Detta måste verifieras med samma algoritm. Sålunda har vi beskrivit ett steg-för-steg-förfarande där primeness av N kan bevisas med primeness av q och små troliga primeness, upprepa tills vi når vissa primeness och avslutar. [8] [9] $mP=0$ $kP\neq 0$

Problem med algoritmen

Atkin och Moraine sa att "problemet med Goldwasser-Kilian-algoritmen är att Schouf-algoritmen är nästan omöjlig att implementera." [10] Det är mycket långsamt och krångligt att beräkna alla punkter på E med Schuf-algoritmen, som är den föredragna algoritmen för Goldwasser-Kilian-algoritmen. Schoofs ursprungliga algoritm är dock inte tillräckligt effektiv för att ge beräkningen av antalet poäng under en kort tidsperiod. [11] Dessa kommentarer måste ses i ett historiskt sammanhang, före Elkis och Atkins förbättring av Schuf-metoden.

Elliptic Curve Simplicity Test (ECPP) Atkin-Morain

I en artikel från 1993 beskrev Atkin och Moraine en ECPP-algoritm som undviker svårigheterna med att använda en algoritm som bygger på en besvärlig poängräkning (Schoofs algoritm). Algoritmen förlitar sig fortfarande på påståendena ovan, men istället för att generera elliptiska kurvor slumpmässigt och sedan hitta rätt m , är deras idé att bygga en kurva E på vilken det är lätt att beräkna antalet punkter. Komplex multiplikation är nyckeln i kurvkonstruktion.

Nu, givet ett visst N , vars enkelhet måste bevisas, måste vi hitta lämpliga m och q , precis som i Goldwasser-Kilian-algoritmen, som kommer att uppfylla satsen och bevisa enkelheten hos N . (naturligtvis måste också punkten P och själva kurvan, E , hittas)

ECPP använder komplex multiplikation för att bygga kurvan E , denna metod gör det enkelt att beräkna m (antal punkter på E ). Låt oss nu beskriva denna metod:

Användningen av komplex multiplikation kräver en negativ diskriminant , D, så att D kan skrivas som en produkt av två element , eller, helt ekvivalent, vi kan skriva ekvationen: $D=\pi {\bar {\pi }}$

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

För vissa a, b . Om vi kan beskriva N i termer av någon av dessa former, kan vi skapa en elliptisk kurva E på med komplex multiplikation (detaljerad nedan), och antalet poäng ges av: $\mathbb {Z} /N\mathbb {Z}$

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

För att dela upp N i två element måste vi göra det (där betecknar Legendre-symbolen ). Detta är ett nödvändigt villkor, och vi kommer att uppnå tillräcklighet om ordningen för gruppen h (D) i är 1. Detta händer bara för de 13 värdena av D, som är elementen {-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)))$

Anteckningar

↑ Handbook of Elliptic and Hyperelliptic Curve Cryptography / Henri Cohen, Gerhard Frey. — Boca Raton: Chapman & Hall/CRC, 2006.
↑ Top, Jaap, Elliptic Curve Primality Proving , http://www.math.rug.nl/~top/atkin.pdf Arkiverad 25 januari 2014 på Wayback Machine
↑ Frank Lee. En översikt över elliptisk kurvaprimalitetsbevis (15 december 2011). Hämtad 17 november 2015. Arkiverad från originalet 5 juli 2017. (obestämd)
↑ Washington, Lawrence C. , Elliptic Curves: Number Theory and Cryptography , Chapman & Hall/CRC, 2003
↑ Lenstra, Jr., A.K.; Lenstra, Jr., HW Algoritmer i talteori // Teoretisk datavetenskap. - Amsterdam och New York: The MIT Press, 1990. - Vol. A. _ - s. 673-715 .
↑ Caldwell, Chris. The Top Twenty: Elliptic Curve Primality Proof Arkiverad 10 december 2008 på Wayback Machine från Prime Pages .
↑ Koblitz, Neal, Introduktion till talteori och kryptografi , 2:a upplagan, Springer, 1994
↑ Arkiverad kopia (länk ej tillgänglig) . Datum för åtkomst: 17 november 2015. Arkiverad från originalet den 4 mars 2016. (obestämd)
↑ Blake, Ian F., Seroussi, Gadiel, Smart, Nigel Paul, Elliptic Curves in Cryptography , Cambridge University Press, 1999
↑ Atkin, AOL, Morain, F., Elliptic Curves and Primity Proving , Arkiverad kopia . Tillträdesdatum: 27 januari 2010. Arkiverad från originalet den 18 juli 2011. (obestämd)
↑ Lenstra, Hendrik W., Efficient Algorithms in Number Theory , https://openaccess.leidenuniv.nl/bitstream/1887/2141/1/346_081.pdf Arkiverad 26 juli 2007 på Wayback Machine

Litteratur

Elliptiska kurvor och Primality Proving av Atkin och Morain.
Weisstein, Eric W. Elliptic Curve Primality Proving (engelska) på Wolfram MathWorld- webbplatsen .
Chris Caldwell, "Primality Proving 4.2: Elliptic curves and the ECPP test" på Prime Pages .
François Morain, "ECPP-hemsidan" (inkluderar gammal ECPP-mjukvara för vissa arkitekturer).
Marcel Martin, "Primo" (binär för Linux 64-bitars)
GMP-ECPP , en gratis ECPP-implementering