Edit on GitHub

Elliptic Curves

An elliptic plane curve is a projective plane curve of degree 3 together with a point of the curve, called the base point. An operation of addition of points can be defined on elliptic curves.

Constructor

An elliptic curve is a subtype of the abstract type ProjectivePlaneCurve. To define an elliptic curve over a field, one can either give as input an equation and the point at infinity, or just an equation in Weierstrass form. In the latter case, the point at infinity is $(0 : 1 : 0)$.

Considering elliptic curves over a ring is helpful in some primality proving test. We introduce here a structure of elliptic curve over a ring. In that case, we always assume the equation to be in Weierstrass form, with infinity point $(0 : 1 : 0)$.

ProjEllipticCurve — Type
ProjEllipticCurve{S}(eq::Oscar.MPolyDecRingElem{S}) where {S <: FieldElem}
ProjEllipticCurve(eq::Oscar.MPolyDecRingElem{S}, P::Oscar.Geometry.ProjSpcElem{S}) where {S <: FieldElem}
ProjEllipticCurve(eq::Oscar.MPolyDecRingElem{S}) where {S <: Nemo.ZZModRingElem}

Return the Projective Elliptic Curve defined by the equation eq, with P as infinity point. If no point is specified it is expected that eq is in Weierstrass form, and the infinity point is (0:1:0).

Examples

julia> S, (x, y, z) = polynomial_ring(QQ, ["x", "y", "z"])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])

julia> T, _ = grade(S)
(Graded multivariate polynomial ring in 3 variables over QQ, MPolyDecRingElem{QQFieldElem, QQMPolyRingElem}[x, y, z])

julia> F = T(-x^3 - 3*x^2*y - 3*x*y^2 - x*z^2 - y^3 + y^2*z - y*z^2 - 4*z^3)
-x^3 - 3*x^2*y - 3*x*y^2 - x*z^2 - y^3 + y^2*z - y*z^2 - 4*z^3

julia> PP = proj_space(QQ, 2)
(Projective space of dim 2 over Rational field
, MPolyDecRingElem{QQFieldElem, QQMPolyRingElem}[x[0], x[1], x[2]])

julia> P = Oscar.Geometry.ProjSpcElem(PP[1], [QQ(-1), QQ(1), QQ(0)])
(-1 : 1 : 0)

julia> E1 = Oscar.ProjEllipticCurve(F, P)
Projective elliptic curve defined by -x^3 - 3*x^2*y - 3*x*y^2 - x*z^2 - y^3 + y^2*z - y*z^2 - 4*z^3

julia> E2 = Oscar.ProjEllipticCurve(T(y^2*z - x^3 - x*z^2))
Projective elliptic curve defined by -x^3 - x*z^2 + y^2*z
source

Points on Elliptic Curves

We define a specific structure for the points on an elliptic curve, on which the operation of addition and multiplication by an integer are defined.

Point_EllCurve — Type
Point_EllCurve(E::ProjEllipticCurve{S}, P::Oscar.Geometry.ProjSpcElem{S}) where {S <: FieldElem}
Point_EllCurve(E::ProjEllipticCurve{S}, P::Oscar.Geometry.ProjSpcElem{S}) where {S <: Nemo.ZZModRingElem}

Create the point P on the elliptic curve E.

Examples

julia> S, (x, y, z) = polynomial_ring(QQ, ["x", "y", "z"])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])

julia> T, _ = grade(S)
(Graded multivariate polynomial ring in 3 variables over QQ, MPolyDecRingElem{QQFieldElem, QQMPolyRingElem}[x, y, z])

julia> E = Oscar.ProjEllipticCurve(T(y^2*z - x^3 + 2*x*z^2))
Projective elliptic curve defined by -x^3 + 2*x*z^2 + y^2*z

julia> PP = Oscar.proj_space(E)
Projective space of dim 2 over Rational field

julia> P = Oscar.Geometry.ProjSpcElem(PP, [QQ(2), QQ(2), QQ(1)])
(2 : 2 : 1)

julia> Q = Oscar.Point_EllCurve(E, P)
(2 : 2 : 1)
source

Methods

Most of the functions described for projective plane curves are also available for elliptic curves over a field. We describe here the functions which are specific to elliptic curves.

Basic functions

proj_space — Method
proj_space(E::ProjEllipticCurve{S}) where S <: FieldElem

Return the projective space to which the base point of the elliptic curve E belongs.

source
proj_space — Method
proj_space(P::Point_EllCurve{S}) where S <: FieldElem

Return the projective space to which the point P belongs.

source
curve — Method
curve(P::Point_EllCurve{S}) where S <: FieldElem

Return the curve on which the point P is considered.

source

Addition and multiplication by an integer of a point on an elliptic curve can be performed using the usual symbols + and *.

Example

julia> S, (x, y, z) = polynomial_ring(QQ, ["x", "y", "z"])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])

julia> T, _ = grade(S)
(Graded multivariate polynomial ring in 3 variables over QQ, MPolyDecRingElem{QQFieldElem, QQMPolyRingElem}[x, y, z])

