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)
Cardinality and orders
order
— Methodorder(::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.
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.
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
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
order(W::WeylGroup) -> ZZRingELem
order(::Type{T}, W::WeylGroup) where {T} -> T
Return the order of W
.
If W
is infinite, an InfiniteOrderError
exception will be thrown.
order
— Methodorder(::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.
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.
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
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
order(W::WeylGroup) -> ZZRingELem
order(::Type{T}, W::WeylGroup) where {T} -> T
Return the order of W
.
If W
is infinite, an InfiniteOrderError
exception will be thrown.
Frobenius
trace_of_frobenius
— Methodtrace_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
trace_of_frobenius
— Methodtrace_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
Group structure of rational points
gens
— Methodgens(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)
abelian_group
— Methodabelian_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$.
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
Discrete logarithm
disc_log
— Methoddisc_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