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)
Point  (2 : 0 : 1)  of Elliptic curve with equation
y^2 = x^3 + x + 2

Cardinality and orders

order Method

order(E::EllipticCurve{<: FinFieldElem}) -> ZZRingElem

Given an elliptic curve $E$ over a finite field $\mathbf{F}$, compute $\mathrm{\#}E(\mathbf{F})$.

Examples

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

julia> order(E)
100

source

order Method

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))
1 * 5^2 * 2^2

julia> order(P, fac)
100

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}}:
 Point  (16*o + 42 : 88*o + 97 : 1)  of Elliptic curve with equation
y^2 = x^3 + x + 2
 Point  (88*o + 23 : 94*o + 22 : 1)  of Elliptic curve with equation
y^2 = x^3 + x + 2

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

julia> gens(E)
1-element Vector{EllipticCurvePoint{FqFieldElem}}:
 Point  (85 : 58 : 1)  of Elliptic curve with equation
y^2 = x^3 + x + 2

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])
Point  (6 : 74 : 1)  of Elliptic curve with equation
y^2 = x^3 + x + 2

julia> Q = E([85, 43])
Point  (85 : 43 : 1)  of Elliptic curve with equation
y^2 = x^3 + x + 2

julia> disc_log(P, Q)
13

source