Division polynomials

In mathematics the division polynomials provide a way to calculate multiples of points on elliptic curves over Finite fields. They play a central role in the study of counting points on elliptic curves in Schoof's algorithm.
Contents
Definition
The division polynomials are a sequence of polynomials in with x,y,A,B free variables that is recursively defined by:

 ψ_{0} = 0

 ψ_{1} = 1

 ψ_{2} = 2y

 ψ_{3} = 3x^{4} + 6Ax^{2} + 12Bx − A^{2}

 ψ_{4} = 4y(x^{6} + 5Ax^{4} + 20Bx^{3} − 5A^{2}x^{2} − 4ABx − 8B^{2} − A^{3})
The polynomial ψ_{n} is called the n^{th} division polynomial.
Properties
 ψ_{2n + 1} is a polynomial in Z[x,y^{2},A,B], while ψ_{2m} is a polynomial in 2yZ[x,y^{2},A,B].
 The division polynomials form an elliptic divisibility sequence. Moreover all nonsingular elliptic divisibility sequences arise this way.
 If an elliptic curve E is given in the Weierstrass form y^{2} = x^{3} + Ax + B over some field K, i.e. one can evaluate the division polynomials at those A,B and consider them as polynomials in the coordinate ring. Then the powers of y can only be less or equal to 1, as y^{2} is replaced by x^{3} + Ax + B. In particular, ψ_{2n + 1} is a univariate polynomial in x only. The roots of the (2n + 1)^{th} division polynomial ψ_{2n + 1} are exactly the x coordinates of the points of , where E[2n + 1] is the (2n + 1)^{th} torsion subgroup of the group E of an elliptic curve.
 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:

 where ϕ_{n} and ω_{n} are defined by:
Using the relation between ψ_{2m} and ψ_{2m + 1}, along with the equation of the curve, we have that , and ϕ_{n} are all functions in the variable x.
Let p > 3 be prime and let be an elliptic curve over the finite field . The ltorsion group of E over is isomorphic to if and to of {0} otherwise which means that the degree of ψ_{l} is (l^{2} − 1) / 2, (l − 1) / 2 or 0.
René Schoof observed that working modulo the lth division polynomial means working with all ltorsion points simultaneously. This is heavily used in Schoof's algorithm for counting points on elliptic curves.
See also
References
 A. Brown: Algorithms for Elliptic Curves over Finite Fields, EPFL — LMA. Available at http://algo.epfl.ch/handouts/en/andrew.pdf
 A. Enge: Elliptic Curves and their Applications to Cryptography: An Introduction. Kluwer Academic Publishers, Dordrecht, 1999.
 N. Koblitz: A Course in Number Theory and Cryptography, Graduate Texts in Math. No. 114, SpringerVerlag, 1987. Second edition, 1994
 Müller : Die Berechnung der Punktanzahl von elliptischen kurvenüber endlichen Primkörpern. Master's Thesis. Universität des Saarlandes, Saarbrücken, 1991.
 G. Musiker: Schoof's Algorithm for Counting Points on . Available at http://wwwmath.mit.edu/~musiker/schoof.pdf
 Schoof: Elliptic Curves over Finite Fields and the Computation of Square Roots mod p. Math. Comp., 44(170):483–494, 1985. Available at http://www.mat.uniroma2.it/~schoof/ctpts.pdf
 R. Schoof: Counting Points on Elliptic Curves over Finite Fields. J. Theor. Nombres Bordeaux 7:219–254, 1995. Available at http://www.mat.uniroma2.it/~schoof/ctg.pdf
 L. C. Washington: Elliptic Curves: Number Theory and Cryptography. Chapman & Hall/CRC, New York, 2003.
 J. Silverman: The Arithmetic of Elliptic Curves, SpringerVerlag, GTM 106, 1986.
Categories: Polynomials
 Algebraic curves

Wikimedia Foundation. 2010.
Look at other dictionaries:
División polinomial — Saltar a navegación, búsqueda En álgebra, división polinomial es un algoritmo que permite dividir un polinomio por otro polinomio de igual o menor grado. El algoritmo es una versión generalizada de la técnica aritmética de división. Es fácilmente … Wikipedia Español
Division (mathematics) — Divided redirects here. For other uses, see Divided (disambiguation). For the digital implementation of mathematical division, see Division (digital). In mathematics, especially in elementary arithmetic, division (÷ … Wikipedia
Greatest common divisor of two polynomials — Informally, the greatest common divisor (GCD) of two polynomials p ( x ) and q ( x ) is the biggest polynomial that divides evenly into both p ( x ) and q ( x ). The definition is modeled on the concept of the greatest common divisor of two… … Wikipedia
Polynomial long division — In algebra, polynomial long division is an algorithm for dividing a polynomial by another polynomial of the same or lower degree, a generalised version of the familiar arithmetic technique called long division. It can be done easily by hand,… … Wikipedia
Chebyshev polynomials — Not to be confused with discrete Chebyshev polynomials. In mathematics the Chebyshev polynomials, named after Pafnuty Chebyshev,[1] are a sequence of orthogonal polynomials which are related to de Moivre s formula and which can be defined… … Wikipedia
Multivariate division algorithm — In mathematics, polynomials in more than one variable do not form a Euclidean domain, so it is not possible to construct a true division algorithm; but an approximate multivariate division algorithm can be constructed. Given a polynomial g,… … Wikipedia
Calculus with polynomials — Topics in Calculus Fundamental theorem Limits of functions Continuity Mean value theorem Differential calculus Derivative Change of variables Implicit differentiation Taylor s theorem Related rates … Wikipedia
Long division — For the album by Rustic Overtones, see Long Division.In arithmetic, long division is the standard procedure suitable for dividing simple or complex multidigit numbers. It breaks down a division problem into a series of easier steps. As in all… … Wikipedia
Counting points on elliptic curves — An important aspect in the study of elliptic curves is devising effective ways of counting points on the curve. There have been several approaches to do so, and the algorithms devised have proved to be useful tools in the study of various fields… … Wikipedia
Riemann surface — For the Riemann surface of a subring of a field, see Zariski–Riemann space. Riemann surface for the function ƒ(z) = √z. The two horizontal axes represent the real and imaginary parts of z, while the vertical axis represents the real… … Wikipedia