Test de primalidad per curves elíptiques

En matemàtiques, les tècniques de prova de primalidad per mig de curves elíptiques, o tests de primalidad per curves elíptiques (ECPP per les sigles del seu nom en anglés, Elliptic Curve Primality Proving), es troben entre els métodos més ràpits i més utilisats en la prova de primalidad. És una idea proposta per Shafrira Goldwasser i Joe Kilian en 1986 i convertida en algoritme per A. O. L. Atkin eixe mateix any. L'algoritme va ser alterat i millorat per varis colaboradors posteriorment, i en particular per Atkin i François Morain, en 1993. El concepte d'usar curves elíptiques en la factorización havia segut desenrollat per H. W. Lenstra en 1985, i les implicacions per al seu us en proves (i demostracions) de primalidad varen seguir ràpidament.

Els tests de primalidad són un camp que existix des de l'época de Pierre de Fermat, en el temps de la qual la majoria dels algoritmes es basaven en la factorización, que es torna difícil de manejar en números grans. Els algoritmes moderns tracten els problemes de determinar si un número és primer i quins són els seus factors per separat, una qüestió que es va tornar d'importància pràctica en l'inici de la criptografia moderna. Encara que moltes proves actuals donen com resultat una eixida provabilística (N es mostra com a compost o com provablement primer, com en el test de primalidad de Baillie-PSW o el test de primalidad de Miller-Rabin), la prova de la curva elíptica prova la primalidad (o composició) en un certificat ràpidament verificable.

Els métodos per a demostrar la primalidad d'un número coneguts anteriorment, com el test de Pocklington-Lehmer, requerien a lo manco una factorización parcial de $N\pm 1$ per a demostrar que $N$ és primer. Com a resultat, estos métodos requerien una miqueta de sòrt i generalment són llents en la pràctica.

Primalidad per mig de curves elíptiques

És un algoritme d'us general, lo que significa que no depén de que el número tinga una forma especial. La ECPP és actualment en la pràctica l'algoritme conegut més ràpit per a provar la primalidad dels números en general, pero no es coneix el seu temps d'eixecució en el pijor dels casos. Heurísticamente, s'eixecuta en el temps:

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

per a alguns $\epsilon >0$. Este exponent pot reduir-se a $4+\epsilon$ per a algunes versions per mig d'arguments heurístics. L'algoritme funciona de la mateixa manera que la majoria dels atres tests de primalidad, per a lo que troba un grup i mostra que el seu tamany és tal que $p$ és primer. Per a la ECPP, el grup és una curva elíptica sobre un conjunt finito de formes quadràtiques, de modo que $p-1$ és trivial per a la factorización sobre el grup.

Genera un certificat de primalidad d'Atkin-Goldwasser-Kilian-Morain per recursión i després intenta verificar el certificat. El pas que requerix més temps de processament és la generació del certificat, perque es deu realisar la factorización sobre un cos de classes. El certificat es pot verificar ràpidament, lo que permet que una verificació de funcionament prenga molt poc temps.

Plantilla:A data de, el cosí més gran que s'ha provat en el método ECPP és $10^{50000}+65859$. La certificació va ser realisada per Andreas Enge usant el seu software fastECPP CM.

Proposició

Les proves de primalidad per curves elíptiques es basen en criteris anàlecs al criteri de Pocklington, a on el grup $(\mathbb{Z}/n\mathbb{Z}{)}^{*}$ es reemplaça per $E(\mathbb{Z}/n\mathbb{Z}),$ i I és una curva elíptica elegida adequadament. A continuació s'enuncia una proposició sobre la qual basar la prova, que és anàloga al criteri de Pocklington i dona lloc a la forma de Goldwasser-Kilian-Atkin de la prova de primalidad de la curva elíptica:

Siga N un sancer positiu i I el conjunt definit per l'equació $y^2=x^3+ax+bmodN.$ Considere's I sobre $\mathbb{Z}/N\mathbb{Z},$ aplique's una llei d'adició usual sobre I i siga 0 per al element neutre en I.

Siga m un número entero. Si hi ha un primer q que dividix a m, i és major que ${(\sqrt[4]{N}+1)}^2$ i existix un punt P en I tal que

(1) mP= 0

(2) (m/q)P està definit i no és igual a 0

Llavors N és primer.

Prova

Si N és compost, llavors existix un primer $p\le \sqrt{N}$ que dividix a N. Definixca's $E_p$ com la curva elíptica definida per la mateixa equació que I pero evaluada mòdul p en lloc de mòdul N. Définase també $m_p$ com l'orde del grup $E_p$. Pel teorema sobre curves elíptiques de Hasse se sap que

$m_p\le p+1+2\sqrt{p}={(\sqrt{p}+1)}^2\le {(\sqrt[4]{N}+1)}^2<q$

i per lo tant $\gcd (q,m_p)=1$ i existix un sancer o en la propietat de que

$uq\equiv 1mod{m}_p.$

Siga $P_p$ el punt P evaluat mòdul p. Aixina, en $E_p$ es té que

$(m/q)P_p=uq(m/q)P_p=um{P}_p=0,$

per (1), ya que $m{P}_p$ es calcula usant el mateix método que mP, llevat mòdul p en lloc de mòdul N (i $p\mid N$).

Açò contradiu (2), perque si (m/q)P està definit i no és igual a 0 (mod N), llavors en el mateix método es calcula mòdul p en lloc de mòdul N que produirà:

$(m/q)P_p\ne 0.$