Affine coordinates for Weierstrass curves #
This file defines the type of points on a Weierstrass curve as an inductive, consisting of the point
at infinity and affine points satisfying a Weierstrass equation with a nonsingular condition. This
file also defines the negation and addition operations of the group law for this type, and proves
that they respect the Weierstrass equation and the nonsingular condition. The fact that they form an
abelian group is proven in Mathlib.AlgebraicGeometry.EllipticCurve.Group
.
Mathematical background #
Let W
be a Weierstrass curve over a field F
. A rational point on W
is simply a point
$[X:Y:Z]$ defined over F
in the projective plane satisfying the homogeneous cubic equation
$Y^2Z + a_1XYZ + a_3YZ^2 = X^3 + a_2X^2Z + a_4XZ^2 + a_6Z^3$. Any such point either lies in the
affine chart $Z \ne 0$ and satisfies the Weierstrass equation obtained by replacing $X/Z$ with $X$
and $Y/Z$ with $Y$, or is the unique point at infinity $0 := [0:1:0]$ when $Z = 0$. With this new
description, a nonsingular rational point on W
is either $0$ or an affine point $(x, y)$ where
the partial derivatives $W_X(X, Y)$ and $W_Y(X, Y)$ do not vanish simultaneously. For a field
extension K
of F
, a K
-rational point is simply a rational point on W
base changed to K
.
The set of nonsingular rational points forms an abelian group under a secant-and-tangent process.
The identity rational point is
0
.Given a nonsingular rational point
P
, its negation-P
is defined to be the unique third point of intersection betweenW
and the line through0
andP
. Explicitly, ifP
is $(x, y)$, then-P
is $(x, -y - a_1x - a_3)$.Given two points
P
andQ
, their additionP + Q
is defined to be the negation of the unique third point of intersection betweenW
and the lineL
throughP
andQ
. Explicitly, letP
be $(x_1, y_1)$ and letQ
be $(x_2, y_2)$.- If $x_1 = x_2$ and $y_1 = -y_2 - a_1x_2 - a_3$, then
L
is vertical andP + Q
is0
. - If $x_1 = x_2$ and $y_1 \ne -y_2 - a_1x_2 - a_3$, then
L
is the tangent ofW
atP = Q
, and has slope $\ell := (3x_1^2 + 2a_2x_1 + a_4 - a_1y_1) / (2y_1 + a_1x_1 + a_3)$. - Otherwise $x_1 \ne x_2$, then
L
is the secant ofW
throughP
andQ
, and has slope $\ell := (y_1 - y_2) / (x_1 - x_2)$.
In the latter two cases, the $X$-coordinate of
P + Q
is then the unique third solution of the equation obtained by substituting the line $Y = \ell(X - x_1) + y_1$ into the Weierstrass equation, and can be written down explicitly as $x := \ell^2 + a_1\ell - a_2 - x_1 - x_2$ by inspecting the $X^2$ terms. The $Y$-coordinate ofP + Q
, after applying the final negation that maps $Y$ to $-Y - a_1X - a_3$, is precisely $y := -(\ell(x - x_1) + y_1) - a_1x - a_3$.- If $x_1 = x_2$ and $y_1 = -y_2 - a_1x_2 - a_3$, then
The group law on this set is then uniquely determined by these constructions.
Main definitions #
WeierstrassCurve.Affine.Equation
: the Weierstrass equation of an affine Weierstrass curve.WeierstrassCurve.Affine.Nonsingular
: the nonsingular condition on an affine Weierstrass curve.WeierstrassCurve.Affine.Point
: a nonsingular rational point on an affine Weierstrass curve.WeierstrassCurve.Affine.Point.neg
: the negation operation on an affine Weierstrass curve.WeierstrassCurve.Affine.Point.add
: the addition operation on an affine Weierstrass curve.
Main statements #
WeierstrassCurve.Affine.equation_neg
: negation preserves the Weierstrass equation.WeierstrassCurve.Affine.equation_add
: addition preserves the Weierstrass equation.WeierstrassCurve.Affine.nonsingular_neg
: negation preserves the nonsingular condition.WeierstrassCurve.Affine.nonsingular_add
: addition preserves the nonsingular condition.WeierstrassCurve.Affine.nonsingular_of_Δ_ne_zero
: an affine Weierstrass curve is nonsingular at every point if its discriminant is non-zero.EllipticCurve.Affine.nonsingular
: an affine elliptic curve is nonsingular at every point.
Notations #
W⟮K⟯
: the group of nonsingular rational points onW
base changed toK
.
References #
J Silverman, The Arithmetic of Elliptic Curves
Tags #
elliptic curve, rational point, affine coordinates
Weierstrass curves #
An abbreviation for a Weierstrass curve in affine coordinates.
Equations
Instances For
The coercion to a Weierstrass curve in affine coordinates.
Equations
- W.toAffine = W
Instances For
Weierstrass equations #
The polynomial $W(X, Y) := Y^2 + a_1XY + a_3Y - (X^3 + a_2X^2 + a_4X + a_6)$ associated to a
Weierstrass curve W
over R
. For ease of polynomial manipulation, this is represented as a term
of type R[X][X]
, where the inner variable represents $X$ and the outer variable represents $Y$.
For clarity, the alternative notations Y
and R[X][Y]
are provided in the Polynomial
scope to represent the outer variable and the bivariate polynomial ring R[X][X]
respectively.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The proposition that an affine point $(x, y)$ lies in W
. In other words, $W(x, y) = 0$.
Equations
- W.Equation x y = (Polynomial.evalEval x y W.polynomial = 0)
Instances For
Nonsingular Weierstrass equations #
The partial derivative $W_X(X, Y)$ of $W(X, Y)$ with respect to $X$.
TODO: define this in terms of Polynomial.derivative
.
Equations
Instances For
The partial derivative $W_Y(X, Y)$ of $W(X, Y)$ with respect to $Y$.
TODO: define this in terms of Polynomial.derivative
.
Equations
Instances For
The proposition that an affine point $(x, y)$ in W
is nonsingular.
In other words, either $W_X(x, y) \ne 0$ or $W_Y(x, y) \ne 0$.
Note that this definition is only mathematically accurate for fields. TODO: generalise this definition to be mathematically accurate for a larger class of rings.
Equations
- W.Nonsingular x y = (W.Equation x y ∧ (Polynomial.evalEval x y W.polynomialX ≠ 0 ∨ Polynomial.evalEval x y W.polynomialY ≠ 0))
Instances For
A Weierstrass curve is nonsingular at every point if its discriminant is non-zero.
Group operation polynomials over a ring #
The polynomial $-Y - a_1X - a_3$ associated to negation.
Equations
Instances For
The $Y$-coordinate of the negation of an affine point in W
.
This depends on W
, and has argument order: $x$, $y$.
Instances For
The polynomial $L(X - x) + y$ associated to the line $Y = L(X - x) + y$, with a slope of $L$ that passes through an affine point $(x, y)$.
This does not depend on W
, and has argument order: $x$, $y$, $L$.
Equations
- WeierstrassCurve.Affine.linePolynomial x y L = Polynomial.C L * (Polynomial.X - Polynomial.C x) + Polynomial.C y
Instances For
The polynomial obtained by substituting the line $Y = L*(X - x) + y$, with a slope of $L$
that passes through an affine point $(x, y)$, into the polynomial $W(X, Y)$ associated to W
.
If such a line intersects W
at another point $(x', y')$, then the roots of this polynomial are
precisely $x$, $x'$, and the $X$-coordinate of the addition of $(x, y)$ and $(x', y')$.
This depends on W
, and has argument order: $x$, $y$, $L$.
Equations
- W.addPolynomial x y L = Polynomial.eval (WeierstrassCurve.Affine.linePolynomial x y L) W.polynomial
Instances For
The $X$-coordinate of the addition of two affine points $(x_1, y_1)$ and $(x_2, y_2)$ in W
,
where the line through them is not vertical and has a slope of $L$.
This depends on W
, and has argument order: $x_1$, $x_2$, $L$.
Instances For
The $Y$-coordinate of the negated addition of two affine points $(x_1, y_1)$ and $(x_2, y_2)$, where the line through them is not vertical and has a slope of $L$.
This depends on W
, and has argument order: $x_1$, $x_2$, $y_1$, $L$.
Instances For
The $Y$-coordinate of the addition of two affine points $(x_1, y_1)$ and $(x_2, y_2)$ in W
,
where the line through them is not vertical and has a slope of $L$.
This depends on W
, and has argument order: $x_1$, $x_2$, $y_1$, $L$.
Equations
- W.addY x₁ x₂ y₁ L = W.negY (W.addX x₁ x₂ L) (W.negAddY x₁ x₂ y₁ L)
Instances For
The negation of an affine point in W
lies in W
.
The negation of a nonsingular affine point in W
is nonsingular.
Group operation polynomials over a field #
The slope of the line through two affine points $(x_1, y_1)$ and $(x_2, y_2)$ in W
.
If $x_1 \ne x_2$, then this line is the secant of W
through $(x_1, y_1)$ and $(x_2, y_2)$,
and has slope $(y_1 - y_2) / (x_1 - x_2)$. Otherwise, if $y_1 \ne -y_1 - a_1x_1 - a_3$,
then this line is the tangent of W
at $(x_1, y_1) = (x_2, y_2)$, and has slope
$(3x_1^2 + 2a_2x_1 + a_4 - a_1y_1) / (2y_1 + a_1x_1 + a_3)$. Otherwise, this line is vertical,
and has undefined slope, in which case this function returns the value 0.
This depends on W
, and has argument order: $x_1$, $x_2$, $y_1$, $y_2$.
Equations
Instances For
The negated addition of two affine points in W
on a sloped line lies in W
.
The addition of two affine points in W
on a sloped line lies in W
.
The negated addition of two nonsingular affine points in W
on a sloped line is nonsingular.
The addition of two nonsingular affine points in W
on a sloped line is nonsingular.
The formula x(P₁ + P₂) = x(P₁ - P₂) - ψ(P₁)ψ(P₂) / (x(P₂) - x(P₁))², where ψ(x,y) = 2y + a₁x + a₃.
The formula y(P₁)(x(P₂) - x(P₃)) + y(P₂)(x(P₃) - x(P₁)) + y(P₃)(x(P₁) - x(P₂)) = 0, assuming that P₁ + P₂ + P₃ = O.
The formula ψ(P₁ + P₂) = (ψ(P₂)(x(P₁) - x(P₃)) - ψ(P₁)(x(P₂) - x(P₃))) / (x(P₂) - x(P₁)), where ψ(x,y) = 2y + a₁x + a₃.
Group operations #
A nonsingular rational point on a Weierstrass curve W
in affine coordinates. This is either
the unique point at infinity WeierstrassCurve.Affine.Point.zero
or the nonsingular affine points
WeierstrassCurve.Affine.Point.some
$(x, y)$ satisfying the Weierstrass equation of W
.
- zero: {R : Type u} → [inst : CommRing R] → {W : WeierstrassCurve.Affine R} → W.Point
- some: {R : Type u} → [inst : CommRing R] → {W : WeierstrassCurve.Affine R} → {x y : R} → W.Nonsingular x y → W.Point
Instances For
For an algebraic extension S
of R
, the type of nonsingular S
-rational points on W
.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Pretty printer defined by notation3
command.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Equations
- WeierstrassCurve.Affine.Point.instInhabited = { default := WeierstrassCurve.Affine.Point.zero }
Equations
- WeierstrassCurve.Affine.Point.instZero = { zero := WeierstrassCurve.Affine.Point.zero }
The negation of a nonsingular rational point on W
.
Given a nonsingular rational point P
on W
, use -P
instead of neg P
.
Equations
- WeierstrassCurve.Affine.Point.zero.neg = 0
- (WeierstrassCurve.Affine.Point.some h).neg = WeierstrassCurve.Affine.Point.some ⋯
Instances For
Equations
- WeierstrassCurve.Affine.Point.instNeg = { neg := WeierstrassCurve.Affine.Point.neg }
Equations
- WeierstrassCurve.Affine.Point.instInvolutiveNeg = InvolutiveNeg.mk ⋯
The addition of two nonsingular rational points on W
.
Given two nonsingular rational points P
and Q
on W
, use P + Q
instead of add P Q
.
Equations
- WeierstrassCurve.Affine.Point.zero.add x = x
- x.add WeierstrassCurve.Affine.Point.zero = x
- (WeierstrassCurve.Affine.Point.some h₁).add (WeierstrassCurve.Affine.Point.some h₂) = if h : x₁ = x₂ ∧ y₁ = W.negY x₂ y₂ then 0 else WeierstrassCurve.Affine.Point.some ⋯
Instances For
Equations
- WeierstrassCurve.Affine.Point.instAddPoint = { add := WeierstrassCurve.Affine.Point.add }
Equations
- WeierstrassCurve.Affine.Point.instAddZeroClassPoint = AddZeroClass.mk ⋯ ⋯
Maps across ring homomorphisms #
Base changes across algebra homomorphisms #
The function from W⟮F⟯
to W⟮K⟯
induced by an algebra homomorphism f : F →ₐ[S] K
,
where W
is defined over a subring of a ring S
, and F
and K
are field extensions of S
.
Equations
- WeierstrassCurve.Affine.Point.mapFun W f WeierstrassCurve.Affine.Point.zero = 0
- WeierstrassCurve.Affine.Point.mapFun W f (WeierstrassCurve.Affine.Point.some h) = WeierstrassCurve.Affine.Point.some ⋯
Instances For
The group homomorphism from W⟮F⟯
to W⟮K⟯
induced by an algebra homomorphism f : F →ₐ[S] K
,
where W
is defined over a subring of a ring S
, and F
and K
are field extensions of S
.
Equations
- WeierstrassCurve.Affine.Point.map W f = { toFun := WeierstrassCurve.Affine.Point.mapFun W f, map_zero' := ⋯, map_add' := ⋯ }
Instances For
The group homomorphism from W⟮F⟯
to W⟮K⟯
induced by the base change from F
to K
,
where W
is defined over a subring of a ring S
, and F
and K
are field extensions of S
.
Equations
Instances For
Alias of WeierstrassCurve.Affine.negAddY
.
The $Y$-coordinate of the negated addition of two affine points $(x_1, y_1)$ and $(x_2, y_2)$, where the line through them is not vertical and has a slope of $L$.
This depends on W
, and has argument order: $x_1$, $x_2$, $y_1$, $L$.
Instances For
Alias of WeierstrassCurve.Affine.nonsingular_negAdd_of_eval_derivative_ne_zero
.
Alias of WeierstrassCurve.Affine.slope_of_Y_eq
.
Alias of WeierstrassCurve.Affine.slope_of_Y_ne
.
Alias of WeierstrassCurve.Affine.slope_of_X_ne
.
Alias of WeierstrassCurve.Affine.Y_eq_of_X_eq
.
Alias of WeierstrassCurve.Affine.Y_eq_of_Y_ne
.
Alias of WeierstrassCurve.Affine.equation_negAdd
.
The negated addition of two affine points in W
on a sloped line lies in W
.
Alias of WeierstrassCurve.Affine.nonsingular_negAdd
.
The negated addition of two nonsingular affine points in W
on a sloped line is nonsingular.
Alias of WeierstrassCurve.Affine.map_negAddY
.
Elliptic curves #
The coercion from an elliptic curve to a Weierstrass curve in affine coordinates.
Equations
- E.toAffine = E.toAffine