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, correspondence of the first coordinates and determination of the second coordinate of addition over a Montgomery curve [D, section M].
(9.4.) Practicals: Computing Montgomery's ladder and calculating operations using Montgomery ladder.
Lecture: Montgomery's ladder and its application to computing powers in the group of a Montgomery curve.
Charecterization of WEPs K-equivalent to Montgomery polynomials [D, section M.3-M.6].
(16.4.) Practicals: Deciding which WEPs are K-equivalent to Montgomery polynomials.
Lecture: 5. Edwards curves. Absolute irreducibility and smoothnes of affine (twisted) Edwards curves. [D, section E.1].
(23.4.) Practicals: Points in infinity of a projective Edwards curve.
Lecture: Rational mappings and birational equivalencve. One-to-one correspondence of twisted Edwards curves and Montgomery curves. Closed and generic formulas of the group operation on Edwards curves, points in infinity [D, sections E.1, E.2].
[D] - Lecture notes of Aleše Drápal