En matemáticas , las técnicas de prueba de primalidad de curva elíptica , o prueba de primalidad de curva elíptica (ECPP), se encuentran entre los métodos más rápidos y más utilizados en la prueba de primalidad. [1] Es una idea presentada por Shafi Goldwasser y Joe Kilian en 1986 y convertida en un algoritmo por AOL Atkin el mismo año. El algoritmo fue modificado y mejorado por varios colaboradores posteriormente, y en particular por Atkin y François Morain , en 1993. [2] El concepto de usar curvas elípticas en factorización había sido desarrollado por HW Lenstra en 1985, y las implicaciones de su uso en las pruebas (y demostraciones) de primalidad siguieron rápidamente.
La prueba de primordialidad es un campo que existe desde la época de Fermat , en cuya época la mayoría de los algoritmos se basaban en la factorización, que se vuelven difíciles de manejar con una gran cantidad de datos ; Los algoritmos modernos tratan los problemas de determinar si un número es primo y cuáles son sus factores por separado. Se volvió de importancia práctica con el advenimiento de la criptografía moderna. Aunque muchas pruebas actuales dan como resultado una salida probabilística ( N se muestra compuesto, o probablemente primo, como con la prueba de primalidad de Baillie-PSW o la prueba de Miller-Rabin ), la prueba de curva elíptica demuestra primalidad (o composición) con una rapidez certificado comprobable. [3]
La prueba de primalidad de curva elíptica proporciona una alternativa (entre otras) a la prueba de primalidad de Pocklington , que puede ser difícil de implementar en la práctica.
Demostración de primalidad de curva elíptica
Es un algoritmo de propósito general , lo que significa que no depende de que el número sea de una forma especial. Actualmente, ECPP es en la práctica el algoritmo más rápido conocido para probar la primacía de los números generales, pero se desconoce el tiempo de ejecución del peor de los casos . ECPP se ejecuta heurísticamente en el tiempo:
para algunos . [4] Este exponente puede reducirse apara algunas versiones por argumentos heurísticos. ECPP funciona de la misma manera que la mayoría de las otras pruebas de primalidad , encontrar un grupo y mostrar su tamaño es tal quees primordial. Para ECPP, el grupo es una curva elíptica sobre un conjunto finito de formas cuadráticas tales que Es trivial factorizar sobre el grupo.
ECPP genera un certificado de primalidad Atkin - Goldwasser -Kilian-Morain por recursividad y luego intenta verificar el certificado. El paso que toma más tiempo de CPU es la generación del certificado, porque se debe realizar la factorización sobre un campo de clase . El certificado se puede verificar rápidamente, lo que permite que la verificación del funcionamiento lleve muy poco tiempo.
En febrero de 2020, la prima más grande que se ha probado con el método ECPP tiene 40.000 dígitos. [5] La certificación de Paul Underwood tomó 21,5 meses utilizando el software Primo de Marcel Martin.
Proposición
Las pruebas de primalidad de la curva elíptica se basan en criterios análogos al criterio de Pocklington, en el que se basa esa prueba, [6] donde el grupo es reemplazado por y E es una curva elíptica elegida correctamente. Ahora presentaremos una proposición en la que basar nuestra prueba, que es análoga al criterio de Pocklington, y da lugar a la forma Goldwasser-Kilian-Atkin de la prueba de primalidad de la curva elíptica.
Sea N un entero positivo y E el conjunto definido por la ecuaciónConsidere E sobreutilizar la ley de adición habitual en E , y escribir 0 para el elemento neutro en E .
Sea m un número entero. Si hay un primo q que divide m , y es mayor quey existe un punto P en E tal que
(1) mP = 0
(2) ( m / q ) P está definido y no es igual a 0
Entonces N es primo.
Prueba
Si N es compuesto, entonces existe un primoque divide N . Definircomo la curva elíptica definida por la misma ecuación que E pero evaluado modulo p en lugar de módulo N . Definir como el orden del grupo . Por el teorema de Hasse sobre curvas elípticas sabemos
y por lo tanto y existe un entero u con la propiedad de que
Dejar sea el punto P evaluado módulo p . Por lo tanto, en tenemos
por (1), como se calcula utilizando el mismo método que mP , excepto módulo p en lugar de módulo N (y).
Esto contradice (2), porque si ( m / q ) P está definido y no es igual a 0 (mod N ), entonces el mismo método calculado módulo p en lugar de módulo N producirá: [7]
Algoritmo Goldwasser-Kilian
A partir de esta proposición, se puede construir un algoritmo para demostrar que un número entero, N , es primo. Esto se hace de la siguiente manera:
Elija tres números enteros al azar, a, x, y y establezca
Ahora P = ( x , y ) es un punto en E , donde tenemos que E está definido por. Lo siguiente que necesitamos un algoritmo para contar el número de puntos de E . Aplicado a E , este algoritmo (Koblitz y otros sugieren el algoritmo de Schoof ) produce un número m que es el número de puntos en la curva E sobre F N , siempre que N sea primo. Si el algoritmo de punto de conteo se detiene en una expresión indefinida Esto permite determinar un factor no trivial de N . Si tiene éxito, aplicamos un criterio para decidir si nuestra curva E es aceptable.
Si podemos escribir m en la forma dónde es un entero pequeño y q un probable primo (que ha pasado algún probabilística anterior test de primalidad , por ejemplo), entonces no descarte E . De lo contrario, descartamos nuestra curva y seleccionamos aleatoriamente otro triple (a, x, y) para comenzar de nuevo. La idea aquí es encontrar una m dividida por un número primo grande q . Este primo tendrá aproximadamente la misma magnitud que m para m suficientemente grande .
Suponiendo que encontramos una curva que pasa el criterio, procedemos a calcular mP y kP . Si cualquiera de los dos cálculos producen una expresión indefinida, podemos obtener un factor no trivial de N . Si ambos cálculos tienen éxito, examinamos los resultados.
Si está claro que N no es primo, porque si N fuera primo, entonces E tendría el orden my cualquier elemento de E se convertiría en 0 al multiplicar por m . Si kP = 0, entonces el algoritmo descarta E y comienza de nuevo con un triple a , x, y diferente .
Ahora si y entonces nuestra proposición anterior nos dice que N es primo. Sin embargo, existe un posible problema, que es la primordialidad de q . Esto se verifica utilizando el mismo algoritmo. Así que hemos descrito un algoritmo recursivo , donde la primacía de N depende de la primacía de q y, de hecho, de 'primos probables' más pequeños hasta que se alcanza algún umbral donde q se considera lo suficientemente pequeño como para aplicar un algoritmo determinista no recursivo. [8] [9]
Problemas con el algoritmo
Atkin y Morain afirman que "el problema con GK es que el algoritmo de Schoof parece casi imposible de implementar". [3] Es muy lento y engorroso contar todos los puntos en E usando el algoritmo de Schoof, que es el algoritmo preferido para el algoritmo Goldwasser-Kilian. Sin embargo, el algoritmo original de Schoof no es lo suficientemente eficiente como para proporcionar el número de puntos en poco tiempo. [10] Estos comentarios deben ser vistos en el contexto histórico, antes de las mejoras de Elkies y Atkin al método de Schoof.
Un segundo problema que observa Koblitz es la dificultad de encontrar la curva E cuyo número de puntos es de la forma kq , como se indicó anteriormente. No existe un teorema conocido que garantice que podemos encontrar una E adecuada en muchos intentos polinomiales. La distribución de primos en el intervalo de Hasse, que contiene m , no es lo mismo que la distribución de primos en los órdenes de grupo, contando curvas con multiplicidad. Sin embargo, este no es un problema significativo en la práctica. [7]
Prueba de primalidad de la curva elíptica de Atkin-Morain (ECPP)
En un artículo de 1993, Atkin y Morain describieron un algoritmo ECPP que evitaba la molestia de depender de un engorroso algoritmo de conteo de puntos (el de Schoof). El algoritmo aún se basa en la proposición mencionada anteriormente, pero en lugar de generar curvas elípticas al azar y buscar una m adecuada , su idea era construir una curva E donde el número de puntos sea fácil de calcular. La multiplicación compleja es clave en la construcción de la curva.
Ahora, dada una N en que las necesidades de primalidad para ser probados tenemos que encontrar un adecuado m y q , al igual que en la prueba Goldwasser-Kilian, que cumplirá con la proposición y probar la primalidad de N . (Por supuesto, también se deben encontrar un punto P y la curva en sí, E ).
ECPP usa multiplicaciones complejas para construir la curva E , haciéndolo de una manera que permite calcular fácilmente m (el número de puntos en E ). Ahora describiremos este método:
La utilización de la multiplicación compleja requiere un discriminante negativo , D , tal que D pueda escribirse como el producto de dos elementos, o de manera completamente equivalente, podemos escribir la ecuación:
Para algunos a, b . Si podemos describir N en términos de cualquiera de estas formas, podemos crear una curva elíptica E en con multiplicación compleja (descrita en detalle a continuación), y el número de puntos viene dado por:
Para que N se divida en los dos elementos, necesitamos que (dónde denota el símbolo de Legendre ). Esta es una condición necesaria, y logramos suficiencia si el número de clase h ( D ) del pedido enes 1. Esto sucede solo para 13 valores de D , que son los elementos de {−3, −4, −7, −8, −11, −12, −16, −19, −27, −28, −43 , −67, −163}
La prueba
Elija discriminantes D en secuencia de aumento de h ( D ). Para cada D, compruebe siy si 4 N se puede escribir como:
Esta parte se puede verificar utilizando el algoritmo de Cornacchia . Una vez aceptables D y un han sido descubiertos, calcular. Ahora bien, si m tiene un factor primo q de tamaño
utilice el método de multiplicación compleja para construir la curva E y un punto P en ella. Entonces podemos usar nuestra propuesta para comprobar la primalidad de N . Tenga en cuenta que si m no tiene un factor primo grande o no se puede factorizar lo suficientemente rápido, se puede hacer otra elección de D. [1]
Método de multiplicación complejo
Para completar, proporcionaremos una descripción general de la multiplicación compleja , la forma en que se puede crear una curva elíptica, dada nuestra D (que se puede escribir como un producto de dos elementos).
Suponga primero que y (estos casos se hacen mucho más fácilmente). Es necesario calcular los invariantes j elípticos de las clases h ( D ) del orden del discriminante D como números complejos. Hay varias fórmulas para calcularlos.
Luego crea el polinomio monico , que tiene raíces correspondientes a los valores de h ( D ). Tenga en cuenta quees el polinomio de la clase . De la teoría de la multiplicación compleja, sabemos que tiene coeficientes enteros, lo que nos permite estimar estos coeficientes con la suficiente precisión para descubrir sus valores verdaderos.
Ahora, si N es primo, CM nos dice quedivide módulo N en un producto de h ( D ) factores lineales, basándose en el hecho de que D se eligió de modo que N se divide como el producto de dos elementos. Ahora, si j es una de las raíces h ( D ) módulo N , podemos definir E como:
c es cualquier mod N cuadrático no residual , y r es 0 o 1.
Dada una raíz j , solo hay dos posibles opciones no isomórficas de E , una para cada opción de r . Tenemos la cardinalidad de estas curvas como
- o [1] [9] [11]
Discusión
Al igual que con la prueba Goldwasser-Killian, ésta conduce a un procedimiento de bajada. Nuevamente, el culpable es q . Una vez que encontremos una q que funcione, debemos verificar que sea primo, por lo que, de hecho, ahora estamos haciendo toda la prueba para q . Entonces, nuevamente, es posible que tengamos que realizar la prueba para los factores de q . Esto conduce a un certificado anidado donde en cada nivel tenemos una curva elíptica E , una my la prima en duda, q .
Ejemplo de ECPP de Atkin-Morain
Construimos un ejemplo para demostrar que es primordial con la prueba ECPP de Atkin-Morain. Primero proceda a través del conjunto de 13 posibles discriminantes, probando si el símbolo de Legendre, y si 4 N se puede escribir como.
Por nuestro ejemplo esta elegido. Esto es porquey también, utilizando el algoritmo de Cornacchia , sabemos quey así a = 25 y b = 1.
El siguiente paso es calcular m . Esto se hace fácilmente como cuyos rendimientos A continuación, necesitamos encontrar un divisor primo probable de m , al que se hizo referencia como q . Debe satisfacer la condición de que
En este caso, m = 143 = 11 × 13. Entonces, desafortunadamente, no podemos elegir 11 o 13 como nuestra q , ya que no satisface la desigualdad necesaria. Sin embargo, nos salva una proposición análoga a la que planteamos antes del algoritmo Goldwasser-Kilian, que proviene de un artículo de Morain. [12] Dice que, dada nuestra m , buscamos una s que divida a m ,, pero no es necesariamente primo, y compruebe si, para cada que divide s
para algún punto P en nuestra curva aún por construir.
Si s satisface la desigualdad y sus factores primos satisfacen lo anterior, entonces N es primo.
Entonces, en nuestro caso, elegimos s = m = 143. Por lo tanto, nuestro posibleson 11 y 13. Primero, está claro que , por lo que solo necesitamos verificar los valores de
Pero antes de que podamos hacer esto, debemos construir nuestra curva, y elegir un punto P . Para construir la curva, utilizamos la multiplicación compleja. En nuestro caso calculamos el invariante J
A continuación calculamos
y sabemos que nuestra curva elíptica tiene la forma:
- ,
donde k es como se describió anteriormente yc un no cuadrado en. Entonces podemos comenzar con
cuyos rendimientos
Ahora, utilizando el punto P = (6,6) en E se puede verificar que
Es sencillo comprobar que 13 (6, 6) = (12, 65) y 11 P = (140, 147), por lo que, según la proposición de Morain, N es primo.
Complejidad y tiempos de ejecución
El algoritmo de prueba de primalidad de curva elíptica de Goldwasser y Kilian termina en el tiempo polinomial esperado durante al menos
de insumos primarios.
Conjetura
Dejar ser el número de primos menor que x
para x suficientemente grande .
Si se acepta esta conjetura, entonces el algoritmo Goldwasser-Kilian termina en el tiempo polinomial esperado para cada entrada. Además, si nuestra N es de longitud k , entonces el algoritmo crea un certificado de tamaño que se puede verificar en . [13]
Ahora considere otra conjetura, que nos dará un límite en el tiempo total del algoritmo.
Conjetura 2
Supongamos que existen constantes positivas y tal que la cantidad de primos en el intervalo
- Es mas grande que
Luego, el algoritmo de Goldwasser Kilian demuestra la primordialidad de N en un tiempo esperado de
- [12]
Para el algoritmo de Atkin-Morain, el tiempo de ejecución indicado es
- para algunos [3]
Primas de forma especial
Para algunas formas de números, es posible encontrar 'atajos' a una prueba de primalidad. Este es el caso de los números de Mersenne . De hecho, debido a su estructura especial, que permite una verificación más fácil de la primalidad, los seis números primos más grandes conocidos son todos números de Mersenne. [14] Ha habido un método en uso durante algún tiempo para verificar la primacía de los números de Mersenne, conocido como la prueba de Lucas-Lehmer . Esta prueba no se basa en curvas elípticas. Sin embargo, presentamos un resultado donde los números de la forma dónde , n impar se puede probar como primo (o compuesto) utilizando curvas elípticas. Por supuesto, esto también proporcionará un método para demostrar la primacía de los números de Mersenne, que corresponden al caso donde n = 1. Existe un método para probar esta forma de número sin curvas elípticas (con una limitación en el tamaño de k) conocida como la prueba de Lucas-Lehmer-Riesel . El siguiente método se extrae de la prueba de primalidad en papelusando curvas elípticas , por Yu Tsumura. [15]
Estructura de grupo de
Tomamos E como nuestra curva elíptica, donde E tiene la forma por dónde es primo, y con impar.
- Teorema 1. [6]
- Teorema 2. o dependiendo de si m es un residuo cuadrático módulo p .
- Teorema 3. Sea Q = ( x , y ) en E tal que x sea un módulo p cuadrático sin residuos . Entonces el orden de Q es divisible por en el grupo cíclico
Primero presentaremos el caso donde n es relativamente pequeño con respecto a, y esto requerirá un teorema más:
- Teorema 4. Elija un y supongo
- Entonces p es un primo si y solo si existe un Q = ( x , y ) en E , tal que para i = 1, 2, ..., k - 1 y dónde es una secuencia con valor inicial
El algoritmo
Proporcionamos el siguiente algoritmo, que se basa principalmente en los teoremas 3 y 4. Para verificar la primacía de un número dado , realice los siguientes pasos:
(1) Elija tal que , y encontrar tal que .
Llevar y .
Luego Está encendido .
Calcular . Si luego es compuesto; de lo contrario, proceda a (2).
(2) Conjunto como la secuencia con valor inicial . Calcular por .
Si por un , dónde luego es compuesto. De lo contrario, continúe con (3).
(3) Si luego es primordial. De lo contrario,es compuesto. Esto completa la prueba.
Justificación del algoritmo
En (1), se elige una curva elíptica, E , junto con un punto Q en E , de modo que la coordenada x de Q es un no residuo cuadrático. Podemos decir
Por tanto, si N es primo, Q ' tiene un orden divisible por, por el Teorema 3, y por lo tanto el orden de Q ' es d | n .
Esto significa que Q = nQ ' tiene orden. Por lo tanto, si (1) concluye que N es compuesto, realmente es compuesto. (2) y (3) compruebe si Q tiene orden. Por lo tanto, si (2) o (3) concluyen que N es compuesto, es compuesto.
Ahora, si el algoritmo concluye que N es primo, eso significasatisface la condición del teorema 4, por lo que N es realmente primo.
También existe un algoritmo para cuando n es grande, sin embargo, para esto nos referimos al artículo mencionado anteriormente. [15]
Referencias
- ↑ a b c Henri Cohen, Gerhard Frey, ed. (2006). Manual de criptografía de curvas elípticas e hiperelípticas . Boca Ratón: Chapman & Hall / CRC.
- ^ Arriba, Jaap, Demostración de primordialidad de curva elíptica , http://www.math.rug.nl/~top/atkin.pdf
- ^ a b c Atkin, AOL, Morain, F., Curvas elípticas y prueba de primordialidad , https://www.ams.org/mcom/1993-61-203/S0025-5718-1993-1199989-X/S0025-5718 -1993-1199989-X.pdf
- ^ Lenstra, Jr., AK; Lenstra, HW, Jr. (1990). "Algoritmos en teoría de números". Manual de Informática Teórica: Algoritmos y Complejidad . Amsterdam y Nueva York: The MIT Press. A : 673–715.
- ^ Caldwell, Chris. Los veinte primeros: prueba de primalidad de curva elíptica de las páginas principales .
- ^ a b Washington, Lawrence C. , Curvas elípticas: teoría de números y criptografía , Chapman y Hall / CRC, 2003
- ^ a b Koblitz, Neal, Introducción a la teoría de números y la criptografía , 2da edición, Springer, 1994
- ^ http://www.mast.queensu.ca/~math418/m418oh/m418oh27.pdf
- ^ a b Blake, Ian F., Seroussi, Gadiel, Smart, Nigel Paul, Curvas elípticas en criptografía , Cambridge University Press, 1999
- ^ Lenstra, Hendrik W., Algoritmos eficientes en teoría de números , https://openaccess.leidenuniv.nl/bitstream/1887/2141/1/346_081.pdf
- ^ http://algo.inria.fr/seminars/sem97-98/morain.html
- ^ a b Morain, Francois, Implementación del algoritmo de prueba de primordialidad Atkin-Goldwasser-Kilian, https://hal.archives-ouvertes.fr/docs/00/07/56/45/PDF/RR-0911.pdf
- ^ Goldwasser, Shafi, Kilian, Joe, Casi todos los Primes pueden ser certificados rápidamente , http://www.iai.uni-bonn.de/~adrian/ecpp/p316-goldwasser.pdf Archivado el 18 de julio de 2011 en el Wayback Máquina
- ^ http://primes.utm.edu/notes/by_year.html
- ^ a b Tsumura, Yu, Pruebas de primordialidad paraUsando curvas elípticas , arXiv : 0912.5279v1
enlaces externos
- Curvas elípticas y prueba de primalidad de Atkin y Morain.
- Weisstein, Eric W. "Demostración de primalidad de curva elíptica" . 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)
- PARI / GP , un sistema de álgebra informática con funciones para crear certificados de primalidad Atkin-Morain y Primo
- GMP-ECPP , una implementación gratuita de ECPP
- LiDIA , una biblioteca C ++ gratuita para Linux con soporte ECPP