The functions in this section are only defined for elliptic curves over a finite field.
Proof: BoolElt Default: true
Returns false if the elliptic curve E is ordinary, otherwise proves that E is supersingular. If the parameter Proof is set to false, then the effect of the function is the same as that of IsProbablySupersingular(E).
Returns false if E is proved to be ordinary, otherwise true. The algorithm is nondeterministic, and repeated tests are independent.
The logical negation of IsSupersingular(E).
In this section the descriptions will refer to a point set H, which is either the H in the signature or the base point set of the elliptic curve E in the signature.
Returns the set of rational points of the point set H, including the point at infinity.
Returns a random rational point of H. Every rational point has a roughly equal chance of being selected, including the zero element.
Magma contains an efficient implementation of the Schoof--Elkies--Atkin (SEA) algorithm, with Lercier's extension to base fields of characteristic 2, for computing the number of points on an elliptic curve over a finite field. Calculations are performed in the smallest field over which the curve is defined, and the result is lifted to the original field.
Like all group functions on elliptic curves, these intrinsics really apply to a particular point set; the curve is identified with its base point set for the purposes of these functions. To aid exposition only the versions that take the curves are shown but an appropriate point set (over a finite field) may be used instead.
The order of the group of K-rational points of E, where E is an elliptic curve defined over the finite field K.
This function returns the factorization of the order of the group of K-rational points of E, where E is an elliptic curve defined over the finite field K. This factorization is computed and stored once within E, and is reused when computing the order of points on E.
Al: MonStgElt Default: "Default"
MaxSmooth: RngIntElt Default: Infinity
AbortLevel: RngIntElt Default: 0
This is the internal algorithm used by the point counting routines, but it can be invoked directly if desired. The most obvious reason to do this is because of the parameters AbortLevel and MaxSmooth, which allow the computation to be stopped early if it can be shown not to satisfy certain conditions (such as the order of the group being prime). Warning: Unlike the external functions which call this (such as Order and FactoredOrder), this routine does not store the computed group order back on the curve itself, and so functions which need the group order will have to compute it again.The parameter Al can be set to one of "Enumerate", "BSGS", or "Default". Setting Al := "Enumerate" causes the group order to be found by enumeration of all points on the curve, and hence is only practical for small orders. Setting Al := "BSGS" is currently equivalent to choosing Al := "Default", which uses point enumeration for suitably small finite fields and the full Schoof--Elkies--Atkin algorithm otherwise.
The parameter MaxSmooth can be used to specify a limit on the number of small primes that divide the group order. That is, we will consider the group order to be "smooth" if it is divisible by the product of small primes and this product is larger than the value of MaxSmooth. Then the possible values of AbortLevel have the following meanings:
One common use of these parameters is when searching for a curve with prime order. Setting MaxSmooth := 1 will cause the early termination of the algorithm if a small factor of the order is found. If the algorithm did not abort then the group order is not necessarily prime, however --- this just means that no small prime dividing the order was encountered during the computation.
- 0 : abort if the curve has smooth order.
- 1 : abort if both the curve and its twist have smooth order.
- 2 : abort if either the curve or its twist have smooth order. hfil If the early abort is triggered then the returned group order is 0.
> p := NextPrime(10^9); > p; 1000000007 > K := GF(p); > E := EllipticCurve([K | -1, 1]); > time SEA(E : MaxSmooth := 1); 0 Time: 0.020 > time #E; 1000009476 Time: 0.140For curves this small the amount of time saved by an early abort is fairly small, but for curves over large fields the savings can be quite significant. As mentioned above, even when SEA does not abort there is no guarantee that the curve has prime order:
> E := EllipticCurve([K | 0, 1]); > time SEA(E : MaxSmooth := 1); 1000000008 > IsSupersingular(E); true > E := EllipticCurve([K | -30, 1]); > time SEA(E : MaxSmooth := 1); 1000035283 > Factorization($1); [ <13, 1>, <709, 1>, <108499, 1> ]In the first case the curve was supersingular, and so the order was easily computed directly; thus no early abort was attempted. The latter case shows that small primes may not be looked at even when the curve is ordinary.
Now let's find a curve with prime order:
> for k in [1..p] do > E := EllipticCurve([K | k, 1]); > n := SEA(E : MaxSmooth := 1); > if IsPrime(n) then > printf "Found curve of prime order %o for k = %o\n", n, k; > break; > end if; > end for; Found curve of prime order 999998501 for k = 29 > E; Elliptic Curve defined by y^2 = x^3 + 29*x + 1 over GF(1000000007) > #E; 999998501
This procedure changes the verbose printing level for the SEA algorithm which counts the number of points on an elliptic curve. Currently the legal values for v are false, true, or an integer between 0 and 5 (inclusive), where false is equivalent to 0 and true equivalent to 1. A nonzero value gives information during the course of the algorithm, increased in verbosity for higher values of v.
N.B. The previous name for this verbose flag, "ECPointCount" is now deprecated and will be removed in a future release. It should continue to function in this release, but its verbose levels are different to those of "SEA".
The order of E over the extension field of K of degree r, where K is the base field of E. The order is found by calculating the order of E over K and lifting.
The trace of the Frobenius endomorphism on E, equal to q + 1 - n, where q is the cardinality of the coefficient field and n is the order of the group of rational points of E.
The trace of the r-th power Frobenius endomorphism, where E is an elliptic curve over a finite field.
> FF := GF(2^133); > E := EllipticCurve([1,0,0,0,FF.1]); > time #E; 10889035741470030830941160923712974513152 Time: 15.370 > FactoredOrder(E); [ <2, 10>, <3, 2>, <150959, 1>, <654749, 1>, <11953995917236774217401867, 1> ] > time TraceOfFrobenius(E); -113173485896391746559 Time: 0.000 > time TraceOfFrobenius(E,3); 2247497466279379392112525914232899060001042788725924296315905 Time: 0.000
> E := EllipticCurve(GF(101^2)!0); > Twists(E); [ Elliptic Curve defined by y^2 = x^3 + 1 over GF(101^2), Elliptic Curve defined by y^2 = x^3 + (61*w + 91) over GF(101^2), Elliptic Curve defined by y^2 = x^3 + (98*w + 16) over GF(101^2), Elliptic Curve defined by y^2 = x^3 + (9*w + 66) over GF(101^2), Elliptic Curve defined by y^2 = x^3 + (59*w + 76) over GF(101^2), Elliptic Curve defined by y^2 = x^3 + (87*w + 81) over GF(101^2) ] > IsSupersingular(E); trueSince E is supersingular, so are the twists of E. Hence the traces are divisible by the prime:
> [ TraceOfFrobenius(F) : F in Twists(E) ]; [ -202, -101, 101, 202, 101, -101 ] > [ TraceOfFrobenius(F) : F in QuadraticTwists(E) ]; [ -202, 202 ]We see that the traces come in pairs; the trace of a curve is the negative of the trace of its quadratic twist. This is not just true of the supersingular curves:
> E := EllipticCurve(GF(101^2)!12^3); > Twists(E); [ Elliptic Curve defined by y^2 = x^3 + x over GF(101^2), Elliptic Curve defined by y^2 = x^3 + (40*w + 53)*x over GF(101^2), Elliptic Curve defined by y^2 = x^3 + (3*w + 99)*x over GF(101^2), Elliptic Curve defined by y^2 = x^3 + (92*w + 19)*x over GF(101^2) ] > IsSupersingular(E); false > [ TraceOfFrobenius(F) : F in Twists(E) ]; [ -198, 40, 198, -40 ] > [ TraceOfFrobenius(F) : F in QuadraticTwists(E) ]; [ -198, 198 ]
Given an elliptic curve E over a finite field, returns the zeta function of E as a rational function in one variable.
everypar{hangindent=0pt hangafter=0} Note that each of the function calls Order(E), Trace(E), and ZetaFunction(E) invoke the same call to the SEA algorithm and determine equivalent data.
((d log zeta_E(t))/(d log t)) = sum_(n=1)^(Infinity) |E(F_(q^n))| t^n
The following example illustrates this property of zeta_E(t).
> p := 11; > E := EllipticCurve([GF(p)|1, 2]); > Z := ZetaFunction(E); > Q<t> := LaurentSeriesRing(Rationals()); > t*Derivative(Log(Evaluate(Z,t))) + O(t^7); 16*t + 128*t^2 + 1264*t^3 + 14848*t^4 + 160976*t^5 + 1769600*t^6 + O(t^7) > [ Order(E,n) : n in [1..6] ]; [ 16, 128, 1264, 14848, 160976, 1769600 ]
Like all group functions on elliptic curves, these intrinsics really apply to a particular point set; the curve is identified with its base point set for the purposes of these functions. To aid exposition only the versions that take the curves are shown but an appropriate point set (over a finite field) may be used instead.
Computes the abelian group isomorphic to the group of rational points on the elliptic curve E over a finite field. The function returns two values: an abelian group A and a map m from A to E. The map m provides an isomorphism between the abstract group A and the group of rational points on the curve.
Given an elliptic curve E defined over a finite field, this function returns generators for the group of points of E. The i-th element of the sequence corresponds to the i-th generator of the group as returned by the function AbelianGroup.
The number of generators of the group of rational points of E; this is simply the length of the sequence returned by Generators(E).
The i-th generator of the group of rational points of E; this is the i-th element of the sequence returned by Generators(E)).
> p := 1048583; > FF<w> := FiniteField(p^2); > E := EllipticCurve([ 1016345*w + 272405, 660960*w + 830962 ]); > A, m := AbelianGroup(E); > A; Abelian Group isomorphic to Z/3 + Z/366508289334 Defined on 2 generators Relations: 3*A.1 = 0 366508289334*A.2 = 0 > Generators(E); [ (191389*w + 49138 : 878749*w + 1008891 : 1), (852793*w + 24192 : 376202*w + 48552 : 1) ] > m(A.1) eq E.1; true > m(A.2) eq E.2; true
Computing discrete logarithms on elliptic curves over finite fields is considered to be a very difficult problem. The best algorithms for general elliptic curves take exponential time, and do not take much advantage of properties of the curve. Thus, solving such problems can be computationally infeasible for large curves. Indeed, elliptic curves are appearing more appealing for applications in cryptography all the time.
Although hard instances of the elliptic curve discrete logarithm may be impossible to solve, Magma is able to efficiently solve reasonable sized instances, or instances where the large prime factor of the order of the base point is not too big. Magma does this as follows. The first step is to compute the factorization of the order of the base point, which may require calling SEA if the order of the curve is not already known to Magma. Then it checks that the order of the base point is a multiple of the order of the other point. If this is not true, then there is no solution. It next breaks the problem down to solving the discrete logarithm modulo the prime power factors of the order using the Pohlig-Hellman algorithm. For small primes, it will try to solve it by exhaustive search. If a solution does not exist, Magma might determine this during the exhaustive search, and then abort the remaining computations. For the larger prime power factors, Magma uses the parallel collision search version of Pollard's rho algorithm. The implementation includes Edlyn Teske's idea of r-adding walks, and Michael Wiener's and Robert Zuccherato's idea of treating the point P the same as -P (for curves of the form y^2 = x^3 + a x + b) so as to reduce the search space by a factor of 1/Sqrt(2) (this idea was independently discovered by other researchers). It should be noted that Magma is not always able to determine the nonexistence of a solution, and therefore may run forever if given very bad parameters. For this reason, the user has the option of setting a time limit on the calculation.
The discrete log of P to the base Q (an integer n satisfying n * Q = P where 0 <= n < Order(Q)). The arguments Q and P must be points on the same elliptic curve, which must be defined over a finite field. The function returns -1 if it is determined that no solution exists.
The discrete log of P to the base Q (an integer n satisfying n * Q = P where 0 <= n < Order(Q)). The arguments Q and P must be points on the same elliptic curve, which must be defined over a finite field. The argument t is a time limit in seconds on the calculation: if this limit is exceeded the calculation is aborted. The time limit t must be a small positive integer. This function returns -1 if it is determined that no solution exists; if the calculation is aborted due to the time limit being exceeded then -2 is returned.
> GetSeed(); 1020 132 > K := GF(RandomPrime(40)); > E := EllipticCurve([Random(K), Random(K)]); > E; Elliptic Curve defined by y^2 = x^3 + 456271502613*x + 504334195864 over GF(742033232201) > Q := Random(E); > Q; (174050269867 : 191768822966 : 1) > FactoredOrder(Q); [ <31, 1>, <7789, 1>, <3073121, 1> ] > P := Random(Order(Q))*Q; > P; (602107809261 : 356483659853 : 1) > m := Log(Q, P); > m; 679095763051 > m*Q - P; (0 : 1 : 0)