Division polynomials - Reference.org

On this page

Division polynomials

In mathematics, the division polynomials provide a way to calculate multiples of points on elliptic curves and to study the fields generated by torsion points. They play a central role in the study of counting points on elliptic curves in Schoof's algorithm.

We don't have any images related to Division polynomials yet.

You can add one yourself here.

We don't have any YouTube videos related to Division polynomials yet.

You can add one yourself here.

We don't have any PDF documents related to Division polynomials yet.

You can add one yourself here.

We don't have any Books related to Division polynomials yet.

You can add one yourself here.

We don't have any archived web articles related to Division polynomials yet.

You can submit a link to a page to archive here.

Definition

The set of division polynomials is a sequence of polynomials in Z [ x , y , A , B ] {\displaystyle \mathbb {Z} [x,y,A,B]} with x , y , A , B {\displaystyle x,y,A,B} free variables that is recursively defined by:

ψ 0 = 0 {\displaystyle \psi _{0}=0} ψ 1 = 1 {\displaystyle \psi _{1}=1} ψ 2 = 2 y {\displaystyle \psi _{2}=2y} ψ 3 = 3 x 4 + 6 A x 2 + 12 B x − A 2 {\displaystyle \psi _{3}=3x^{4}+6Ax^{2}+12Bx-A^{2}} ψ 4 = 4 y ( x 6 + 5 A x 4 + 20 B x 3 − 5 A 2 x 2 − 4 A B x − 8 B 2 − A 3 ) {\displaystyle \psi _{4}=4y(x^{6}+5Ax^{4}+20Bx^{3}-5A^{2}x^{2}-4ABx-8B^{2}-A^{3})} ⋮ {\displaystyle \vdots } ψ 2 m + 1 = ψ m + 2 ψ m 3 − ψ m − 1 ψ m + 1 3 for m ≥ 2 {\displaystyle \psi _{2m+1}=\psi _{m+2}\psi _{m}^{3}-\psi _{m-1}\psi _{m+1}^{3}{\text{ for }}m\geq 2} ψ 2 m = ( ψ m 2 y ) ⋅ ( ψ m + 2 ψ m − 1 2 − ψ m − 2 ψ m + 1 2 ) for m ≥ 3 {\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}

The polynomial ψ n {\displaystyle \psi _{n}} is called the nth division polynomial.

Properties

In practice, one sets y 2 = x 3 + A x + B {\displaystyle y^{2}=x^{3}+Ax+B} , and then ψ 2 m + 1 ∈ Z [ x , A , B ] {\displaystyle \psi _{2m+1}\in \mathbb {Z} [x,A,B]} and ψ 2 m ∈ 2 y Z [ x , A , B ] {\displaystyle \psi _{2m}\in 2y\mathbb {Z} [x,A,B]} .
The division polynomials form a generic elliptic divisibility sequence over the ring Q [ x , y , A , B ] / ( y 2 − x 3 − A x − B ) {\displaystyle \mathbb {Q} [x,y,A,B]/(y^{2}-x^{3}-Ax-B)} .
If an elliptic curve E {\displaystyle E} is given in the Weierstrass form y 2 = x 3 + A x + B {\displaystyle y^{2}=x^{3}+Ax+B} over some field K {\displaystyle K} , i.e. A , B ∈ K {\displaystyle A,B\in K} , one can use these values of A , B {\displaystyle A,B} and consider the division polynomials in the coordinate ring of E {\displaystyle E} . The roots of ψ 2 n + 1 {\displaystyle \psi _{2n+1}} are the x {\displaystyle x} -coordinates of the points of E [ 2 n + 1 ] ∖ { O } {\displaystyle E[2n+1]\setminus \{O\}} , where E [ 2 n + 1 ] {\displaystyle E[2n+1]} is the ( 2 n + 1 ) th {\displaystyle (2n+1)^{\text{th}}} torsion subgroup of E {\displaystyle E} . Similarly, the roots of ψ 2 n / y {\displaystyle \psi _{2n}/y} are the x {\displaystyle x} -coordinates of the points of E [ 2 n ] ∖ E [ 2 ] {\displaystyle E[2n]\setminus E[2]} .
Given a point P = ( x P , y P ) {\displaystyle P=(x_{P},y_{P})} on the elliptic curve E : y 2 = x 3 + A x + B {\displaystyle E:y^{2}=x^{3}+Ax+B} over some field K {\displaystyle K} , we can express the coordinates of the nth multiple of P {\displaystyle P} in terms of division polynomials:

n P = ( ϕ n ( x ) ψ n 2 ( x ) , ω n ( x , y ) ψ n 3 ( x , y ) ) = ( x − ψ n − 1 ψ n + 1 ψ n 2 ( x ) , ψ 2 n ( x , y ) 2 ψ n 4 ( x ) ) {\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)} where ϕ n {\displaystyle \phi _{n}} and ω n {\displaystyle \omega _{n}} are defined by: ϕ n = x ψ n 2 − ψ n + 1 ψ n − 1 , {\displaystyle \phi _{n}=x\psi _{n}^{2}-\psi _{n+1}\psi _{n-1},} ω n = ψ n + 2 ψ n − 1 2 − ψ n − 2 ψ n + 1 2 4 y . {\displaystyle \omega _{n}={\frac {\psi _{n+2}\psi _{n-1}^{2}-\psi _{n-2}\psi _{n+1}^{2}}{4y}}.}

Using the relation between ψ 2 m {\displaystyle \psi _{2m}} and ψ 2 m + 1 {\displaystyle \psi _{2m+1}} , along with the equation of the curve, the functions ψ n 2 {\displaystyle \psi _{n}^{2}} , ψ 2 n y , ψ 2 n + 1 {\displaystyle {\frac {\psi _{2n}}{y}},\psi _{2n+1}} , ϕ n {\displaystyle \phi _{n}} are all in K [ x ] {\displaystyle K[x]} .

Let p > 3 {\displaystyle p>3} be prime and let E : y 2 = x 3 + A x + B {\displaystyle E:y^{2}=x^{3}+Ax+B} be an elliptic curve over the finite field F p {\displaystyle \mathbb {F} _{p}} , i.e., A , B ∈ F p {\displaystyle A,B\in \mathbb {F} _{p}} . The ℓ {\displaystyle \ell } -torsion group of E {\displaystyle E} over F ¯ p {\displaystyle {\bar {\mathbb {F} }}_{p}} is isomorphic to Z / ℓ × Z / ℓ {\displaystyle \mathbb {Z} /\ell \times \mathbb {Z} /\ell } if ℓ ≠ p {\displaystyle \ell \neq p} , and to Z / ℓ {\displaystyle \mathbb {Z} /\ell } or { 0 } {\displaystyle \{0\}} if ℓ = p {\displaystyle \ell =p} . Hence the degree of ψ ℓ {\displaystyle \psi _{\ell }} is equal to either 1 2 ( l 2 − 1 ) {\displaystyle {\frac {1}{2}}(l^{2}-1)} , 1 2 ( l − 1 ) {\displaystyle {\frac {1}{2}}(l-1)} , or 0.

René Schoof observed that working modulo the ℓ {\displaystyle \ell } th division polynomial allows one to work with all ℓ {\displaystyle \ell } -torsion points simultaneously. This is heavily used in Schoof's algorithm for counting points on elliptic curves.

Definition

Properties

See also