GitHub

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(::Type{T} = BigInt, G::Group) where T

Return the order of $G$ as an instance of T. If $G$ is of infinite order, an InfiniteOrderError exception will be thrown. Use is_finite(G) to avoid this kind of exception. If the order does not fit into type T, an InexactError exception will be thrown.

source
order(::Type{T} = BigInt, g::GroupElem) where T

Return the order of $g$ as an instance of T. If $g$ is of infinite order, an InfiniteOrderError exception will be thrown. Use is_finite_order(G) to avoid this kind of exception. If the order does not fit into type T, an InexactError exception will be thrown.

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

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

Examples

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

julia> order(E)
100
source
order(::Type{T} = ZZRingElem, c::CycleType) where T <: IntegerUnion

Return the order of the permutations with cycle structure c.

Examples

julia> g = symmetric_group(3);

julia> all(x -> order(cycle_structure(x)) == order(x), gens(g))
true
source
order(::Type{T}, W::WeylGroup) where {T} -> T

Returns the order of W.

source
order — Method
order(::Type{T} = BigInt, G::Group) where T

Return the order of $G$ as an instance of T. If $G$ is of infinite order, an InfiniteOrderError exception will be thrown. Use is_finite(G) to avoid this kind of exception. If the order does not fit into type T, an InexactError exception will be thrown.

source
order(::Type{T} = BigInt, g::GroupElem) where T

Return the order of $g$ as an instance of T. If $g$ is of infinite order, an InfiniteOrderError exception will be thrown. Use is_finite_order(G) to avoid this kind of exception. If the order does not fit into type T, an InexactError exception will be thrown.

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

julia> order(P, fac)
100
source
order(::Type{T} = ZZRingElem, c::CycleType) where T <: IntegerUnion

Return the order of the permutations with cycle structure c.

Examples

julia> g = symmetric_group(3);

julia> all(x -> order(cycle_structure(x)) == order(x), gens(g))
true
source
order(::Type{T}, W::WeylGroup) where {T} -> T

Returns the order of W.

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