Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Division polynomials
open-in-new
<h2 id="definition">Definition</h2> <p>The set of division polynomials is a sequence of <a href="/facts/Polynomials/Lzak8VVx">polynomials</a> 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: </p> ψ 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} <p>The polynomial ψ n {\displaystyle \psi _{n}} is called the <i>n</i>th division polynomial. </p> <h2 id="properties">Properties</h2> <ul><li>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]} .</li> <li>The division polynomials form a generic <a href="/facts/Elliptic_divisibility_sequence/y5ccgRE6">elliptic divisibility sequence</a> 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)} .</li> <li>If an <a href="/facts/Elliptic_curve/60jvaHSA">elliptic curve</a> E {\displaystyle E} is given in the <a href="/facts/Weierstrass_form/GHRXDknk">Weierstrass form</a> 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 <a href="/facts/Imaginary_hyperelliptic_curve/Q6s08NuU">coordinate ring</a> 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}}} <a href="/facts/Torsion_subgroup/dIwLuG5j">torsion subgroup</a> 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]} .</li> <li>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:</li></ul> 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}}.} <p>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]} . </p><p>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 <a href="/facts/Elliptic_curve/60jvaHSA">elliptic curve</a> 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 <a href="/facts/Isomorphic_(mathematics)/pj8KgkxU">isomorphic</a> 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. </p><p><a href="/facts/Ren%25C3%25A9_Schoof/lHMtQACY">René Schoof</a> observed that working modulo the ℓ {\displaystyle \ell } <i>th</i> division polynomial allows one to work with all ℓ {\displaystyle \ell } -torsion points simultaneously. This is heavily used in <a href="/facts/Schoof%2527s_algorithm/0JIRl1pP">Schoof's algorithm</a> for counting points on elliptic curves. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Schoof%2527s_algorithm/0JIRl1pP">Schoof's algorithm</a></li></ul> <ul><li>A. Enge: <i>Elliptic Curves and their Applications to Cryptography: An Introduction</i>. Kluwer Academic Publishers, Dordrecht, 1999.</li> <li>N. Koblitz: <i>A Course in Number Theory and Cryptography</i>, Graduate Texts in Math. No. 114, Springer-Verlag, 1987. Second edition, 1994</li> <li>Müller : <i>Die Berechnung der Punktanzahl von elliptischen kurven über endlichen Primkörpern</i>. Master's Thesis. Universität des Saarlandes, Saarbrücken, 1991.</li> <li>G. Musiker: <i>Schoof's Algorithm for Counting Points on E ( F q ) {\displaystyle E(\mathbb {F} _{q})} </i>. Available at <a href="https://www-users.cse.umn.edu/~musiker/schoof.pdf">https://www-users.cse.umn.edu/~musiker/schoof.pdf</a></li> <li>Schoof: <i>Elliptic Curves over Finite Fields and the Computation of Square Roots mod p</i>. Math. Comp., 44(170):483–494, 1985. Available at <a href="http://www.mat.uniroma2.it/~schoof/ctpts.pdf">http://www.mat.uniroma2.it/~schoof/ctpts.pdf</a></li> <li>R. Schoof: <i>Counting Points on Elliptic Curves over Finite Fields</i>. J. Theor. Nombres Bordeaux 7:219–254, 1995. Available at <a href="http://www.mat.uniroma2.it/~schoof/ctg.pdf">http://www.mat.uniroma2.it/~schoof/ctg.pdf</a></li> <li>L. C. Washington: <i>Elliptic Curves: Number Theory and Cryptography</i>. Chapman & Hall/CRC, New York, 2003.</li> <li>J. Silverman: <i>The Arithmetic of Elliptic Curves</i>, Springer-Verlag, GTM 106, 1986.</li></ul>