julia> E = Oscar.ProjEllipticCurve(T(y^2*z - x^3 + 2*x*z^2))
Projective elliptic curve defined by -x^3 + 2*x*z^2 + y^2*z

julia> PP = Oscar.proj_space(E)
Projective space of dim 2 over Rational field

julia> P = Oscar.Geometry.ProjSpcElem(PP, [QQ(2), QQ(2), QQ(1)])
(2 : 2 : 1)

julia> Q = Oscar.Point_EllCurve(E, P)
(2 : 2 : 1)

julia> Q+Q
(9//4 : -21//8 : 1)

julia> 3*Q
(338 : 6214 : 1)

Weierstrass form

weierstrass_form — Method
weierstrass_form(E::ProjEllipticCurve{S}) where {S <: FieldElem}

Return the equation of a projective elliptic curve defined by an equation in Weierstrass form and which is linearly equivalent to E.

Examples

julia> S, (x, y, z) = polynomial_ring(QQ, ["x", "y", "z"])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])

julia> T, _ = grade(S)
(Graded multivariate polynomial ring in 3 variables over QQ, MPolyDecRingElem{QQFieldElem, QQMPolyRingElem}[x, y, z])

julia> F = T(-x^3 - 3*x^2*y - 3*x*y^2 - x*z^2 - y^3 + y^2*z - y*z^2 - 4*z^3)
-x^3 - 3*x^2*y - 3*x*y^2 - x*z^2 - y^3 + y^2*z - y*z^2 - 4*z^3

julia> PP = proj_space(QQ, 2)
(Projective space of dim 2 over Rational field
, MPolyDecRingElem{QQFieldElem, QQMPolyRingElem}[x[0], x[1], x[2]])

julia> P = Oscar.Geometry.ProjSpcElem(PP[1], [QQ(-1), QQ(1), QQ(0)])
(-1 : 1 : 0)

julia> E = Oscar.ProjEllipticCurve(F, P)
Projective elliptic curve defined by -x^3 - 3*x^2*y - 3*x*y^2 - x*z^2 - y^3 + y^2*z - y*z^2 - 4*z^3

julia> Oscar.weierstrass_form(E)
-x^3 - x*z^2 + y^2*z - 4*z^3
source
toweierstrass — Method
toweierstrass(C::ProjPlaneCurve{S}, P::Oscar.Geometry.ProjSpcElem{S}) where S <: FieldElem

Given a smooth plane cubic projective curve C and a point P on the curve, return an elliptic curve birationally equivalent to C given by an equation in long Weierstrass form.

Examples

julia> S, (x, y, z) = polynomial_ring(QQ, ["x", "y", "z"])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])

julia> T, _ = grade(S)
(Graded multivariate polynomial ring in 3 variables over QQ, MPolyDecRingElem{QQFieldElem, QQMPolyRingElem}[x, y, z])

julia> PP = proj_space(QQ, 2)
(Projective space of dim 2 over Rational field
, MPolyDecRingElem{QQFieldElem, QQMPolyRingElem}[x[0], x[1], x[2]])

julia> Q = Oscar.Geometry.ProjSpcElem(PP[1], [QQ(-1), QQ(1), QQ(0)])
(-1 : 1 : 0)

julia> D = Oscar.ProjPlaneCurve(T(-x^3 - 3*x^2*y + 2*x^2*z - 3*x*y^2 + 3*x*y*z - 4*x*z^2 - y^3 - y*z^2 + 6*z^3))
Projective plane curve defined by -x^3 - 3*x^2*y + 2*x^2*z - 3*x*y^2 + 3*x*y*z - 4*x*z^2 - y^3 - y*z^2 + 6*z^3

julia> Oscar.toweierstrass(D, Q)
-x^3 - 2*x^2*z + x*y*z - 4*x*z^2 + y^2*z + 3*y*z^2 - 6*z^3
source

Invariant of Elliptic Curves, torsion points...

discriminant — Method
discriminant(E::ProjEllipticCurve{S}) where S <: FieldElem

Return the discriminant of the projective elliptic curve E.

source
j_invariant — Method
j_invariant(E::ProjEllipticCurve{S}) where S <: FieldElem

Return the j-invariant of the projective elliptic curve E.

source
is_torsion_point — Method
is_torsion_point(P::Point_EllCurve{QQFieldElem})

Return whether the point P is a torsion point.

source
torsion_points_lutz_nagell — Method
torsion_points_lutz_nagell(E::ProjEllipticCurve{QQFieldElem})

Return the rational torsion points of the elliptic curve E using the Lutz-Nagell theorem.

source
torsion_points_division_poly — Method
torsion_points_division_poly(E::ProjEllipticCurve{QQFieldElem})

Return the rational torsion points of a rational elliptic curve E using division polynomials.

source
order — Method
order(P::Point_EllCurve{QQFieldElem})

Return the order of the point P or 0 if the order is infinite.

source

The following functions are implemented for elliptic curves over finite fields:

