Samiksha Jaiswal (Editor)

Division polynomials

Updated on
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
Covid-19

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.

Contents

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 nth 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 nth 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.

    References

    Division polynomials Wikipedia


    Similar Topics
    Lance Norick
    Joe Schreiber
    Cindy Frich
    Topics
     
    B
    i
    Link
    H2
    L