Division polynomials

Definition

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

The polynomial ψ n is called the n^th division polynomial.

Properties

In practice, one sets y 2 = x 3 + A x + B , and then ψ 2 m + 1 ∈ Z [ x , A , B ] and ψ 2 m ∈ 2 y 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 ) .

If an elliptic curve E is given in the Weierstrass form y 2 = x 3 + A x + B over some field K , i.e. A , B ∈ K , one can use these values of A , B and consider the division polynomials in the coordinate ring of E . The roots of ψ 2 n + 1 are the x -coordinates of the points of E [ 2 n + 1 ] ∖ { O } , where E [ 2 n + 1 ] is the ( 2 n + 1 ) th torsion subgroup of E . Similarly, the roots of ψ 2 n / y are the x -coordinates of the points of E [ 2 n ] ∖ E [ 2 ] .

Given a point P = ( x P , y P ) on the elliptic curve E : y 2 = x 3 + A x + B over some field K , we can express the coordinates of the n^th multiple of P in terms of division polynomials:

where ϕ n and ω n are defined by: ϕ n = x ψ n 2 − ψ n + 1 ψ n − 1 , ω n = ψ n + 2 ψ n − 1 2 − ψ n − 2 ψ n + 1 2 4 y .

Using the relation between ψ 2 m and ψ 2 m + 1 , along with the equation of the curve, the functions ψ n 2 , ψ 2 n y , ψ 2 n + 1 and ϕ n are all in K [ x ] .

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

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