Algorithms on Elliptic Curves


Průběh přednášky

   (19.2.)    Lecture: Motivation and structure of the course. 1.Curves and functional fields. Terminology, notation and basic facts about coordinate rings and functional fields of affine curves [D, C.1 and C.3].
   Practicals: affine curves in R2, irreducible components, use of the signature of the real quadratic form.

   (26.2.) Practicals: Functional fields of lines, construction of algebraic closure of a finite field.
   Lecture: Curves in projective space, correctness of the definition of the functional field of an irreducible projective curve. Concepts of smooth and singular curves. Normalized discrete valuations on functional fields. [D, C.2-C.5].

   (5.3.) Practicals: Extension of an affine curve into projective space. Normalized discrete valuation of the function field K(x).
   Lecture: Places of the function field and the corresponding normalized discrete valuation [D, C.5], equivalent description of the group structure on an elliptic curve [D, W.3]. 2. Weierstrass curves. Geometric motivation of the notion of genus of a curve and genus of a curve over a general field. Weierstrass polynomials (WEP) and Weierstrass curves. The function field (and therefore group) of an elliptic curve can be expressed in terms of a Weierstrass curve. [D, W.1-4]

   (12.3.) Practicals: K-equivalence of affine WEP. Computing of short WEP.
   Lecture: Affine transformation of WEP. Singularities of WEP of the form y2-f(x) [D, W.1-4]

   (19.3.) Practicals: Smooth WEP, computing singularatiries at sinular curves. Singularities of projective extensions of a smooth affine curve.
   Lecture: WEP of the form y2-f(x) is smooth iff f(x) is separable. Formula testing smoothnes. Smooth projective WEP [D, W.2-3] 3. Aritmetics on a Weierstrass curve. Calculation of group operations on the curve using geometric interpretation. Opposite element (intersection of a curve with a line x1 = c1), sum of two different elements (intersection of a curve with a secant), doubling of an element (intersection of a curve with a tangent). [D, W.4, A]

   (26.3.) Practicals: Secants, tangents and the group operation on the elliptic curves over finite fields.
   Lecture: Time complexity of operations on general and short (i.e. for a1=a2=a3=0) smooth affine Weierstrass curve [D, part A]. Time complexity of operations on short smooth projective Weierstrass curve [D, section A.1].

   (2.4.) Practicals: A tangent and dubling on WEC.
   Lecture: 4. Montgomery curve. Each Montgomery curve is K-equivavalent to a smooth Weierstrass curve, computing of group operations on Montgomery curve [D, section M], correspondence of the first coordinates and determination of the second coordinate of addition over a Montgomery curve.


[D] - Lecture notes of Aleše Drápal