Prueba de simplicidad usando curvas elípticas

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 2 de enero de 2020; las comprobaciones requieren 3 ediciones .

En matemáticas , los métodos de prueba de primalidad que utilizan curvas elípticas (ing. - Elliptic Curve Primality Proving , abreviatura ECPP ) son uno de los métodos más rápidos y más utilizados para probar la primalidad [1] . Esta idea fue propuesta por Shafi Goldwasser y Joe Kilian en 1986; se convirtió en el algoritmo A.O.L. Atkin en el mismo año. Posteriormente, el algoritmo ha sido modificado y mejorado varias veces, sobre todo por Atkin y François Morain en 1993 [2] . El concepto de usar factorización con curvas elípticas fue desarrollado por Hendrik Lenstraen 1985, y pronto fue seguido por su uso para probar y demostrar números primos.

La prueba de primalidad ha existido desde la época de Fermat , cuando la mayoría de los algoritmos se basaban en la factorización , que se vuelve difícil de manejar cuando la entrada es grande. Los algoritmos modernos resuelven individualmente los problemas de determinar si un número es primo y cuáles son sus factores . Con el advenimiento del período moderno de desarrollo de la criptografía, esto comenzó a tener un significado práctico significativo. Aunque muchas pruebas modernas solo dan un resultado probabilístico (o muestran que N es compuesto, o probablemente primo , como por ejemplo con la prueba de Miller-Rabin ), la prueba de la curva elíptica muestra que un número es primo (o compuesto) usando un número rápidamente verificado. certificado [3] ( inglés ).

La prueba de primalidad de la curva elíptica proporciona una alternativa (entre otras) a la prueba de Pocklington, que puede ser difícil de implementar en la práctica. La prueba de la curva elíptica se basa en criterios similares a la prueba de Pocklington , en la que se basa la prueba correspondiente [4] . Ahora formulamos una propuesta en base a la cual nuestra prueba, que es similar al criterio de Pocklington, y da lugar a la prueba de Goldwasser-Kilian-Atkin de la prueba de la curva de primalidad elíptica.

Prueba de simplicidad con curvas elípticas

Es un algoritmo general , lo que significa que no depende de números de forma especial. Actualmente, ECPP es, en la práctica, el algoritmo conocido más rápido para verificar la primalidad de los números, pero se desconoce el tiempo de ejecución en el peor de los casos (el tiempo máximo en el que se puede completar una tarea en una plataforma de hardware particular). ESRR funciona a tiempo: [5]

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

para algunos Por razones heurísticas, este indicador puede reducirse a para algunos casos. ECPP funciona igual que la mayoría de las otras pruebas de primalidad , encuentra un grupo y muestra que su tamaño es tal que es primo. Para ECPP, un grupo es una curva elíptica sobre un conjunto finito de formas cuadráticas tal que es trivial con respecto al factor de grupo*(?). $\varepsilon >0$ $4+\varepsilon$ $pags$ $p-1$

ECPP genera un certificado de primalidad Atkin-Goldwaser-Kilian-Morain mediante recursividad y luego intenta verificar el certificado. El paso que toma más tiempo de CPU es generar el certificado, porque la factorización se debe realizar en el campo de clase . El certificado se puede validar rápidamente, lo que hace que la demora para esta operación sea muy corta.

A partir de septiembre de 2015, el número primo más grande [6] encontrado por el método ECPP tiene un valor de 30950 dígitos, que se denota en términos de la secuencia de Lucas como:

${\ estilo de visualización V (148091).}$

Paul Underwood tardó 9 meses en obtener la certificación con Primo (software de Marcel Martin).

Declaración

Sea N un entero positivo y E un conjunto, que está determinado por la fórmula . Considere E sobre , usando la ley de adición usual en E , y escriba 0 como el elemento neutral en E . $y^{2}=x^{3}+ax+b{\pmod {N))$ $\mathbb {Z} /N\mathbb {Z}$

Sea m un número entero. Si hay un número primo q que es divisor de m y mayor que y hay un punto P en E tal que ${\ estilo de visualización (N^{1/4}+1)^{2}}$

