Polinomios de división

En matemáticas, la división de polinomios proporciona una forma de calcular múltiplos de puntos en curvas elípticas y de estudiar los campos generados por los puntos de torsión. Desempeñan un papel central en el estudio de los puntos de conteo en curvas elípticas en el algoritmo de Schoof .

Definición

El conjunto de polinomios de división es una secuencia de polinomios con variables libres que se define recursivamente por: ${\displaystyle \mathbb {Z} [x,y,A,B]}$ ${\displaystyle x,y,A,B}$

${\displaystyle \psi _{0}=0}$

${\displaystyle \psi _{1}=1}$

${\displaystyle \psi _{2}=2y}$

${\displaystyle \psi _{3}=3x^{4}+6Ax^{2}+12Bx-A^{2}}$

${\displaystyle \psi _{4}=4y(x^{6}+5Ax^{4}+20Bx^{3}-5A^{2}x^{2}-4ABx-8B^{2}-A^{3})}$

${\displaystyle \vdots }$

${\displaystyle \psi _{2m+1}=\psi _{m+2}\psi _{m}^{3}-\psi _{m-1}\psi _{m+1}^{3}{\text{ for }}m\geq 2}$

${\displaystyle \psi _{2m}=\left({\frac {\psi _{m}}{2y}}\right)\cdot (\psi _{m+2}\psi _{m-1}^{2}-\psi _{m-2}\psi _{m+1}^{2}){\text{ for }}m\geq 3}$

El polinomio se llama polinomio de n- ^{ésima división.} ${\displaystyle \psi _{n}}$

Propiedades

• En la práctica, se establece , y luego y . ${\displaystyle y^{2}=x^{3}+Ax+B}$ ${\displaystyle \psi _{2m+1}\in \mathbb {Z} [x,A,B]}$ ${\displaystyle \psi _{2m}\in 2y\mathbb {Z} [x,A,B]}$
• Los polinomios de división forman una secuencia de divisibilidad elíptica genérica sobre el anillo . ${\displaystyle \mathbb {Q} [x,y,A,B]/(y^{2}-x^{3}-Ax-B)}$
• Si se da una curva elíptica en la forma de Weierstrass sobre algún campo , es decir , se pueden usar estos valores de y considerar los polinomios de división en el anillo de coordenadas de . Las raíces de son las coordenadas de los puntos de , donde es el subgrupo de torsión de . De manera similar, las raíces de son las coordenadas de los puntos de . ${\displaystyle E}$ ${\displaystyle y^{2}=x^{3}+Ax+B}$ ${\displaystyle K}$ ${\displaystyle A,B\in K}$ ${\displaystyle A,B}$ ${\displaystyle E}$ ${\displaystyle \psi _{2n+1}}$ ${\displaystyle x}$ ${\displaystyle E[2n+1]\setminus \{O\}}$ ${\displaystyle E[2n+1]}$ ${\displaystyle (2n+1)^{\text{th}}}$ ${\displaystyle E}$ ${\displaystyle \psi _{2n}/y}$ ${\displaystyle x}$ ${\displaystyle E[2n]\setminus E[2]}$
• Dado un punto en la curva elíptica sobre algún campo , podemos expresar las coordenadas del n ^ésimo múltiplo de en términos de polinomios de división: ${\displaystyle P=(x_{P},y_{P})}$ ${\displaystyle E:y^{2}=x^{3}+Ax+B}$ ${\displaystyle K}$ ${\displaystyle P}$

${\displaystyle nP=\left({\frac {\phi _{n}(x)}{\psi _{n}^{2}(x)}},{\frac {\omega _{n}(x,y)}{\psi _{n}^{3}(x,y)}}\right)=\left(x-{\frac {\psi _{n-1}\psi _{n+1}}{\psi _{n}^{2}(x)}},{\frac {\psi _{2n}(x,y)}{2\psi _{n}^{4}(x)}}\right)}$

donde y están definidos por: ${\displaystyle \phi _{n}}$ ${\displaystyle \omega _{n}}$

${\displaystyle \phi _{n}=x\psi _{n}^{2}-\psi _{n+1}\psi _{n-1},}$

${\displaystyle \omega _{n}={\frac {\psi _{n+2}\psi _{n-1}^{2}-\psi _{n-2}\psi _{n+1}^{2}}{4y}}.}$

Usando la relación entre y , junto con la ecuación de la curva, las funciones , , están todas en . ${\displaystyle \psi _{2m}}$ ${\displaystyle \psi _{2m+1}}$ ${\displaystyle \psi _{n}^{2}}$ ${\displaystyle {\frac {\psi _{2n}}{y}},\psi _{2n+1}}$ ${\displaystyle \phi _{n}}$ ${\displaystyle K[x]}$

Sea primo y sea una curva elíptica sobre el campo finito , es decir ,. El grupo de torsión de over es isomorfo a if y a or if . Por tanto, el grado de es igual a , o 0. ${\displaystyle p>3}$ ${\displaystyle E:y^{2}=x^{3}+Ax+B}$ ${\displaystyle \mathbb {F} _{p}}$ ${\displaystyle A,B\in \mathbb {F} _{p}}$ ${\displaystyle \ell }$ ${\displaystyle E}$ ${\displaystyle {\bar {\mathbb {F} }}_{p}}$ ${\displaystyle \mathbb {Z} /\ell \times \mathbb {Z} /\ell }$ ${\displaystyle \ell \neq p}$ ${\displaystyle \mathbb {Z} /\ell }$ ${\displaystyle \{0\}}$ ${\displaystyle \ell =p}$ ${\displaystyle \psi _{\ell }}$ ${\displaystyle {\frac {1}{2}}(l^{2}-1)}$ ${\displaystyle {\frac {1}{2}}(l-1)}$

René Schoof observó que trabajar en módulo el polinomio de división permite trabajar con todos los puntos de torsión simultáneamente. Esto se usa mucho en el algoritmo de Schoof para contar puntos en curvas elípticas. ${\displaystyle \ell }$ ${\displaystyle \ell }$

Ver también

• algoritmo de Schoof

Referencias

• A. Enge: Curvas elípticas y sus aplicaciones a la criptografía: una introducción . Editorial académica Kluwer, Dordrecht, 1999.
• N. Koblitz: un curso de teoría de números y criptografía , Textos de posgrado en matemáticas. n° 114, Springer-Verlag, 1987. Segunda edición, 1994
• Müller: Die Berechnung der Punktanzahl von elliptischen kurven über endlichen Primkörpern . Tesis de maestría. Universität des Saarlandes, Saarbrücken, 1991.
• G. Musiker: Algoritmo de Schoof para contar puntos en ${\displaystyle E(\mathbb {F} _{q})}$ . Disponible en https://www-users.cse.umn.edu/~musiker/schoof.pdf
• 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
• LC Washington: Curvas elípticas: teoría de números y criptografía . Chapman & Hall/CRC, Nueva York, 2003.
• J. Silverman: La aritmética de las curvas elípticas , Springer-Verlag, GTM 106, 1986.