rand — Method
rand(E::ProjEllipticCurve{S}) where S <: FieldElem

Return a random point on the elliptic curve E defined over a finite field.

source
list_rand — Method
list_rand(E::ProjEllipticCurve, N::Int)

Return a list of N random points on the elliptic curve E defined over a finite field.

source
order — Method
order(E::ProjEllipticCurve{S}) where S <: FieldElem

Given an elliptic curve E over a finite field $\mathbf F$, computes $\#E(\mathbf F)$.

source

The addition of points is not well defined for projective elliptic curves over a ring, that's why this case has to be considered separately. The following methods can for example be used for teaching purposes to show the steps of the Elliptic Curve Method.

sum_Point_EllCurveZnZ — Method
sum_Point_EllCurveZnZ(P::Point_EllCurve{S}, Q::Point_EllCurve{S}) where S <: Nemo.ZZModRingElem

Return, if possible, the sum of the points P and Q, and an error otherwise.

source
IntMult_Point_EllCurveZnZ — Method
IntMult_Point_EllCurveZnZ(m::ZZRingElem, P::Point_EllCurve{S}) where S <: Nemo.ZZModRingElem

Return, if possible, the point mP, and an error otherwise.

source
rand_pair_EllCurve_Point — Method
rand_pair_EllCurve_Point(R::Oscar.MPolyDecRing{S}, PP::Oscar.Geometry.ProjSpc{S}) where S <: Nemo.ZZModRingElem

Return a pair composed of an elliptic plane curve E with equation in R, and a point P on E.

source

Primality proving

Elliptic Curve Method

Projective elliptic curves over a ring are for example used in the Elliptic Curve Method. We give here an example (see Example 7.1 of Lawrence C. Washington (2008)) on how to use the previous functions to apply it. 

julia> n = 4453
4453

julia> A = residue_ring(ZZ, ZZ(n))
Integers modulo 4453

julia> S, (x,y,z) = polynomial_ring(A, ["x", "y", "z"])
(Multivariate polynomial ring in 3 variables over ZZ/(4453), AbstractAlgebra.Generic.MPoly{ZZModRingElem}[x, y, z])

julia> T, _ = grade(S)
(Graded multivariate polynomial ring in 3 variables over ZZ/(4453), MPolyDecRingElem{ZZModRingElem, AbstractAlgebra.Generic.MPoly{ZZModRingElem}}[x, y, z])

julia> E = Oscar.ProjEllipticCurve(T(y^2*z - x^3 - 10*x*z^2 + 2*z^3))
Projective elliptic curve defined by 4452*x^3 + 4443*x*z^2 + y^2*z + 2*z^3

julia> PP = proj_space(A, 2)
(Projective space of dim 2 over Integers modulo 4453
, MPolyDecRingElem{ZZModRingElem, AbstractAlgebra.Generic.MPoly{ZZModRingElem}}[x[0], x[1], x[2]])

julia> Q = Oscar.Geometry.ProjSpcElem(PP[1], [A(1), A(3), A(1)])
(1 : 3 : 1)

julia> P = Oscar.Point_EllCurve(E, Q)
(1 : 3 : 1)

julia> P2 = Oscar.IntMult_Point_EllCurveZnZ(ZZ(2), P)
(4332 : 3230 : 1)

julia> Oscar.sum_Point_EllCurveZnZ(P, P2)
ERROR: 61 is not invertible in the base ring, cannot perform the sum

The last sum is not defined, and the error which is shown when we ask for the sum gives us a factor of 4453. The Elliptic Curve Method is implemented and can be called using:

ECM — Method
ECM(n::ZZRingElem; nbcurve::Int = 25000, multfact::ZZRingElem = factorial(ZZ(10^4)))

Return a factor of n, obtained with the Elliptic Curve Method.

source

Elliptic Curve Primality Proving

Elliptic curves over finite fields or rings are used for the method called "Elliptic Curve Primality Proving". We implemented here the version relying on Atkin-Morain's test. The present implementation is not intended to be competitive.

ECPP — Method
ECPP(n::ZZRingElem)

The algorithm returns true if the number is prime, false if not, and an error if it can't decide.

source

Other algorithms

TODO: The following algorithms are not directly related to Plane Curves, they might be moved to another section of the documentation.

cornacchia_algorithm — Method
cornacchia_algorithm(d::ZZRingElem, m::ZZRingElem)

Return true and a solution of x^2 + d*y^2 = m if it exists, and false and (0, 0) otherwise.

source
Miller_Rabin_test — Function
Miller_Rabin_test(N::ZZRingElem, k::Int64 = 20)

Given an odd number N, return false if the number is composite, and true if it is probably prime.

source
Pollard_rho — Function
Pollard_rho(N::ZZRingElem, bound::Int = 50000)

The algorithm computes a factor of N using the Pollard rho algorithm and returns it.

source
Pollard_p_1 — Function
Pollard_p_1(N::ZZRingElem, B::ZZRingElem = ZZ(10)^5)

The algorithm computes a factor of N and returns it.

source