Hide Notes 

Slide 1: GROUP Xiis .. Click to edit Master subtitle style Group Members: Aira Coleen T. Muring Regiel L. Chiong Paulo T. Ybanez 11/15/10
Slide 2: M T A M E H T A S IC 11/15/10
Slide 3: WHAT IS A POLYNOMIAL ?? 11/15/10
Slide 4:  In mathematics, a polynomial is an expression of finite length constructed from variables (also known as indeterminates) and constants, using only the operations of addition, subtraction, multiplication, and nonnegative integer exponents. For example, x2 − 4x + 7 is a polynomial, but x2 − 4/x + 7x3/2 is not, because its second term involves division by the variable x (4/x) and because its third term contains an exponent that is not a whole number (3/2). The term 'polynomial' indicates11/15/10 a simplified
Slide 5:  Polynomials appear in a wide variety of areas of mathematics and science. For example, they are used to form polynomial equations, which encode a wide range of problems, from elementary word problems to complicated problems in the sciences; they are used to define polynomial functions, which appear in settings ranging from basic chemistry and physics to economics and social science ; they are used in calculus and numerical analysis to approximate other functions. In advanced mathematics, 11/15/10
Slide 6: Division Polynomials …. 11/15/10
Slide 7: 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 curv in Schoof's algorithm. 11/15/10
Slide 8:   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 = 3x4 + 6Ax2 + 12Bx − A2 ψ4 = 4y(x6 + 5Ax4 + 20Bx3 − 5A2x2 − 4ABx − 8B2 − A3) The polynomial ψn is called the nth 11/15/10      
Slide 9:  ψ2n + 1 is a polynomial in Z[x,y2,A,B], while ψ2m is a polynomial in 2yZ[x,y2,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 y2 = x3 + 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 y2 is replaced by x3 + Ax +11/15/10 particular, B. In
Slide 10:  Given a point P = (xP,yP) on the elliptic curve E:y2 = x3 + Ax + B over some field K, we can express the coordinates of the nth multiple of P in terms of division polynomials: where φn and 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 l-torsion group of E over is isomorphic to if and to of {0} otherwise which means that the degree of ψl is (l2 − 1) / 2, (l − 1) / 2 or 0. René Schoof observed that working modulo the lth division polynomial means working with all l-torsion points simultaneously. This is heavily used in Schoof's algorithm for counting points on elliptic curves ωn are defined by: 11/15/10    
Slide 11:   Polynomial Division Recall how to perform long division.  We will divide 4321 by 6.  We see that we follow the steps: Write it in long division form. Determine what we need to multiply the quotient by to get the first term. Place that number on top of the long division sign. 11/15/10   
Slide 12:    Example Divide         4321                                  6 Solution                720         6 | 4321                42        6 x 7  = 42                12       43 - 42  =  1 and drop down the 2                12       6 x 2  =  12  11/15/10  
Slide 13:     Solution We first write in long division form         Next decide what we need to multiply x2 by to get x4.  Since          (x2)(x2)  =  x4  we can write         Next, we multiply x2 + 7x and x2.         Now subtract to get and bring down the 3x2 11/15/10      
Slide 14:    Division of Polynomials Polynomials are expressions involving x raised to a whole number power (exponent). Some examples are: In this lesson we consider division of polynomials such as: and . There are two ways to calculate a division of polynomials. One is long division and a second method is called synthetic division. Synthetic division can be used when the polynomial divisor such as x-2 has the highest power of x as 1 and the coefficient of x is also 11/15/10 1. Otherwise, such
Slide 15: or f ks an Th !! ng hi tc a w 11/15/10
Slide 16: PREPARED BY : GROUP Xiis .. Aira Muring .. Regiel Chiong.. Paulo Ybanez 11/15/10