Elliptic curves over finite fields

Random points

  rand(E::EllipticCurve{<: FinFieldElem})

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

julia> E = elliptic_curve(GF(3), [1, 2]);

julia> rand(E)
(2 : 0 : 1)

Curves with a point of given order

elliptic_curve_with_point_of_order Method

elliptic_curve_with_point_of_order(K::FinField, N::IntegerUnion;
                                   rng::AbstractRNG = Random.default_rng())
                                   -> EllipticCurve, EllipticCurvePoint

Return a random elliptic curve over the finite field $K$ and a point on it of order exactly $N$, by the construction of [5].

The order $N\ge 2$ must be prime to the characteristic of $K$. For $N\ge 4$ the curve is the Tate normal form $y^2+(1-c)xy-by=x^3-b{x}^2$ and the point is $(0,0)$; for $N\ge 6$, $(b,c)$ comes from a point of the raw form $F_N(r,s)=0$ of $X_1(N)$, which Algorithm 1 of [5] computes the first time it is needed in a session. Its cost grows quickly with $N$, from instant for small $N$ to minutes around $N=100$. Equations of lower degree for $X_1(N)$, which would make large $N$ faster, are available at https://math.mit.edu/~drew/X1_altcurves.html.

An error is raised when no elliptic curve over $K$ has a point of order $N$, as for $N=13$ over ${\mathbb{F}}_2$; at once when $N>q+1+2\sqrt{q}$, $q$ the order of $K$, the Hasse bound on the number of points.

Examples

julia> E, P = elliptic_curve_with_point_of_order(GF(101), 7);

julia> order(P)
7

source

Cardinality and orders

order Method

order(K::AbsSimpleNumField, A::ZZMatrix, check::Bool = true) -> AbsSimpleNumFieldOrder

Returns the order which has basis matrix $A$ with respect to the power basis of $K$. If check is set, it is checked whether $A$ defines an order.

source

order(A::AbstractAssociativeAlgebra{<: NumFieldElem}, M::PMat{<: NumFieldElem, T})
  -> AlgAssRelOrd

Returns the order of $A$ with basis pseudo-matrix $M$.

source

order Method

order(K::AbsSimpleNumField, A::ZZMatrix, check::Bool = true) -> AbsSimpleNumFieldOrder

Returns the order which has basis matrix $A$ with respect to the power basis of $K$. If check is set, it is checked whether $A$ defines an order.

source

order(P::EllipticCurvePoint, [fac::Fac{ZZRingElem}]) -> ZZRingElem

Given a point $P$ on an elliptic curve $E$ over a finite field, return the order of this point.

Optionally, one can supply the factorization of a multiple of the point order, for example the order of $E$.

Examples

julia> E = elliptic_curve(GF(101), [1, 2]);

julia> P = E([17, 65]);

julia> order(P)
100

julia> fac = factor(order(E))
2^2 * 5^2

julia> order(P, fac)
100

source

order(A::AbstractAssociativeAlgebra{<: NumFieldElem}, M::PMat{<: NumFieldElem, T})
  -> AlgAssRelOrd

Returns the order of $A$ with basis pseudo-matrix $M$.

source

Frobenius

trace_of_frobenius Method

trace_of_frobenius(E::EllipticCurve{FinFieldElem}) -> Int

Return the trace of the Frobenius endomorphism on the elliptic curve $E$ over ${\mathbf{F}}_q$. This is equal to $q+1-n$ where n is the number of points on $E$ over ${\mathbf{F}}_q$.

Examples

julia> E = elliptic_curve(GF(101), [1, 2]);

julia> trace_of_frobenius(E) == 101 + 1 - order(E)
true

source

trace_of_frobenius Method

trace_of_frobenius(E::EllipticCurve{<: FinFieldElem}, r::Int) -> ZZRingElem

Return the trace of the $r$-th power of the Frobenius endomorphism on the elliptic curve $E$.

julia> E = elliptic_curve(GF(101, 2), [1, 2]);

julia> trace_of_frobenius(E, 2)
18802

source

Group structure of rational points

gens Method

gens(E::EllipticCurve{<:FinFieldElem}) -> Vector{EllipticCurvePoint}

Return a list of generators of the group of rational points on $E$.

Examples

julia> E = elliptic_curve(GF(101, 2), [1, 2]);

julia> gens(E)
2-element Vector{EllipticCurvePoint{FqFieldElem}}:
 (13*o + 83 : 90*o + 25 : 1)
 (61*o + 62 : 19*o + 24 : 1)

julia> E = elliptic_curve(GF(101), [1, 2]);

julia> gens(E)
1-element Vector{EllipticCurvePoint{FqFieldElem}}:
 (27 : 57 : 1)

source

abelian_group Method

abelian_group(E::EllipticCurve{<:FinFieldElem}) -> FinGenAbGroup, Map

Return an abelian group $A$ isomorphic to the group of rational points of $E$ and a map $E\to A$.

Warning

The map is not implemented yet.

julia> E = elliptic_curve(GF(101, 2), [1, 2]);

julia> A, _ = abelian_group(E);

julia> A
Z/2 x Z/5200

source

Discrete logarithm

disc_log Method

disc_log(P::EllipticCurvePoint, Q::EllipticCurvePoint, [n::IntegerUnion]) -> ZZRingElem

Return the discrete logarithm $m$ of $Q$ with respect to the base $P$, that is, $mP=Q$.

If a multiple $n$ of the order of $P$ is known, this can be supplied as an optional argument.

julia> E = elliptic_curve(GF(101), [1, 2]);

julia> P = E([6, 74])
(6 : 74 : 1)

julia> Q = E([85, 43])
(85 : 43 : 1)

julia> disc_log(P, Q)
13

source