# 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)$.

ProjEllipticCurveType
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 x, y, z over Rational Field, QQMPolyRingElem[x, y, z])

julia> T, _ = grade(S)
(Multivariate Polynomial Ring in x, y, z over Rational Field graded by
x -> [1]
y -> [1]
z -> [1], 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_EllCurveType
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 x, y, z over Rational Field, QQMPolyRingElem[x, y, z])

julia> T, _ = grade(S)
(Multivariate Polynomial Ring in x, y, z over Rational Field graded by
x -> [1]
y -> [1]
z -> [1], 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_spaceMethod
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_spaceMethod
proj_space(P::Point_EllCurve{S}) where S <: FieldElem

Return the projective space to which the point P belongs.

source
curveMethod
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 x, y, z over Rational Field, QQMPolyRingElem[x, y, z])

julia> T, _ = grade(S)
(Multivariate Polynomial Ring in x, y, z over Rational Field graded by
x -> [1]
y -> [1]
z -> [1], 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_formMethod
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 x, y, z over Rational Field, QQMPolyRingElem[x, y, z])

julia> T, _ = grade(S)
(Multivariate Polynomial Ring in x, y, z over Rational Field graded by
x -> [1]
y -> [1]
z -> [1], 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
toweierstrassMethod
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 x, y, z over Rational Field, QQMPolyRingElem[x, y, z])

julia> T, _ = grade(S)
(Multivariate Polynomial Ring in x, y, z over Rational Field graded by
x -> [1]
y -> [1]
z -> [1], 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...

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

Return the discriminant of the projective elliptic curve E.

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

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

source
is_torsion_pointMethod
is_torsion_point(P::Point_EllCurve{QQFieldElem})

Return whether the point P is a torsion point.

source
torsion_points_lutz_nagellMethod
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_polyMethod
torsion_points_division_poly(E::ProjEllipticCurve{QQFieldElem})

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

source
orderMethod
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:

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

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

source
list_randMethod
list_rand(E::ProjEllipticCurve, N::Int)

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

source
orderMethod
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_EllCurveZnZMethod
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_EllCurveZnZMethod
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_PointMethod
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 x, y, z over Integers modulo 4453, AbstractAlgebra.Generic.MPoly{ZZModRingElem}[x, y, z])

julia> T, _ = grade(S)
(Multivariate Polynomial Ring in x, y, z over Integers modulo 4453 graded by
x -> [1]
y -> [1]
z -> [1], 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:

ECMMethod
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.

ECPPMethod
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_algorithmMethod
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_testFunction
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_rhoFunction
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_1Function
Pollard_p_1(N::ZZRingElem, B::ZZRingElem = ZZ(10)^5)

The algorithm computes a factor of N and returns it.

source