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. 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. The set of division polynomials is a sequence of polynomials in Z [ x , y , A , B ] {displaystyle mathbb {Z} } with x , y , A , B {displaystyle x,y,A,B} free variables that is recursively defined by: The polynomial ψ n {displaystyle psi _{n}} is called the nth division polynomial. 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} . 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,Bin mathbb {F} _{p}} . The ℓ {displaystyle ell } -torsion group of E {displaystyle E} over F ¯ p {displaystyle {ar {mathbb {F} }}_{p}} is isomorphic to Z / ℓ × Z / ℓ {displaystyle mathbb {Z} /ell imes mathbb {Z} /ell } if ℓ ≠ p {displaystyle ell eq 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.