(1) mP = 0

2) ( m / q ) P está definido y no es igual a 0

Entonces N es un número primo.

Prueba

Si N es compuesto, entonces hay un número primo que divide a N. La definimos como una curva elíptica definida por la misma ecuación que E , pero la definimos módulo p , no módulo N. Definamos como el orden del grupo . Por el teorema de Hasse sobre curvas elípticas, sabemos $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$

y por lo tanto mcd , y hay un entero u con la propiedad ${\ estilo de visualización {(q, m_ {p})} = 1}$

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

Sea un punto P estimado módulo p. Así, sobre tenemos $Páginas}$ $E_{p}$

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

usando (1), porque calculado utilizando los mismos métodos que mP , excepto por el módulo de p en lugar del módulo de N (y ). $mP_{p}$ $p\mid N$

Esto contradice (2), porque si ( m/q ) P está definido y no es igual a 0 (mod N ), entonces el mismo método módulo p en lugar de mod N dará

${\ estilo de visualización (m/q) P_ {p} \ neq 0}$ [7]

El algoritmo de Goldwasser-Kilian

A partir de esta declaración, se puede construir un algoritmo para demostrar que el número entero N es primo. Esto se hace de la siguiente manera:

Elegimos tres enteros aleatorios a, x, y y establecemos

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

Sea ahora P = ( x , y ) un punto perteneciente a E , donde E se define como . A continuación, necesitamos un algoritmo para contar el número de puntos en E. Aplicado a E , este algoritmo (Koblitz y otros proponen el algoritmo de Schuf [un algoritmo para contar puntos de una curva elíptica sobre un campo finito]) dará un número m que expresa el número de puntos en la curva E sobre F N , siempre que N es primo A continuación, tenemos un criterio para decidir si nuestra curva E es aceptable. $y^{2}=x^{3}+ax+b$

Si podemos escribir m como donde es un número entero pequeño y q es probablemente primo (por ejemplo, pasó algunas pruebas anteriores de primalidad probabilística) , entonces no descartamos E. Si no es posible escribir m de esta forma, descartamos nuestra curva y elegimos al azar otra tripleta ( a, x, y ) para comenzar de nuevo. ${\ estilo de visualización m = kq}$ $k\geq 2$

Supongamos que hemos encontrado una curva que pasa por debajo del criterio, entonces procedemos a calcular mP y kP . Si en cualquier etapa del cálculo encontramos una expresión indefinida (del cálculo de P o en el algoritmo para contar el número de puntos), esto nos da un factor no trivial N.

Si , queda claro que N no es primo, porque si N fuera primo, entonces E tendría orden m , y cualquier elemento de E se convertiría en 0 cuando se multiplicara por m . Si Kp = 0, llegamos a un callejón sin salida y debemos comenzar de nuevo con otro triple. $mP\neq 0$

Ahora, si y , entonces nuestro enunciado anterior nos dice que N es primo. Sin embargo, hay un problema posible, que es la simplicidad de q . Esto debe verificarse utilizando el mismo algoritmo. Así hemos descrito un procedimiento paso a paso donde se puede probar la primacía de N usando la primacía de q y pequeños primos probables, repitiendo hasta llegar a ciertos primos y terminar. [8] [9] ${\ estilo de visualización MP = 0}$ $kP\neq 0$

Problemas con el algoritmo

Atkin y Moraine dijeron que "el problema con el algoritmo de Goldwasser-Kilian es que el algoritmo de Schouf es casi imposible de implementar". [10] Es muy lento y engorroso calcular todos los puntos en E utilizando el algoritmo de Schuf, que es el algoritmo preferido para el algoritmo de Goldwasser-Kilian. Sin embargo, el algoritmo original de Schoof no es lo suficientemente eficiente para proporcionar el cálculo de la cantidad de puntos en un corto período de tiempo. [11] Estos comentarios deben verse en un contexto histórico, anterior a la mejora del método Schuf por parte de Elkis y Atkin.

Prueba de simplicidad de la curva elíptica (ECPP) Atkin-Morain

