# Elliptic Curves over Finite Fields

This chapter describes the specialised facilities for elliptic curves defined over finite fields. Details concerning their construction, arithmetic, and basic properties may be found in Chapter [Elliptic Curves](../EllipticCurves/index-elliptic-curves.md#crvell). Most of the machinery has been constructed with Elliptic Curve Cryptography in mind.

The first major group of intrinsics relate to the determination of the order of the group of rational points of an elliptic curve over a large finite field. A variety of canonical lift algorithms are provided for characteristic $2$ fields while the SEA algorithm is used for fields having characteristic greater than $2$. These tools are used as the basis for functions that search for curves suitable for cryptographic applications.

A function for computing the Weil pairing forms the basis of the MOV reduction of the discrete logarithm problem (DLP) for a supersingular elliptic curve to a DLP in a finite field. A second type of attack on the DLP is based on the use of Weil descent. Tools implementing a generalisation of the GHS attack for ordinary curves in characteristic $2$ are provided.

Finally, for a direct attack on the DLP for elliptic curves, a parallel collision search version of the Pollard rho algorithm is available.

- [Supersingular Curves](ff_curves-supersingular_curves.md)

  - [`IsSupersingular(E : parameters): CrvEll → BoolElt`](ff_curves-supersingular_curves.md#function-issupersingular-crvell)

  - [`SupersingularPolynomial(p): RngIntElt → RngUPolElt`](ff_curves-supersingular_curves.md#function-supersingularpolynomial-rngintelt)

  - [`IsOrdinary(E): CrvEll → BoolElt`](ff_curves-supersingular_curves.md#function-isordinary-crvell)

  - [`IsProbablySupersingular(E): CrvEll → BoolElt`](ff_curves-supersingular_curves.md#function-isprobablysupersingular-crvell)

- [The Order of the Group of Points](ff_curves-group_points.md)

  - [Point Counting](ff_curves-group_points.md#point-counting)

    - [`# H: SetPtEll → RngIntElt`](ff_curves-group_points.md#operation-operation-setptell-rngintelt)

    - [`# E: CrvEll → RngIntElt`](ff_curves-group_points.md#operation-operation-crvell-rngintelt)

    - [`Order(H): SetPtEll → RngIntElt`](ff_curves-group_points.md#function-order-setptell)

    - [`Order(E): CrvEll → RngIntElt`](ff_curves-group_points.md#function-order-crvell)

    - [`FactoredOrder(H): SetPtEll → RngIntElt`](ff_curves-group_points.md#function-factoredorder-setptell)

    - [`FactoredOrder(E): CrvEll → RngIntElt`](ff_curves-group_points.md#function-factoredorder-crvell)

    - [`SEA(H : parameters): SetPtEll → RngIntElt`](ff_curves-group_points.md#function-sea-setptell)

    - [`SEA(E : parameters): CrvEll → RngIntElt`](ff_curves-group_points.md#function-seaf)

    - [`Example: SEA`](ff_curves-group_points.md#example-ex-05153b)

    - [`SetVerbose("SEA", v): MonStgElt, RngIntElt`](ff_curves-group_points.md#function-setverbose-monstgelt-rngintelt)

    - [`Order(H, r): SetPtEll, RngIntElt → RngIntElt`](ff_curves-group_points.md#function-order-setptell-rngintelt)

    - [`Order(E, r): CrvEll, RngIntElt → RngIntElt`](ff_curves-group_points.md#function-order-crvell-rngintelt)

    - [`Trace(H): SetPtEll → RngIntElt`](ff_curves-group_points.md#function-trace-setptell)

    - [`Trace(E): CrvEll → RngIntElt`](ff_curves-group_points.md#function-trace-crvell)

    - [`TraceOfFrobenius(E): CrvEll → RngIntElt`](ff_curves-group_points.md#function-traceoffrobenius-crvell)

    - [`Trace(H, r): SetPtEll, RngIntElt → RngIntElt`](ff_curves-group_points.md#function-trace-setptell-rngintelt)

    - [`Trace(E, r): CrvEll, RngIntElt → RngIntElt`](ff_curves-group_points.md#function-trace-crvell-rngintelt)

    - [`TraceOfFrobenius(H, r): SetPtEll, RngIntElt → RngIntElt`](ff_curves-group_points.md#function-traceoffrobenius-setptell-rngintelt)

    - [`TraceOfFrobenius(E, r): CrvEll, RngIntElt → RngIntElt`](ff_curves-group_points.md#function-traceoffrobenius-crvell-rngintelt)

    - [`Example: Order`](ff_curves-group_points.md#example-ex-e97387)

    - [`Example: Twists`](ff_curves-group_points.md#example-ex-94b05b)

  - [Zeta Functions](ff_curves-group_points.md#zeta-functions)

    - [`ZetaFunction(E): CrvEll → FldFunRatUElt`](ff_curves-group_points.md#function-zetafunction-crvell)

    - [`Example: Invariants to Read`](ff_curves-group_points.md#example-ex-7a0b38)

  - [Cryptographic Elliptic Curve Domains](ff_curves-group_points.md#cryptographic-elliptic-curve-domains)

    - [`CryptographicCurve(F): FldFin → CrvEll, PtEll, RngIntElt, RngIntElt`](ff_curves-group_points.md#function-ecdom)

    - [`ValidateCryptographicCurve({E, }{P, ordP, h}): CrvEll, PtEll, RngIntElt, RngIntElt → BoolElt`](ff_curves-group_points.md#function-validatecryptographiccurve-crvell-ptell-rngintelt-rngintelt)

    - [`SetVerbose("ECDom", v): MonStgElt, RngIntElt`](ff_curves-group_points.md#function-setverbose-monstgelt-rngintelt-2)

    - [`Example: Cryptographic Curve`](ff_curves-group_points.md#example-ex-a66ecd)

- [Enumeration of Points](ff_curves-points.md)

  - [`Points(E): CrvEll → {@ PtEll @}`](ff_curves-points.md#function-points-crvell)

  - [`Points(H): SetPtEll → {@ PtEll @}`](ff_curves-points.md#function-points-setptell)

  - [`RationalPoints(E): CrvEll → {@ PtEll @}`](ff_curves-points.md#function-rationalpoints-crvell)

  - [`RationalPoints(H): SetPtEll → {@ PtEll @}`](ff_curves-points.md#function-rationalpoints-setptell)

  - [`Random(E): CrvEll → PtEll`](ff_curves-points.md#function-random-crvell)

  - [`Random(H): SetPtEll → PtEll`](ff_curves-points.md#function-random-setptell)

- [Abelian Group Structure](abelian_group.md)

  - [`AbelianGroup(H): SetPtEll → GrpAb, Map`](abelian_group.md#function-abeliangroup-setptell)

  - [`AbelianGroup(E): CrvEll → GrpAb, Map`](abelian_group.md#function-abeliangroup-crvell)

  - [`TorsionSubgroup(H): SetPtEll → GrpAb, Map`](abelian_group.md#function-torsionsubgroup-setptell)

  - [`TorsionSubgroup(E): CrvEll → GrpAb, Map`](abelian_group.md#function-torsionsubgroup-crvell)

  - [`Generators(H): SetPtEll → [ PtEll ]`](abelian_group.md#function-generators-setptell)

  - [`Generators(E): CrvEll → [ PtEll ]`](abelian_group.md#function-generators-crvell)

  - [`NumberOfGenerators(H): SetPtEll → RngIntElt`](abelian_group.md#function-numberofgenerators-setptell)

  - [`NumberOfGenerators(E): CrvEll → RngIntElt`](abelian_group.md#function-numberofgenerators-crvell)

  - [`Ngens(H): SetPtEll → RngIntElt`](abelian_group.md#function-ngens-setptell)

  - [`Ngens(E): CrvEll → RngIntElt`](abelian_group.md#function-ngens-crvell)

  - [`Example: Abelian Group`](abelian_group.md#example-ex-04fd99)

- [Pairings on Elliptic Curves](pairings.md)

  - [Weil Pairing](pairings.md#weil-pairing)

    - [`WeilPairing(P, Q, n): PtEll, PtEll, RngIntElt → RngElt`](pairings.md#function-weilpairing-ptell-ptell-rngintelt)

  - [Tate Pairing](pairings.md#tate-pairing)

    - [`TatePairing(P, Q, n): PtEll, PtEll, RngIntElt → RngElt`](pairings.md#function-tatepairing-ptell-ptell-rngintelt)

    - [`ReducedTatePairing(P, Q, n): PtEll, PtEll, RngIntElt → RngElt`](pairings.md#function-reducedtatepairing-ptell-ptell-rngintelt)

  - [Eta Pairing](pairings.md#eta-pairing)

    - [`EtaTPairing(P, Q, n, q): PtEll, PtEll, RngIntElt, RngIntElt → RngElt`](pairings.md#function-etatpairing-ptell-ptell-rngintelt-rngintelt)

    - [`ReducedEtaTPairing(P, Q, n, q): PtEll, PtEll, RngIntElt, RngIntElt → RngElt`](pairings.md#function-reducedetatpairing-ptell-ptell-rngintelt-rngintelt)

    - [`EtaqPairing(P, Q, n, q): PtEll, PtEll, RngIntElt, RngIntElt → RngElt`](pairings.md#function-etaqpairing-ptell-ptell-rngintelt-rngintelt)

  - [Ate Pairing](pairings.md#ate-pairing)

    - [`AteTPairing(Q, P, n, q): PtEll, PtEll, RngIntElt, RngIntElt → RngElt`](pairings.md#function-atetpairing-ptell-ptell-rngintelt-rngintelt)

    - [`ReducedAteTPairing(Q, P, n, q): PtEll, PtEll, RngIntElt, RngIntElt → RngElt`](pairings.md#function-reducedatetpairing-ptell-ptell-rngintelt-rngintelt)

    - [`AteqPairing(P, Q, m, q): PtEll, PtEll, RngIntElt, RngIntElt → RngElt`](pairings.md#function-ateqpairing-ptell-ptell-rngintelt-rngintelt)

    - [`Example: Pairings Finite Fields`](pairings.md#example-ex-cdc875)

    - [`Example: MOV With Weil Pairing`](pairings.md#example-ex-a16e5c)

- [Weil Descent in Characteristic Two](ec_weil_desc.md)

  - [`WeilDescent(E, k, c): FldFun, FldFin, FldFinElt → CrvPln, Map`](ec_weil_desc.md#function-crvell-ec-weil-desc)

  - [`WeilDescentGenus(E, k, c): FldFun, FldFin, FldFinElt → RngIntElt`](ec_weil_desc.md#function-weildescentgenus-fldfun-fldfin-fldfinelt)

  - [`WeilDescentDegree(E, k, c): FldFun, FldFin, FldFinElt → RngIntElt`](ec_weil_desc.md#function-weildescentdegree-fldfun-fldfin-fldfinelt)

  - [`Example: Ec Weil Desc`](ec_weil_desc.md#example-ex-352154)

- [Discrete Logarithms](discrete_logs.md)

  - [`Log(Q, P): PtEll, PtEll → RngIntElt`](discrete_logs.md#function-log-ptell-ptell)

  - [`Log(Q, P, t): PtEll, PtEll, RngIntElt → RngIntElt`](discrete_logs.md#function-log-ptell-ptell-rngintelt)

  - [`Example: ECDL`](discrete_logs.md#example-ex-fd64db)