{
  "id": "enwiki-001289128105",
  "slug": "division-polynomials",
  "title": "Division polynomials",
  "qid": "",
  "lead": "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.",
  "body": "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. \\psi_{0} = 0 \\psi_{1} = 1 \\psi_{2} = 2y \\psi_{3} = 3x^{4} + 6Ax^{2} + 12Bx - A^{2} \\psi_{4} = 4y(x^{6} + 5Ax^{4} + 20Bx^{3} - 5A^{2}x^{2} - 4ABx - 8B^{2} - A^{3}) \\vdots \\psi_{2m+1} = \\psi_{m+2} \\psi_{m}^{ 3} - \\psi_{m-1} \\psi ^{ 3}_{ m+1} \\text{ for } m \\geq 2 \\psi_{ 2m} = \\left ( \\frac { \\psi_{m}}{2y} \\right ) \\cdot ( \\psi_{m+2}\\psi^{ 2}_{m-1} - \\psi_{m-2} \\psi ^{ 2}_{m+1}) \\text{ for } m \\geq 3 The polynomial \\psi_n is called the n th division polynomial. In practice, one sets y^2=x^3+Ax+B , and then \\psi_{2m+1}\\in\\mathbb{Z}[x,A,B] and \\psi_{2m}\\in 2y\\mathbb{Z}[x,A,B] . The division polynomials form a generic elliptic divisibility sequence over the ring \\mathbb{Q}[x,y,A,B]/(y^2-x^3-Ax-B) . If an elliptic curve E is given in the Weierstrass form y^2=x^3+Ax+B over some field K , i.e. A, B\\in K , one can use these values of A, B and consider the division polynomials in the coordinate ring of E . The roots of \\psi_{2n+1} are the x -coordinates of the points of E[2n+1]\\setminus \\{O\\} , where E[2n+1] is the (2n+1)^{\\text{th}} torsion subgroup of E . Similarly, the roots of \\psi_{2n}/y are the x -coordinates of the points of E[2n]\\setminus E[2] . Given a point P=(x_P,y_P) on the elliptic curve E:y^2=x^3+Ax+B over some field K , we can express the coordinates of the n th multiple of P in terms of division polynomials: nP= \\left ( \\frac{\\phi_{n}(x)}{\\psi_{n}^{2}(x)}, \\frac{\\omega_{n}(x,y)}{\\psi^{3}_{n}(x,y)} \\right) = \\left( x - \\frac {\\psi_{n-1} \\psi_{n+1}}{\\psi^{2}_{n}(x)}, \\frac{\\psi_{2 n}(x,y)}{2\\psi^{4}_{n}(x)} \\right) where \\phi_{n} and \\omega_{n} are defined by: \\phi_{n}=x\\psi_{n}^{2} - \\psi_{n+1}\\psi_{n-1}, \\omega_{n}=\\frac{\\psi_{n+2}\\psi_{n-1}^{2}-\\psi_{n-2}\\psi_{n+1}^{2}}{4y}. Using the relation between \\psi_{2m} and \\psi _{2m + 1} , along with the equation of the curve, the functions \\psi_{n}^{2} , \\frac{\\psi_{2n}}{y}, \\psi_{2n + 1} , \\phi_{n} are all in K[x] . Let p>3 be prime and let E:y^2=x^3+Ax+B be an elliptic curve over the finite field \\mathbb{F}_p , i.e., A,B \\in \\mathbb{F}_p . The \\ell -torsion group of E over \\bar{ \\mathbb{F}}_p is isomorphic to \\mathbb{Z}/\\ell \\times \\mathbb{Z}/\\ell if \\ell\\neq p , and to \\mathbb{Z}/\\ell or \\{0\\} if \\ell=p . Hence the degree of \\psi_\\ell is equal to either \\frac{1}{2}(l^2-1) , \\frac{1}{2}(l-1) , or 0. René Schoof observed that working modulo the \\ell th division polynomial allows one to work with all \\ell -torsion points simultaneously. This is heavily used in Schoof's algorithm for counting points on elliptic curves.",
  "categories": [
    "26709316",
    "29176147"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1289128105",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1746544217.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001289128105",
    "type": "webpage",
    "title": "Division polynomials",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/division-polynomials",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          17
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          17
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001289128105",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1289128105",
    "note": "Immutable snapshot enwiki-001289128105"
  }
}