En un artículo de 1993, Atkin y Moraine describieron un algoritmo ECPP que evita las dificultades de usar un algoritmo que se basa en un engorroso cálculo de conteo de puntos (algoritmo de Schoof). El algoritmo aún se basa en las declaraciones anteriores, pero en lugar de generar curvas elípticas al azar y luego encontrar la m correcta , su idea es construir una curva E en la que sea fácil calcular el número de puntos. La multiplicación compleja es clave en la construcción de curvas.

Ahora, dado un cierto N , cuya simplicidad debe probarse, debemos encontrar m y q adecuados , tal como en el algoritmo de Goldwasser-Kilian, que satisfará el teorema y probará la simplicidad de N. (por supuesto , también se debe encontrar el punto P y la curva misma, E )

ECPP usa multiplicaciones complejas para construir la curva E , este método facilita el cálculo de m (número de puntos en E ). Ahora describamos este método:

El uso de la multiplicación compleja requiere un discriminante negativo , D, de modo que D pueda escribirse como un producto de dos elementos o, de manera completamente equivalente, podemos escribir la ecuación: $D=\pi {\bar {\pi }}$

${\ estilo de visualización a^{2}+|D|b^{2}=4N}$

Para algunos a, b . Si podemos describir N en términos de cualquiera de estas formas, podemos crear una curva elíptica E con una multiplicación compleja (detallada a continuación), y el número de puntos viene dado por: $\mathbb {Z} /N\mathbb {Z}$

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

Para dividir N en dos elementos, necesitamos (donde denota el símbolo de Legendre ). Esta es una condición necesaria, y lograremos la suficiencia si el orden del grupo h (D) en es 1. Esto solo ocurre para los 13 valores de D, que son los elementos {-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)))$

Notas

↑ Manual de criptografía de curvas elípticas e hiperelípticas / Henri Cohen, Gerhard Frey. — Boca Ratón: Chapman & Hall/CRC, 2006.
↑ Top, Jaap, Elliptic Curve Primality Proving , http://www.math.rug.nl/~top/atkin.pdf Archivado el 25 de enero de 2014 en Wayback Machine .
↑ Frank Lee. Una descripción general de la prueba de primalidad de la curva elíptica (15 de diciembre de 2011). Consultado el 17 de noviembre de 2015. Archivado desde el original el 5 de julio de 2017. (indefinido)
↑ Washington, Lawrence C. , Curvas elípticas: teoría de números y criptografía , Chapman & Hall/CRC, 2003
↑ Lenstra, Jr., AK; Lenstra, Jr., HW Algoritmos en teoría de números // Ciencias de la computación teórica. - Ámsterdam y Nueva York: The MIT Press, 1990. - vol. A._ _ - Pág. 673-715 .
↑ Caldwell, Chris. The Top Twenty: Prueba de primalidad de curva elíptica Archivado el 10 de diciembre de 2008 en Wayback Machine desde Prime Pages .
↑ Koblitz, Neal, Introducción a la teoría de números y criptografía , 2.ª edición, Springer, 1994
↑ Copia archivada (enlace no disponible) . Fecha de acceso: 17 de noviembre de 2015. Archivado desde el original el 4 de marzo de 2016. (indefinido)
↑ 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 , copia archivada . Fecha de acceso: 27 de enero de 2010. Archivado desde el original el 18 de julio de 2011. (indefinido)
↑ Lenstra, Hendrik W., Efficient Algorithms in Number Theory , https://openaccess.leidenuniv.nl/bitstream/1887/2141/1/346_081.pdf Archivado el 26 de julio de 2007 en Wayback Machine .

Literatura

Curvas elípticas y pruebas de primalidad de Atkin y Morain.
Weisstein, Eric W. Elliptic Curve Primality Proving (inglés) en el sitio web de Wolfram MathWorld .
Chris Caldwell, "Primality Proving 4.2: Curvas elípticas y la prueba ECPP" en Prime Pages .
François Morain, "La página de inicio de ECPP" (incluye software ECPP antiguo para algunas arquitecturas).
Marcel Martin, "Primo" (binario para Linux de 64 bits)
GMP-ECPP , una implementación gratuita de ECPP