Projective coordinates for Weierstrass curves #
This file defines the type of points on a Weierstrass curve as a tuple, consisting of an equivalence
class of triples up to scaling by a unit, 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.lean
.
Mathematical background #
A point on the unweighted projective plane over a commutative ring R
is an equivalence class
[x : y : z]
of triples (x, y, z) ≠ (0, 0, 0)
of elements in R
such that
(x, y, z) ∼ (x', y', z')
if there is some unit u
in Rˣ
with (x, y, z) = (ux', uy', uz')
.
Let W
be a Weierstrass curve over a field F
with coefficients aᵢ
. A projective point is a
point on the unweighted projective plane over F
satisfying the homogeneous Weierstrass equation
W(X, Y, Z) = 0
in projective coordinates, where
W(X, Y, Z) := Y²Z + a₁XYZ + a₃YZ² - (X³ + a₂X²Z + a₄XZ² + a₆Z³)
. It is nonsingular if its
partial derivatives W_X(x, y, z)
, W_Y(x, y, z)
, and W_Z(x, y, z)
do not vanish simultaneously.
The nonsingular projective points on W
can be given negation and addition operations defined by an
analogue of the secant-and-tangent process in Mathlib/AlgebraicGeometry/EllipticCurve/Affine.lean
,
but the polynomials involved are homogeneous, so any instances of division become multiplication in
the Z
-coordinate. Most computational proofs are immediate from their analogous proofs for affine
coordinates. They can be endowed with an group law, which is uniquely determined by these formulae
and follows from an equivalence with the nonsingular points W⟮F⟯
in affine coordinates.
Main definitions #
WeierstrassCurve.Projective.PointClass
: the equivalence class of a point representative.WeierstrassCurve.Projective.Nonsingular
: the nonsingular condition on a point representative.WeierstrassCurve.Projective.NonsingularLift
: the nonsingular condition on a point class.WeierstrassCurve.Projective.negY
: theY
-coordinate of-P
.WeierstrassCurve.Projective.dblZ
: theZ
-coordinate of2 • P
.WeierstrassCurve.Projective.dblX
: theX
-coordinate of2 • P
.WeierstrassCurve.Projective.negDblY
: theY
-coordinate of-(2 • P)
.WeierstrassCurve.Projective.dblY
: theY
-coordinate of2 • P
.WeierstrassCurve.Projective.addZ
: theZ
-coordinate ofP + Q
.WeierstrassCurve.Projective.addX
: theX
-coordinate ofP + Q
.WeierstrassCurve.Projective.negAddY
: theY
-coordinate of-(P + Q)
.WeierstrassCurve.Projective.addY
: theY
-coordinate ofP + Q
.WeierstrassCurve.Projective.neg
: the negation of a point representative.WeierstrassCurve.Projective.negMap
: the negation of a point class.WeierstrassCurve.Projective.add
: the addition of two point representatives.WeierstrassCurve.Projective.addMap
: the addition of two point classes.WeierstrassCurve.Projective.Point
: a nonsingular projective point.WeierstrassCurve.Projective.Point.neg
: the negation of a nonsingular projective point.WeierstrassCurve.Projective.Point.add
: the addition of two nonsingular projective points.WeierstrassCurve.Projective.Point.toAffineAddEquiv
: the equivalence between the type of nonsingular projective points with the type of nonsingular pointsW⟮F⟯
in affine coordinates.
Main statements #
WeierstrassCurve.Projective.polynomial_relation
: Euler's homogeneous function theorem.WeierstrassCurve.Projective.nonsingular_neg
: negation preserves the nonsingular condition.WeierstrassCurve.Projective.nonsingular_add
: addition preserves the nonsingular condition.
Implementation notes #
All definitions and lemmas for Weierstrass curves in projective coordinates live in the namespace
WeierstrassCurve.Projective
to distinguish them from those in other coordinates. This is simply an
abbreviation for WeierstrassCurve
that can be converted using WeierstrassCurve.toProjective
.
This can be converted into WeierstrassCurve.Affine
using WeierstrassCurve.Projective.toAffine
.
A nonsingular projective point representative can be converted to a nonsingular point in affine
coordinates using WeiestrassCurve.Projective.Point.toAffine
, which lifts to a map on nonsingular
projective points using WeiestrassCurve.Projective.Point.toAffineLift
. Conversely, a nonsingular
point in affine coordinates can be converted to a nonsingular projective point using
WeierstrassCurve.Projective.Point.fromAffine
or WeierstrassCurve.Affine.Point.toProjective
.
A point representative is implemented as a term P
of type Fin 3 → R
, which allows for the vector
notation ![x, y, z]
. However, P
is not definitionally equivalent to the expanded vector
![P x, P y, P z]
, so the lemmas fin3_def
and fin3_def_ext
can be used to convert between the
two forms. The equivalence of two point representatives P
and Q
is implemented as an equivalence
of orbits of the action of Rˣ
, or equivalently that there is some unit u
of R
such that
P = u • Q
. However, u • Q
is not definitionally equal to ![u * Q x, u * Q y, u * Q z]
, so the
lemmas smul_fin3
and smul_fin3_ext
can be used to convert between the two forms.
This file makes extensive use of erw
to get around this problem.
While erw
is often an indication of a problem, in this case it is self-contained and should not
cause any issues. It would alternatively be possible to add some automation to assist here.
Note that W(X, Y, Z)
and its partial derivatives are independent of the point representative, and
the nonsingularity condition already implies (x, y, z) ≠ (0, 0, 0)
, so a nonsingular projective
point on W
can be given by [x : y : z]
and the nonsingular condition on any representative.
The definitions of WeierstrassCurve.Projective.dblX
, WeierstrassCurve.Projective.negDblY
,
WeierstrassCurve.Projective.addZ
, WeierstrassCurve.Projective.addX
, and
WeierstrassCurve.Projective.negAddY
are given explicitly by large polynomials that are homogeneous
of degree 4
. Clearing the denominators of their corresponding affine rational functions in
Mathlib/AlgebraicGeometry/EllipticCurve/Affine.lean
would give polynomials that are
homogeneous of degrees 5
, 6
, 6
, 8
, and 8
respectively, so their actual definitions are off
by powers of certain polynomial factors that are homogeneous of degree 1
or 2
. These factors
divide their corresponding affine polynomials only modulo the homogeneous Weierstrass equation, so
their large quotient polynomials are calculated explicitly in a computer algebra system. All of this
is done to ensure that the definitions of both WeierstrassCurve.Projective.dblXYZ
and
WeierstrassCurve.Projective.addXYZ
are homogeneous of degree 4
.
Whenever possible, all changes to documentation and naming of definitions and theorems should be
mirrored in Mathlib/AlgebraicGeometry/EllipticCurve/Jacobian.lean
.
References #
[J Silverman, The Arithmetic of Elliptic Curves][silverman2009]
Tags #
elliptic curve, rational point, projective coordinates
Weierstrass curves #
An abbreviation for a Weierstrass curve in projective coordinates.
Equations
Instances For
The conversion from a Weierstrass curve to projective coordinates.
Equations
- W.toProjective = W
Instances For
The conversion from a Weierstrass curve in projective coordinates to affine coordinates.
Equations
Instances For
Projective coordinates #
The equivalence setoid for a projective point representative on a Weierstrass curve.
Equations
Instances For
The equivalence class of a projective point representative on a Weierstrass curve.
Equations
Instances For
Weierstrass equations #
The polynomial W(X, Y, Z) := Y²Z + a₁XYZ + a₃YZ² - (X³ + a₂X²Z + a₄XZ² + a₆Z³)
associated to a
Weierstrass curve W
over a ring R
in projective coordinates.
This is represented as a term of type MvPolynomial (Fin 3) R
, where X 0
, X 1
, and X 2
represent X
, Y
, and Z
respectively.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The proposition that a projective point representative (x, y, z)
lies in a Weierstrass curve
W
.
In other words, it satisfies the homogeneous Weierstrass equation W(X, Y, Z) = 0
.
Equations
- W'.Equation P = ((MvPolynomial.eval P) W'.polynomial = 0)
Instances For
Nonsingular Weierstrass equations #
The partial derivative W_X(X, Y, Z)
with respect to X
of the polynomial W(X, Y, Z)
associated to a Weierstrass curve W
in projective coordinates.
Equations
- W'.polynomialX = (MvPolynomial.pderiv 0) W'.polynomial
Instances For
The partial derivative W_Y(X, Y, Z)
with respect to Y
of the polynomial W(X, Y, Z)
associated to a Weierstrass curve W
in projective coordinates.
Equations
- W'.polynomialY = (MvPolynomial.pderiv 1) W'.polynomial
Instances For
The partial derivative W_Z(X, Y, Z)
with respect to Z
of the polynomial W(X, Y, Z)
associated to a Weierstrass curve W
in projective coordinates.
Equations
- W'.polynomialZ = (MvPolynomial.pderiv 2) W'.polynomial
Instances For
Euler's homogeneous function theorem in projective coordinates.
The proposition that a projective point representative (x, y, z)
on a Weierstrass curve W
is
nonsingular.
In other words, either W_X(x, y, z) ≠ 0
, W_Y(x, y, z) ≠ 0
, or W_Z(x, y, z) ≠ 0
.
Note that this definition is only mathematically accurate for fields.
Equations
- W'.Nonsingular P = (W'.Equation P ∧ ((MvPolynomial.eval P) W'.polynomialX ≠ 0 ∨ (MvPolynomial.eval P) W'.polynomialY ≠ 0 ∨ (MvPolynomial.eval P) W'.polynomialZ ≠ 0))
Instances For
The proposition that a projective point class on a Weierstrass curve W
is nonsingular.
If P
is a projective point representative on W
, then W.NonsingularLift ⟦P⟧
is definitionally
equivalent to W.Nonsingular P
.
Note that this definition is only mathematically accurate for fields.
Equations
- W'.NonsingularLift P = Quotient.lift W'.Nonsingular ⋯ P
Instances For
Alias of WeierstrassCurve.Projective.nonsingular_of_Z_ne_zero
.
Alias of WeierstrassCurve.Projective.nonsingular_of_Z_ne_zero
.
Alias of WeierstrassCurve.Projective.nonsingular_of_Z_ne_zero
.
Negation formulae #
Doubling formulae #
The unit associated to a representative of 2 • P
for a projective point representative P
on
a Weierstrass curve W
that is 2
-torsion.
More specifically, the unit u
such that W.add P P = u • ![0, 1, 0]
where P = W.neg P
.
Equations
- W.dblU P = (MvPolynomial.eval P) W.polynomialX ^ 3 / P 2 ^ 2
Instances For
The X
-coordinate of a representative of 2 • P
for a projective point representative P
on a
Weierstrass curve.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The Y
-coordinate of a representative of -(2 • P)
for a projective point representative P
on a Weierstrass curve.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The Y
-coordinate of a representative of 2 • P
for a projective point representative P
on a
Weierstrass curve.
Instances For
The coordinates of a representative of 2 • P
for a projective point representative P
on a
Weierstrass curve.
Instances For
Addition formulae #
The Z
-coordinate of a representative of P + Q
for two distinct projective point
representatives P
and Q
on a Weierstrass curve.
If the representatives of P
and Q
are equal, then this returns the value 0
.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The X
-coordinate of a representative of P + Q
for two distinct projective point
representatives P
and Q
on a Weierstrass curve.
If the representatives of P
and Q
are equal, then this returns the value 0
.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The Y
-coordinate of a representative of -(P + Q)
for two distinct projective point
representatives P
and Q
on a Weierstrass curve.
If the representatives of P
and Q
are equal, then this returns the value 0
.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The Y
-coordinate of a representative of P + Q
for two distinct projective point
representatives P
and Q
on a Weierstrass curve.
If the representatives of P
and Q
are equal, then this returns the value 0
.
Instances For
The coordinates of a representative of P + Q
for two distinct projective point representatives
P
and Q
on a Weierstrass curve.
If the representatives of P
and Q
are equal, then this returns the value ![0, 0, 0]
.
Instances For
Negation on point representatives #
The negation of a projective point class on a Weierstrass curve W
.
If P
is a projective point representative on W
, then W.negMap ⟦P⟧
is definitionally equivalent
to W.neg P
.
Equations
- W'.negMap P = Quotient.map W'.neg ⋯ P
Instances For
Addition on point representatives #
The addition of two projective point classes on a Weierstrass curve W
.
If P
and Q
are two projective point representatives on W
, then W.addMap ⟦P⟧ ⟦Q⟧
is
definitionally equivalent to W.add P Q
.
Equations
- W'.addMap P Q = Quotient.map₂ W'.add ⋯ P Q
Instances For
Nonsingular rational points #
A nonsingular projective point on a Weierstrass curve W
.
- point : PointClass R
The projective point class underlying a nonsingular projective point on
W
. - nonsingular : W'.NonsingularLift self.point
The nonsingular condition underlying a nonsingular projective point on
W
.
Instances For
Equations
The natural map from a nonsingular point on a Weierstrass curve in affine coordinates to its corresponding nonsingular projective point.
Equations
Instances For
The negation of a nonsingular projective point on a Weierstrass curve W
.
Given a nonsingular projective point P
on W
, use -P
instead of neg P
.
Equations
Instances For
Equations
The addition of two nonsingular projective points on a Weierstrass curve W
.
Given two nonsingular projective points P
and Q
on W
, use P + Q
instead of add P Q
.
Equations
Instances For
Equations
Equivalence with affine coordinates #
The natural map from a nonsingular projective point representative on a Weierstrass curve to its corresponding nonsingular point in affine coordinates.
Equations
- WeierstrassCurve.Projective.Point.toAffine W P = if hP : W.Nonsingular P ∧ P 2 ≠ 0 then WeierstrassCurve.Affine.Point.some ⋯ else 0
Instances For
The natural map from a nonsingular projective point on a Weierstrass curve W
to its
corresponding nonsingular point in affine coordinates.
If hP
is the nonsingular condition underlying a nonsingular projective point P
on W
, then
toAffineLift ⟨hP⟩
is definitionally equivalent to toAffine W P
.
Equations
- P.toAffineLift = Quotient.lift (fun (x : Fin 3 → F) => WeierstrassCurve.Projective.Point.toAffine W x) ⋯ P.point
Instances For
The addition-preserving equivalence between the type of nonsingular projective points on a
Weierstrass curve W
and the type of nonsingular points W⟮F⟯
in affine coordinates.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Maps across ring homomorphisms #
Base changes across algebra homomorphisms #
An abbreviation for WeierstrassCurve.Projective.Point.fromAffine
for dot notation.