elliptic curves
Summary
The points on a nonsingular elliptic curve, together with the point at infinity, form an abelian group. Scalar multiplication is efficient while elliptic-curve DLOG is believed hard.
Concept
Elliptic curves
- set of points that satisfy an equation + point at infinity
- this simplified weierstrass form requires characteristic != 2
the full weierstrass form is
but not covered in co485
Geometric interpretation
- over the real numbers
- over a finite field
Group operation
- on points on the eliptic curve
- line connecting two points -> 3rd intersection -> flip y
Geometric interpretation
- point addition/chord rule
- identity/neutral element
- inverse, flip y
- tangent rule, “exponentiation” for elliptic curve groups
Algebraic interpretation
- using the equation of the tangent
Short weierstrass form
- all elliptic curves have a weierstrass form if the characteristic != 2 or 3
all elliptic curves in fields where
can be expressed in weierstrass form
Common shapes
Group operation for short weierstrass
Computing
Runtime of group operation
- based on the arithmetic operations
Double-and-add
- calculate “exponentiation” in the elliptic curve group,
- same principle as square-and-multiply,