El algoritmo de Schoof es un algoritmo eficiente para contar puntos en curvas elípticas sobre campos finitos . El algoritmo tiene aplicaciones en criptografía de curva elíptica donde es importante conocer el número de puntos para juzgar la dificultad de resolver el problema del logaritmo discreto en el grupo de puntos de una curva elíptica.
El algoritmo fue publicado por René Schoof en 1985 y supuso un avance teórico, ya que fue el primer algoritmo de tiempo polinomial determinista para contar puntos en curvas elípticas . Antes del algoritmo de Schoof, los enfoques para contar puntos en curvas elípticas, como los algoritmos ingenuos y pasos gigantes , eran, en su mayor parte, tediosos y tenían un tiempo de ejecución exponencial.
Este artículo explica el enfoque de Schoof, haciendo hincapié en las ideas matemáticas que subyacen a la estructura del algoritmo.
Introducción
Dejar ser una curva elíptica definida sobre el campo finito, dónde por un primo y un entero . Sobre un campo de característica una curva elíptica puede estar dada por una ecuación de Weierstrass (corta)
con . El conjunto de puntos definidos sobre consta de las soluciones satisfaciendo la ecuación de la curva y un punto en el infinito . Usando la ley de grupo en curvas elípticas restringidas a este conjunto, se puede ver que este conjuntoforma un grupo abeliano , conactuando como el elemento cero. Para contar puntos en una curva elíptica, calculamos la cardinalidad de. El enfoque de Schoof para calcular la cardinalidadhace uso del teorema de Hasse sobre curvas elípticas junto con el teorema del resto chino y los polinomios de división .
Teorema de hasse
El teorema de Hasse establece que si es una curva elíptica sobre el campo finito , luego satisface
Este poderoso resultado, dado por Hasse en 1934, simplifica nuestro problema al reducir a un conjunto finito (aunque grande) de posibilidades. Definiendo ser - estar , y haciendo uso de este resultado, ahora tenemos que calcular el valor de modulo dónde , es suficiente para determinar , y por lo tanto . Si bien no existe una forma eficiente de calcular directamente para general , es posible calcular por una pequeña prima, con bastante eficiencia. Nosotros elegimos ser un conjunto de números primos distintos de modo que . Dado para todos , el teorema del resto chino nos permite calcular.
Para calcular por un primo , hacemos uso de la teoría del endomorfismo de Frobenius y polinomios de división . Tenga en cuenta que teniendo en cuenta los números primosno es una pérdida, ya que siempre podemos elegir una prima más grande para que ocupe su lugar y garantizar que el producto sea lo suficientemente grande. En cualquier caso, el algoritmo de Schoof se utiliza con mayor frecuencia para abordar el caso ya que son más eficientes, los llamados algoritmos adic para campos de características pequeñas.
El endomorfismo de Frobenius
Dada la curva elíptica definido sobre consideramos puntos en encima , el cierre algebraico de; es decir, permitimos puntos con coordenadas en. El endomorfismo de Frobenius de encima se extiende a la curva elíptica por .
Este mapa es la identidad en y se puede extender hasta el infinito , convirtiéndolo en un morfismo grupal de a sí mismo.
El endomorfismo de Frobenius satisface un polinomio cuadrático que está vinculado a la cardinalidad de por el siguiente teorema:
Teorema: El endomorfismo de Frobenius dado por satisface la ecuación característica
- dónde
Así tenemos para todos que , donde + denota la suma en la curva elíptica y y denotar multiplicación escalar de por y de por .
Se podría intentar calcular simbólicamente estos puntos , y como funciones en el anillo de coordenadas de y luego busque un valor de que satisface la ecuación. Sin embargo, los grados se vuelven muy grandes y este enfoque no es práctico.
La idea de Schoof era realizar este cálculo restringido a puntos de orden. para varios primos pequeños . Arreglando un primo impar, ahora pasamos a resolver el problema de determinar , definido como , para una prima dada . Si un punto está en el - subgrupo de torsión , luego dónde es el número entero único tal que y . Tenga en cuenta que y que para cualquier entero tenemos . Por lo tanto tendrá el mismo orden que . Por lo tanto, para perteneciendo a , también tenemos Si . Por lo tanto, hemos reducido nuestro problema a resolver la ecuación
dónde y tener valores enteros en .
Cálculo módulo primos
El polinomio de l- ésima división es tal que sus raíces son precisamente las coordenadas x de puntos de orden l . Por lo tanto, para restringir el cálculo dea los l -puntos de torsión significa calcular estas expresiones como funciones en el anillo de coordenadas de E y módulo el polinomio de la l- ésima división. Es decir, estamos trabajando en. Esto significa, en particular, que el grado de X e Y definido mediantees como máximo 1 en y y como máximoen x .
La multiplicación escalar se puede hacer mediante métodos de doble y suma o utilizando elpolinomio de la división. El último enfoque da:
dónde es el polinomio de n- ésima división. Tenga en cuenta quees una función en x solamente y la denotar por.
Debemos dividir el problema en dos casos: el caso en el que , y el caso en el que . Tenga en cuenta que estas igualdades se comprueban módulo.
Caso 1: [[Categoría: Plantillas con sintaxis de parámetro incorrecta]]}}, y ^ {{q ^
'' 'Uso inesperado de la plantilla {{2}} ' ''; consulte [[Plantilla: 2]] para obtener más detalles. [[Categoría: Plantillas con sintaxis de parámetro incorrecta] ]}}) \ neq \ pm {\ bar {q}} (x, y)" data-section="5" class="mw-ui-icon mw-ui-icon-element mw-ui-icon-wikimedia-edit-base20 edit-page mw-ui-icon-flush-right">Editar
Usando la fórmula de suma para el grupo obtenemos:
Tenga en cuenta que este cálculo falla en caso de que el supuesto de desigualdad fuera incorrecto.
Ahora podemos usar la coordenada x para reducir la elección dea dos posibilidades, a saber, el caso positivo y negativo. El uso de la coordenada y determina cuál de los dos casos es válido.
Primero mostramos que X es una función solo en x . Considerar. Desde es incluso, reemplazando por , reescribimos la expresión como
y tener eso
Aquí, parece que no está bien, tiramos ?
Ahora si para uno luego satisface
para todos l puntos -torsion P .
Como se mencionó anteriormente, el uso de Y y ahora podemos determinar cuál de los dos valores de ( o ) obras. Esto da el valor de. El algoritmo de Schoof almacena los valores de en una variable para cada primo l considerado.
Caso 2: [[Categoría: Plantillas con sintaxis de parámetro incorrecta]]}}, y ^ {{q ^
'' 'Uso inesperado de la plantilla {{2}} ' ''; consulte [[Plantilla: 2]] para obtener más detalles. [[Categoría: Plantillas con sintaxis de parámetro incorrecta] ]}}) = \ pm {\ bar {q}} (x, y)" data-section="6" class="mw-ui-icon mw-ui-icon-element mw-ui-icon-wikimedia-edit-base20 edit-page mw-ui-icon-flush-right">Editar
Comenzamos con la suposición de que . Como l es un primo impar, no puede ser que y por lo tanto . La ecuación característica produce que. Y en consecuencia que. Esto implica que q es un cuadrado módulo l . Dejar. Calcular en y comprobar si . Si es así, es dependiendo de la coordenada y.
Si q resulta no ser un módulo cuadrado l o si la ecuación no es válida para cualquiera de w y, nuestra suposición de que es falso, por lo tanto . La ecuación característica da.
Caso adicional
Si recuerda, nuestras consideraciones iniciales omiten el caso de . Dado que asumimos que q es impar, y en particular, si y solo si tiene un elemento de orden 2. Por definición de adición en el grupo, cualquier elemento de orden 2 debe tener la forma . Por lo tanto si y solo si el polinomio tiene una raíz en , si y solo si .
El algoritmo
Aporte: 1. Una curva elíptica . 2. Un número entero q para un campo finito con . Producción: El número de puntos de E sobre. Elija un conjunto de primos impares S que no contengan p tal que Poner Si , más . Calcular el polinomio de división . Todos los cálculos del ciclo siguiente se realizan en el anillo Para hacer : dejar ser el único entero tal que y . Calcular, y . Si luego Calcular. por hacer : si entonces si luego ; demás . de lo contrario, si q es un módulo cuadrado l, entonces calcule w con calcular Si luego si no luego demás demás Utilice el teorema del resto chino para calcular t módulo N a partir de las ecuaciones, dónde . Producción .
Complejidad
La mayor parte del cálculo se realiza mediante la evaluación de y , por cada prima , eso es computación , , , por cada prima . Esto implica exponenciación en el anillo. y requiere multiplicaciones. Dado que el grado de es , cada elemento del anillo es un polinomio de grado . Según el teorema de los números primos , hay alrededor primos de tamaño , dando eso es y lo obtenemos . Así, cada multiplicación en el anillo requiere multiplicaciones en que a su vez requiere operaciones de bits. En total, el número de operaciones de bits para cada primo es . Dado que este cálculo debe realizarse para cada uno de los primos, la complejidad total del algoritmo de Schoof resulta ser . El uso rápido de polinomios y aritmética de enteros reduce esto a.
Mejoras en el algoritmo de Schoof
En la década de 1990, Noam Elkies , seguido de AOL Atkin , ideó mejoras en el algoritmo básico de Schoof al restringir el conjunto de números primos.considerado antes a los números primos de cierto tipo. Estos llegaron a llamarse números primos de Elkies y primos de Atkin, respectivamente. Un primo se llama primo de Elkies si la ecuación característica: se divide , mientras que una prima de Atkin es una prima que no es una prima de Elkies. Atkin mostró cómo combinar la información obtenida de los números primos de Atkin con la información obtenida de los números primos de Elkies para producir un algoritmo eficiente, que llegó a conocerse como el algoritmo de Schoof-Elkies-Atkin . El primer problema a abordar es determinar si un primo dado es Elkies o Atkin. Para ello, utilizamos polinomios modulares, que provienen del estudio de formas modulares y de una interpretación de curvas elípticas sobre los números complejos como retículas. Una vez que hayamos determinado en qué caso estamos, en lugar de usar polinomios de división , podemos trabajar con un polinomio que tenga un grado menor que el polinomio de división correspondiente: en vez de . Para una implementación eficiente, se utilizan algoritmos probabilísticos de búsqueda de raíces, lo que hace que este sea un algoritmo de Las Vegas en lugar de un algoritmo determinista. Bajo el supuesto heurístico de que aproximadamente la mitad de los números primos hasta un vinculados son números primos de Elkie, esto produce un algoritmo que es más eficiente que el de Schoof, con un tiempo de ejecución esperado de usando aritmética ingenua, y usando aritmética rápida. Aunque se sabe que esta suposición heurística es válida para la mayoría de las curvas elípticas, no se sabe que se mantenga en todos los casos, incluso bajo el GRH .
Implementaciones
Mike Scott implementó varios algoritmos en C ++ y están disponibles con código fuente . Las implementaciones son gratuitas (sin términos ni condiciones) y hacen uso de la biblioteca MIRACL que se distribuye bajo AGPLv3 .
- Implementación del algoritmo de Schoof para con prima .
- Implementación del algoritmo de Schoof para.
Ver también
Referencias
- R. Schoof: Curvas elípticas sobre campos finitos y cálculo de raíces cuadradas mod p. Matemáticas. Comp., 44 (170): 483–494, 1985. Disponible en http://www.mat.uniroma2.it/~schoof/ctpts.pdf
- R. Schoof: Contando puntos en curvas elípticas sobre campos finitos. J. Theor. Nombres Bordeaux 7: 219–254, 1995. Disponible en http://www.mat.uniroma2.it/~schoof/ctg.pdf
- G. Musiker: algoritmo de Schoof para contar puntos en . Disponible en http://www.math.umn.edu/~musiker/schoof.pdf
- V. Müller: Die Berechnung der Punktanzahl von elliptischen kurven über endlichen Primkörpern. Tesis de maestría. Universität des Saarlandes, Saarbrücken, 1991. Disponible en http://lecturer.ukdw.ac.id/vmueller/publications.php
- A. Enge: Curvas elípticas y sus aplicaciones a la criptografía: Introducción. Editores académicos Kluwer, Dordrecht, 1999.
- LC Washington: Curvas elípticas: teoría de números y criptografía. Chapman & Hall / CRC, Nueva York, 2003.
- N. Koblitz: Curso de Teoría de Números y Criptografía, Textos de Posgrado en Matemáticas. No. 114, Springer-Verlag, 1987. Segunda edición, 1994