Polinomios de división

En matemáticas , los polinomios de división proporcionan un método para calcular múltiplos de puntos en curvas elípticas y para estudiar los campos generados por puntos de torsión. Desempeñan un papel fundamental en el estudio del conteo de puntos en curvas elípticas en el algoritmo de Schoof .

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

${\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{ para }}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{ para }}m\geq 3}$

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

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

${\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)}$

dónde${\displaystyle \phi _{n}}$y${\displaystyle \omega _{n}}$se definen por:

${\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}}.}$

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

Dejar${\displaystyle p>3}$ser primordial y dejar${\displaystyle E:y^{2}=x^{3}+Ax+B}$sea ​​una curva elíptica sobre el campo finito${\displaystyle \mathbb {F} _{p}}$, es decir,${\displaystyle A,B\in \mathbb {F} _{p}}$. El${\displaystyle \ell }$-grupo de torsión de${\displaystyle E}$encima${\displaystyle {\bar {\mathbb {F} }}_{p}}$es isomorfo a${\displaystyle \mathbb {Z} /\ell \times \mathbb {Z} /\ell }$si${\displaystyle \ell \neq p}$y a${\displaystyle \mathbb {Z} /\ell }$o${\displaystyle \{0\}}$si${\displaystyle \ell =p}$. Por lo tanto, el grado de${\displaystyle \psi _{\ell }}$es igual a cualquiera de los dos${\displaystyle {\frac {1}{2}}(l^{2}-1)}$,${\displaystyle {\frac {1}{2}}(l-1)}$o 0.

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

• El algoritmo de Schoof

• A. Enge: Curvas elípticas y sus aplicaciones a la criptografía: una introducción . Kluwer Academic Publishers, 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 cuerpos finitos y el cálculo de raíces cuadradas módulo p . Math. Comp., 44(170):483 – 494, 1985. Disponible en http://www.mat.uniroma2.it/~schoof/ctpts.pdf
• R. Schoof: Conteo de puntos en curvas elípticas sobre cuerpos 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.