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. 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.
Acknowledgements
Supersingular Curves
The Order of the Group of Points
Point Counting
Zeta Functions
Cryptographic Elliptic Curve Domains
Enumeration of Points
Abelian Group Structure
Pairings on Elliptic Curves
Weil Pairing
Tate Pairing
Eta Pairing
Ate Pairing
Weil Descent in Characteristic Two
Discrete Logarithms
Bibliography
Supersingular Curves
IsSupersingular(E : parameters) : CrvEll -> BoolElt
SupersingularPolynomial(p) : RngIntElt -> RngUPolElt
IsOrdinary(E) : CrvEll -> BoolElt
IsProbablySupersingular(E) : CrvEll -> BoolElt
The Order of the Group of Points
Point Counting
# H : SetPtEll -> RngIntElt
FactoredOrder(H) : SetPtEll -> RngIntElt
SEA(H : parameters) : SetPtEll -> RngIntElt
Example CrvEllFldFin_SEA (H121E1)
SetVerbose("SEA", v) : MonStgElt, RngIntElt ->
Order(H, r) : SetPtEll, RngIntElt -> RngIntElt
Trace(H): SetPtEll -> RngIntElt
Trace(H, r): SetPtEll, RngIntElt -> RngIntElt
Example CrvEllFldFin_Order (H121E2)
Example CrvEllFldFin_Twists (H121E3)
Zeta Functions
ZetaFunction(E) : CrvEll -> FldFunRatUElt
Example CrvEllFldFin_Invariants to Read (H121E4)
Cryptographic Elliptic Curve Domains
CryptographicCurve(F) : FldFin -> CrvEll, PtEll, RngIntElt, RngIntElt
SetVerbose("ECDom", v) : MonStgElt, RngIntElt ->
Example CrvEllFldFin_CryptographicCurve (H121E5)
Enumeration of Points
Points(E) : CrvEll -> @ PtEll @
Random(E): CrvEll -> PtEll
Abelian Group Structure
AbelianGroup(H) : SetPtEll -> GrpAb, Map
Generators(H) : SetPtEll -> [ PtEll ]
NumberOfGenerators(H) : SetPtEll -> RngIntElt
Example CrvEllFldFin_AbelianGroup (H121E6)
Weil Pairing
WeilPairing(P, Q, n) : PtEll, PtEll, RngIntElt -> RngElt
Tate Pairing
TatePairing(P, Q, n) : PtEll, PtEll, RngIntElt -> RngElt
ReducedTatePairing(P, Q, n) : PtEll, PtEll, RngIntElt -> RngElt
Eta Pairing
EtaTPairing(P, Q, n, q) : PtEll, PtEll, RngIntElt, RngIntElt -> RngElt
ReducedEtaTPairing(P, Q, n, q) : PtEll, PtEll, RngIntElt, RngIntElt -> RngElt
EtaqPairing(P, Q, n, q) : PtEll, PtEll, RngIntElt, RngIntElt -> RngElt
Ate Pairing
AteTPairing(Q, P, n, q) : PtEll, PtEll, RngIntElt, RngIntElt -> RngElt
ReducedAteTPairing(Q, P, n, q) : PtEll, PtEll, RngIntElt, RngIntElt -> RngElt
AteqPairing(P, Q, m, q) : PtEll, PtEll, RngIntElt, RngIntElt -> RngElt
Example CrvEllFldFin_PairingsFiniteFields (H121E7)
Example CrvEllFldFin_MOVWithWeilPairing (H121E8)
Weil Descent in Characteristic Two
WeilDescent(E, k, c) : FldFun, FldFin, FldFinElt -> CrvPln, Map
WeilDescentGenus(E, k, c) : FldFun, FldFin, FldFinElt -> RngIntElt
WeilDescentDegree(E, k, c) : FldFun, FldFin, FldFinElt -> RngIntElt
Example CrvEllFldFin_ec_weil_desc (H121E9)
Discrete Logarithms
Log(Q, P) : PtEll, PtEll -> RngIntElt
Log(Q, P, t) : PtEll, PtEll, RngIntElt -> RngIntElt
Example CrvEllFldFin_ECDL (H121E10)
Bibliography
[Next][Prev] [Right] [____] [Up] [Index] [Root]
Version: V2.19 of
Wed Apr 24 15:09:57 EST 2013