Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
""" Elliptic curves over finite fields
AUTHORS:
- William Stein (2005): Initial version
- Robert Bradshaw et al....
- John Cremona (2008-02): Point counting and group structure for non-prime fields, Frobenius endomorphism and order, elliptic logs
- Mariah Lenox (2011-03): Added set_order method """
#***************************************************************************** # Copyright (C) 2005 William Stein <wstein@gmail.com> # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 2 of the License, or # (at your option) any later version. # http://www.gnu.org/licenses/ #*****************************************************************************
""" Elliptic curve over a finite field.
EXAMPLES::
sage: EllipticCurve(GF(101),[2,3]) Elliptic Curve defined by y^2 = x^3 + 2*x + 3 over Finite Field of size 101
sage: F=GF(101^2, 'a') sage: EllipticCurve([F(2),F(3)]) Elliptic Curve defined by y^2 = x^3 + 2*x + 3 over Finite Field in a of size 101^2
Elliptic curves over `\ZZ/N\ZZ` with `N` prime are of type "elliptic curve over a finite field"::
sage: F = Zmod(101) sage: EllipticCurve(F, [2, 3]) Elliptic Curve defined by y^2 = x^3 + 2*x + 3 over Ring of integers modulo 101 sage: E = EllipticCurve([F(2), F(3)]) sage: type(E) <class 'sage.schemes.elliptic_curves.ell_finite_field.EllipticCurve_finite_field_with_category'> sage: E.category() Category of schemes over Ring of integers modulo 101
Elliptic curves over `\ZZ/N\ZZ` with `N` composite are of type "generic elliptic curve"::
sage: F = Zmod(95) sage: EllipticCurve(F, [2, 3]) Elliptic Curve defined by y^2 = x^3 + 2*x + 3 over Ring of integers modulo 95 sage: E = EllipticCurve([F(2), F(3)]) sage: type(E) <class 'sage.schemes.elliptic_curves.ell_generic.EllipticCurve_generic_with_category'> sage: E.category() Category of schemes over Ring of integers modulo 95 sage: TestSuite(E).run(skip=["_test_elements"]) """
""" Draw a graph of this elliptic curve over a prime finite field.
INPUT:
- ``*args, **kwds`` - all other options are passed to the circle graphing primitive.
EXAMPLES::
sage: E = EllipticCurve(FiniteField(17), [0,1]) sage: P = plot(E, rgbcolor=(0,0,1)) """ raise NotImplementedError
""" Return a list of all the points on the curve, for prime fields only (see points() for the general case)
EXAMPLES::
sage: S=EllipticCurve(GF(97),[2,3])._points_via_group_structure() sage: len(S) 100
See :trac:`4687`, where the following example did not work::
sage: E=EllipticCurve(GF(2),[0, 0, 1, 1, 1]) sage: E.points() [(0 : 1 : 0)]
::
sage: E=EllipticCurve(GF(2),[0, 0, 1, 0, 1]) sage: E.points() [(0 : 1 : 0), (1 : 0 : 1), (1 : 1 : 1)]
::
sage: E=EllipticCurve(GF(4,'a'),[0, 0, 1, 0, 1]) sage: E.points() [(0 : 1 : 0), (0 : a : 1), (0 : a + 1 : 1), (1 : 0 : 1), (1 : 1 : 1), (a : 0 : 1), (a : 1 : 1), (a + 1 : 0 : 1), (a + 1 : 1 : 1)] """ # TODO, eliminate when polynomial calling is fast
return H0
# else noncyclic group
r""" All the points on this elliptic curve. The list of points is cached so subsequent calls are free.
EXAMPLES::
sage: p = 5 sage: F = GF(p) sage: E = EllipticCurve(F, [1, 3]) sage: a_sub_p = E.change_ring(QQ).ap(p); a_sub_p 2
::
sage: len(E.points()) 4 sage: p + 1 - a_sub_p 4 sage: E.points() [(0 : 1 : 0), (1 : 0 : 1), (4 : 1 : 1), (4 : 4 : 1)]
::
sage: K = GF(p**2,'a') sage: E = E.change_ring(K) sage: len(E.points()) 32 sage: (p + 1)**2 - a_sub_p**2 32 sage: w = E.points(); w [(0 : 1 : 0), (0 : 2*a + 4 : 1), (0 : 3*a + 1 : 1), (1 : 0 : 1), (2 : 2*a + 4 : 1), (2 : 3*a + 1 : 1), (3 : 2*a + 4 : 1), (3 : 3*a + 1 : 1), (4 : 1 : 1), (4 : 4 : 1), (a : 1 : 1), (a : 4 : 1), (a + 2 : a + 1 : 1), (a + 2 : 4*a + 4 : 1), (a + 3 : a : 1), (a + 3 : 4*a : 1), (a + 4 : 0 : 1), (2*a : 2*a : 1), (2*a : 3*a : 1), (2*a + 4 : a + 1 : 1), (2*a + 4 : 4*a + 4 : 1), (3*a + 1 : a + 3 : 1), (3*a + 1 : 4*a + 2 : 1), (3*a + 2 : 2*a + 3 : 1), (3*a + 2 : 3*a + 2 : 1), (4*a : 0 : 1), (4*a + 1 : 1 : 1), (4*a + 1 : 4 : 1), (4*a + 3 : a + 3 : 1), (4*a + 3 : 4*a + 2 : 1), (4*a + 4 : a + 4 : 1), (4*a + 4 : 4*a + 1 : 1)]
Note that the returned list is an immutable sorted Sequence::
sage: w[0] = 9 Traceback (most recent call last): ... ValueError: object is immutable; please change a copy instead. """
else:
""" Returns the cardinality of this elliptic curve over the base field or extensions.
INPUT:
- ``n`` (int) -- a positive integer
OUTPUT:
If `n=1`, returns the cardinality of the curve over its base field.
If `n>1`, returns a list `[c_1, c_2, ..., c_n]` where `c_d` is the cardinality of the curve over the extension of degree `d` of its base field.
EXAMPLES::
sage: p = 101 sage: F = GF(p) sage: E = EllipticCurve(F, [2,3]) sage: E.count_points(1) 96 sage: E.count_points(5) [96, 10368, 1031904, 104053248, 10509895776]
::
sage: F.<a> = GF(p^2) sage: E = EllipticCurve(F, [a,a]) sage: E.cardinality() 10295 sage: E.count_points() 10295 sage: E.count_points(1) 10295 sage: E.count_points(5) [10295, 104072155, 1061518108880, 10828567126268595, 110462212555439192375]
""" except TypeError: raise TypeError("n must be a positive integer")
raise ValueError("n must be a positive integer")
""" Return a random point on this elliptic curve, uniformly chosen among all rational points.
ALGORITHM:
Choose the point at infinity with probability `1/(2q + 1)`. Otherwise, take a random element from the field as x-coordinate and compute the possible y-coordinates. Return the i'th possible y-coordinate, where i is randomly chosen to be 0 or 1. If the i'th y-coordinate does not exist (either there is no point with the given x-coordinate or we hit a 2-torsion point with i == 1), try again.
This gives a uniform distribution because you can imagine `2q + 1` buckets, one for the point at infinity and 2 for each element of the field (representing the x-coordinates). This gives a 1-to-1 map of elliptic curve points into buckets. At every iteration, we simply choose a random bucket until we find a bucket containing a point.
AUTHOR:
- Jeroen Demeyer (2014-09-09): choose points uniformly random, see :trac:`16951`.
EXAMPLES::
sage: k = GF(next_prime(7^5)) sage: E = EllipticCurve(k,[2,4]) sage: P = E.random_element(); P # random (16740 : 12486 : 1) sage: type(P) <class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'> sage: P in E True
::
sage: k.<a> = GF(7^5) sage: E = EllipticCurve(k,[2,4]) sage: P = E.random_element(); P (5*a^4 + 3*a^3 + 2*a^2 + a + 4 : 2*a^4 + 3*a^3 + 4*a^2 + a + 5 : 1) sage: type(P) <class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'> sage: P in E True
::
sage: k.<a> = GF(2^5) sage: E = EllipticCurve(k,[a^2,a,1,a+1,1]) sage: P = E.random_element(); P (a^4 + a : a^4 + a^3 + a^2 : 1) sage: type(P) <class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'> sage: P in E True
Ensure that the entire point set is reachable::
sage: E = EllipticCurve(GF(11), [2,1]) sage: len(set(E.random_element() for _ in range(100))) 16 sage: E.cardinality() 16
TESTS:
See :trac:`8311`::
sage: E = EllipticCurve(GF(3), [0,0,0,2,2]) sage: E.random_element() (0 : 1 : 0) sage: E.cardinality() 1
sage: E = EllipticCurve(GF(2), [0,0,1,1,1]) sage: E.random_point() (0 : 1 : 0) sage: E.cardinality() 1
sage: F.<a> = GF(4) sage: E = EllipticCurve(F, [0, 0, 1, 0, a]) sage: E.random_point() (0 : 1 : 0) sage: E.cardinality() 1
"""
# Choose the point at infinity with probability 1/(2q + 1)
r""" Return the trace of Frobenius acting on this elliptic curve.
.. note::
This computes the curve cardinality, which may be time-consuming.
EXAMPLES::
sage: E=EllipticCurve(GF(101),[2,3]) sage: E.trace_of_frobenius() 6 sage: E=EllipticCurve(GF(11^5,'a'),[2,5]) sage: E.trace_of_frobenius() 802
The following shows that the issue from :trac:`2849` is fixed::
sage: E=EllipticCurve(GF(3^5,'a'),[-1,-1]) sage: E.trace_of_frobenius() -27 """
r""" Special function to compute cardinality when j=1728.
EXAMPLES: An example with q=p=1 (mod 4)
::
sage: F=GF(10009) sage: [EllipticCurve(F,[0,0,0,11^i,0])._cardinality_with_j_invariant_1728() for i in range(4)] [10016, 10210, 10004, 9810]
An example with q=p=3 (mod 4)
::
sage: F=GF(10007) sage: [EllipticCurve(F,[0,0,0,5^i,0])._cardinality_with_j_invariant_1728() for i in range(4)] [10008, 10008, 10008, 10008]
An example with `q=p^2`, p=3 (mod 4)
::
sage: F.<a>=GF(10007^2,'a') sage: [EllipticCurve(F,[0,0,0,a^i,0])._cardinality_with_j_invariant_1728() for i in range(4)] [100160064, 100140050, 100120036, 100140050]
Examples with `q=2^d`, d odd (3 isomorphism classes)::
sage: F.<a> = GF(2**15,'a') sage: ais = [[0,0,1,0,0],[0,0,1,1,0],[0,0,1,1,1]] sage: curves=[EllipticCurve(F,ai) for ai in ais] sage: all([all([e1==e2 or not e1.is_isomorphic(e2) for e1 in curves]) for e2 in curves]) True sage: [e._cardinality_with_j_invariant_1728() for e in curves] [32769, 33025, 32513]
Examples with `q=2^d`, d even (7 isomorphism classes)::
sage: F.<a> = GF(2**16,'a') sage: b = a^11 # trace 1 sage: ais = [[0,0,1,0,0],[0,0,1,0,b],[0,0,1,b,0],[0,0,a,0,0],[0,0,a,0,a^2*b],[0,0,a^2,0,0],[0,0,a^2,0,a^4*b]] sage: curves=[EllipticCurve(F,ai) for ai in ais] sage: all([all([e1==e2 or not e1.is_isomorphic(e2) for e1 in curves]) for e2 in curves]) True sage: [e._cardinality_with_j_invariant_1728() for e in curves] [65025, 66049, 65537, 65793, 65281, 65793, 65281]
Examples with `q=3^d`, d odd (4 isomorphism classes)::
sage: F.<a> = GF(3**15,'a') sage: b=a^7 # has trace 1 sage: ais=[[0,0,0,1,0],[0,0,0,-1,0],[0,0,0,-1,b],[0,0,0,-1,-b]] sage: curves=[EllipticCurve(F,ai) for ai in ais] sage: all([all([e1==e2 or not e1.is_isomorphic(e2) for e1 in curves]) for e2 in curves]) True sage: [e._cardinality_with_j_invariant_1728() for e in curves] [14348908, 14348908, 14342347, 14355469]
Examples with `q=3^d`, d even (6 isomorphism classes)::
sage: F.<g>=GF(3^18,'g') sage: i=F(-1).sqrt() sage: a=g^8 # has trace 1 sage: ais= [[0,0,0,1,0],[0,0,0,1,i*a],[0,0,0,g,0],[0,0,0,g^3,0],[0,0,0,g^2,0], [0,0,0,g^2,i*a*g^3]] sage: curves=[EllipticCurve(F,ai) for ai in ais] sage: all([all([e1==e2 or not e1.is_isomorphic(e2) for e1 in curves]) for e2 in curves]) True sage: [E._cardinality_with_j_invariant_1728() for E in curves] [387459856, 387400807, 387420490, 387420490, 387381124, 387440173]
TESTS:
Check that a bug noted at :trac:`15667` is fixed::
sage: F.<a>=GF(3^6,'a') sage: EllipticCurve([a^5 + 2*a^3 + 2*a^2 + 2*a, a^4 + a^3 + 2*a + 1]).cardinality() 784 sage: EllipticCurve([a^5 + 2*a^3 + 2*a^2 + 2*a, a^4 + a^3 + 2*a + 1]).cardinality_exhaustive() 784
"""
# p=2, j=0=1728 # # Number of isomorphism classes is 3 (in odd degree) or 7 (in even degree) # # The 3 classes are represented, independently of d, # by [0,0,1,0,0], [0,0,1,1,0], [0,0,1,1,1] else: else: # The 7 classes are represented by E1=[0,0,1,0,0], # E2=[0,0,1,0,b], E3=[0,0,1,b,0], E4=[0,0,a,0,0], # E4=[0,0,a,0,a^2*b], E6=[0,0,a^2,0,0], # E7=[0,0,a^2,0,a^4*b], where a is a non-cube and b # has trace 1. E1's Frobenius is pi=(-2)**(d//2); the # Frobeniuses are then pi, -pi, 0; w*pi, -w*pi; # w^2*pi, -w^2*pi where w is either cube root of # unity, so the traces are 2*pi, -2*pi, 0, -pi, +pi; # -pi, +pi. else:
else:
# p=3, j=0=1728 # # Number of isomorphism classes is 4 (odd degree) or 6 (even degree) # # The 4 classes are represented by [0,0,0,1,0], # [0,0,0,-1,0], [0,0,0,-1,a], [0,0,0,-1,-a] where a # has trace 1 else: else: else: # The 6 classes are represented by: [0,0,0,1,0], # [0,0,0,1,i*a]; [0,0,0,g,0], [0,0,0,g^3,0]; # [0,0,0,g^2,0], [0,0,0,g^2,i*a*g^3]; where g # generates the multiplicative group modulo 4th # powers, and a has nonzero trace.
# The curve is isomorphic to [0,0,0,A4,A6]
else: else:
# p>3, j=1728 # # Number of isomorphism classes is 4 if q=1 (mod 4), else 2 # else:
# p=1 (mod 4). First find Frobenius pi=a+b*i for [0,0,0,-1,0] over GF(p): # N(pi)=p and N(pi-1)=0 (mod 8). # else: # p%4==1
# Lift to Frobenius for [0,0,0,-1,0] over GF(p^d):
# Compute appropriate quartic twist:
else:
r""" Special function to compute cardinality when j=0.
EXAMPLES: An example with q=p=1 (mod 6)
::
sage: F=GF(1009) sage: [EllipticCurve(F,[0,0,0,0,11^i])._cardinality_with_j_invariant_0() for i in range(6)] [948, 967, 1029, 1072, 1053, 991]
An example with q=p=5 (mod 6)
::
sage: F=GF(1013) sage: [EllipticCurve(F,[0,0,0,0,3^i])._cardinality_with_j_invariant_0() for i in range(6)] [1014, 1014, 1014, 1014, 1014, 1014]
An example with `q=p^2`, p=5 (mod 6)
::
sage: F.<a>=GF(1013^2,'a') sage: [EllipticCurve(F,[0,0,0,0,a^i])._cardinality_with_j_invariant_0() for i in range(6)] [1028196, 1027183, 1025157, 1024144, 1025157, 1027183]
For examples in characteristic 2 and 3, see the function _cardinality_with_j_invariant_1728() """
# p>3, j=0 # # Number of isomorphism classes is 4 if q=1 (mod 4), else 2 # else:
# p=1 (mod 6). First find Frobenius pi=a+b*w for [0,0,0,0,1] over GF(p): # N(pi)=p and N(pi-1)=0 (mod 12). # else: # p%6==1
# Now pi=a+b*zeta6 with N(pi-1)=0 (mod 12)
# Lift to Frobenius for [0,0,0,0,1] over GF(p^d):
# Compute appropriate sextic twist:
r""" Return the number of points on this elliptic curve.
INPUT:
- ``algorithm`` -- string (default: ``'pari'``), used only for point counting over prime fields:
- ``'pari'`` -- use the baby-step giant-step or Schoof-Elkies-Atkin methods as implemented in the PARI C-library function ``ellap``
- ``'bsgs'`` -- use the baby-step giant-step method as implemented in Sage, with the Cremona-Sutherland version of Mestre's trick
- ``'all'`` -- compute cardinality with both ``'pari'`` and ``'bsgs'``; return result if they agree or raise a ``RuntimeError`` if they do not
- ``extension_degree`` -- an integer `d` (default: 1): if the base field is `\GF{q}`, return the cardinality of ``self`` over the extension `\GF{q^d}` of degree `d`.
OUTPUT:
The order of the group of rational points of ``self`` over its base field, or over an extension field of degree `d` as above. The result is cached.
Over prime fields, one of the above algorithms is used. Over non-prime fields, the serious point counting is done on a standard curve with the same `j`-invariant over the field `\GF{p}(j)`, then lifted to the base field, and finally account is taken of twists.
For `j = 0` and `j = 1728` special formulas are used instead.
EXAMPLES::
sage: EllipticCurve(GF(4, 'a'), [1,2,3,4,5]).cardinality() 8 sage: k.<a> = GF(3^3) sage: l = [a^2 + 1, 2*a^2 + 2*a + 1, a^2 + a + 1, 2, 2*a] sage: EllipticCurve(k,l).cardinality() 29
::
sage: l = [1, 1, 0, 2, 0] sage: EllipticCurve(k, l).cardinality() 38
An even bigger extension (which we check against Magma)::
sage: EllipticCurve(GF(3^100, 'a'), [1,2,3,4,5]).cardinality() 515377520732011331036459693969645888996929981504 sage: magma.eval("Order(EllipticCurve([GF(3^100)|1,2,3,4,5]))") # optional - magma '515377520732011331036459693969645888996929981504'
::
sage: EllipticCurve(GF(10007), [1,2,3,4,5]).cardinality() 10076 sage: EllipticCurve(GF(10007), [1,2,3,4,5]).cardinality(algorithm='pari') 10076 sage: EllipticCurve(GF(next_prime(10**20)), [1,2,3,4,5]).cardinality() 100000000011093199520
The cardinality is cached::
sage: E = EllipticCurve(GF(3^100, 'a'), [1,2,3,4,5]) sage: E.cardinality() is E.cardinality() True sage: E = EllipticCurve(GF(11^2, 'a'), [3,3]) sage: E.cardinality() 128 sage: EllipticCurve(GF(11^100, 'a'), [3,3]).cardinality() 137806123398222701841183371720896367762643312000384671846835266941791510341065565176497846502742959856128
TESTS::
sage: EllipticCurve(GF(10009), [1,2,3,4,5]).cardinality(algorithm='foobar') Traceback (most recent call last): ... ValueError: Algorithm is not known
If the cardinality has already been computed, then the ``algorithm`` keyword is ignored::
sage: E = EllipticCurve(GF(10007), [1,2,3,4,5]) sage: E.cardinality(algorithm='pari') 10076 sage: E.cardinality(algorithm='foobar') 10076 """ # A recursive call to cardinality() with # extension_degree=1, which will cache the cardinality, is # made by the call to frobenius_order() here: return (self.frobenius()**extension_degree-1)**2 else:
# Now extension_degree==1
# use special code for j=0, 1728 (for any field)
# Over prime fields, we have a variety of algorithms to choose from:
algorithm = 'pari' N = self.cardinality_bsgs() N1 = self.cardinality_pari() N2 = self.cardinality_bsgs() if N1 == N2: N = N1 else: raise RuntimeError("BUG! Cardinality with pari=%s but with bsgs=%s"%(N1, N2)) else:
# now k is not a prime field and j is not 0, 1728
# we count points on a standard curve with the same # j-invariant, defined over the field it generates, then lift # to the curve's own field, and finally allow for twists
# Since j is not 0, 1728 the only twists are quadratic
# if not possible to work over a smaller field:
# Let jkj be the j-invariant as element of the smallest finite # field over which j is defined. # j_pol is of the form X - j else: jkj = GF(p**j_deg, name='a', modulus=j_pol).gen()
# recursive call which will do all the real work:
# if curve ia a (quadratic) twist of the "standard" one:
r""" Return the characteristic polynomial of Frobenius.
The Frobenius endomorphism of the elliptic curve has quadratic characteristic polynomial. In most cases this is irreducible and defines an imaginary quadratic order; for some supersingular curves, Frobenius is an integer a and the polynomial is `(x-a)^2`.
.. note::
This computes the curve cardinality, which may be time-consuming.
EXAMPLES::
sage: E=EllipticCurve(GF(11),[3,3]) sage: E.frobenius_polynomial() x^2 - 4*x + 11
For some supersingular curves, Frobenius is in Z and the polynomial is a square::
sage: E=EllipticCurve(GF(25,'a'),[0,0,0,0,1]) sage: E.frobenius_polynomial().factor() (x + 5)^2 """
r""" Return the quadratic order Z[phi] where phi is the Frobenius endomorphism of the elliptic curve
.. note::
This computes the curve cardinality, which may be time-consuming.
EXAMPLES::
sage: E=EllipticCurve(GF(11),[3,3]) sage: E.frobenius_order() Order in Number Field in phi with defining polynomial x^2 - 4*x + 11
For some supersingular curves, Frobenius is in Z and the Frobenius order is Z::
sage: E=EllipticCurve(GF(25,'a'),[0,0,0,0,1]) sage: R=E.frobenius_order() sage: R Order in Number Field in phi with defining polynomial x + 5 sage: R.degree() 1 """
r""" Return the frobenius of self as an element of a quadratic order
.. note::
This computes the curve cardinality, which may be time-consuming.
Frobenius is only determined up to conjugacy.
EXAMPLES::
sage: E=EllipticCurve(GF(11),[3,3]) sage: E.frobenius() phi sage: E.frobenius().minpoly() x^2 - 4*x + 11
For some supersingular curves, Frobenius is in Z::
sage: E=EllipticCurve(GF(25,'a'),[0,0,0,0,1]) sage: E.frobenius() -5 """ else:
r""" Return the cardinality of self over the base field. Simply adds up the number of points with each x-coordinate: only used for small field sizes!
EXAMPLES::
sage: p=next_prime(10^3) sage: E=EllipticCurve(GF(p),[3,4]) sage: E.cardinality_exhaustive() 1020 sage: E=EllipticCurve(GF(3^4,'a'),[1,1]) sage: E.cardinality_exhaustive() 64 """
r""" Return the cardinality of self over the (prime) base field using PARI.
The result is not cached.
EXAMPLES::
sage: p=next_prime(10^3) sage: E=EllipticCurve(GF(p),[3,4]) sage: E.cardinality_pari() 1020 sage: K=GF(next_prime(10^6)) sage: E=EllipticCurve(K,[1,0,0,1,1]) sage: E.cardinality_pari() 999945
TESTS::
sage: K.<a>=GF(3^20) sage: E=EllipticCurve(K,[1,0,0,1,a]) sage: E.cardinality_pari() Traceback (most recent call last): ... ValueError: cardinality_pari() only works over prime fields. sage: E.cardinality() 3486794310
""" else:
r""" Return the cardinality of self over the base field. Will be called by user function cardinality only when necessary, i.e. when the j_invariant is not in the prime field.
ALGORITHM: A variant of "Mestre's trick" extended to all finite fields by Cremona and Sutherland, 2008.
.. note::
1. The Mestre-Schoof-Cremona-Sutherland algorithm may fail for a small finite number of curves over `F_q` for `q` at most 49, so for `q<50` we use an exhaustive count.
2. Quadratic twists are not implemented in characteristic 2 when `j=0 (=1728)`; but this case is treated separately.
EXAMPLES::
sage: p=next_prime(10^3) sage: E=EllipticCurve(GF(p),[3,4]) sage: E.cardinality_bsgs() 1020 sage: E=EllipticCurve(GF(3^4,'a'),[1,1]) sage: E.cardinality_bsgs() 64 sage: F.<a>=GF(101^3,'a') sage: E=EllipticCurve([2*a^2 + 48*a + 27, 89*a^2 + 76*a + 24]) sage: E.cardinality_bsgs() 1031352 """ if verbose: print("q=", q, "< 50 so using exhaustive count") return self.cardinality_exhaustive()
# Construct the quadratic twist: print("Quadratic twist is ", E2.ainvs())
# Throughout, we have #E=q+1-t where |t|<=B and t=a+k*M = a # (mod M) where kmin <= k <= kmax.
# M is the lcm of the orders of all the points found on E1 and # E2, which will eventually exceed 2*B, at which point # kmin=kmax.
N1 *= ZZ(5)**sum([e for P,e in E1._p_primary_torsion_basis(5)]) N2 *= ZZ(5)**sum([e for P,e in E2._p_primary_torsion_basis(5)]) # We now know that t=q+1 (mod N1) and t=-(q+1) (mod N2) print("(a,M)=", (a, M)) self._order = q1-a-kmin*M if verbose: print("no random points were needed") return self._order
# N1, N2 are divisors of the orders of E1, E2 separately, # which are used to speed up the computation of the orders of # points on each curve. For large q it is worth initializing # these with the full order of the (2,3,5)-torsion which are # often non-trivial.
# Get a random point on E1 and find its order, using the # Hasse bounds and the fact that we know that the group # order is a multiple of N1: # update N1 and M # update congruence a (mod M) with q+1 (mod n)
# Get a random point on E2 and find its order, using the # Hasse bounds and the fact that we know that the group # order is a multiple of N2: # update N2 and M # update congruence a (mod M) with -(q+1) (mod n) if verbose: print("number of possibilities is now ",kmax-kmin+1)
def gens(self): r""" Return points which generate the abelian group of points on this elliptic curve.
OUTPUT: a tuple of points on the curve.
- if the group is trivial: an empty tuple.
- if the group is cyclic: a tuple with 1 point, a generator.
- if the group is not cyclic: a tuple with 2 points, where the order of the first point equals the exponent of the group.
.. WARNING::
In the case of 2 generators `P` and `Q`, it is not guaranteed that the group is the cartesian product of the 2 cyclic groups `\langle P \rangle` and `\langle Q \rangle`. In other words, the order of `Q` isn't as small as possible. If you really need to know the group structure, use :meth:`abelian_group`.
EXAMPLES::
sage: E = EllipticCurve(GF(11),[2,5]) sage: P = E.gens()[0]; P # random (0 : 7 : 1) sage: E.cardinality(), P.order() (10, 10) sage: E = EllipticCurve(GF(41),[2,5]) sage: P, Q = E.gens(); P, Q # random ((30 : 13 : 1), (32 : 23 : 1)) sage: P.order()*Q.order() 484 sage: E.cardinality() 44
If the abelian group has been computed, return those generators instead::
sage: E.abelian_group() Additive abelian group isomorphic to Z/22 + Z/2 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 2*x + 5 over Finite Field of size 41 sage: E.abelian_group().gens() ((30 : 13 : 1), (23 : 0 : 1)) sage: E.gens() ((30 : 13 : 1), (23 : 0 : 1)) sage: E.gens()[0].order() 22 sage: E.gens()[1].order() 2
sage: F.<a> = GF(3^6) sage: E = EllipticCurve([a,a+1]) sage: pts = E.gens() sage: len(pts) 1 sage: pts[0].order() == E.cardinality() True sage: E = EllipticCurve(GF(2),[0,0,1,1,1]) sage: E.gens() ()
This works over larger finite fields where :meth:abelian_group may be too expensive::
sage: k.<a> = GF(5^60) sage: E = EllipticCurve([a,a]) sage: len(E.gens()) 2 sage: E.cardinality() # known bug #16931 867361737988403547205571230383620219837340 sage: E.gens()[0].order() # known bug #16931 433680868994201773602785615191810109918670 sage: E.gens()[1].order() # known bug #16931 48186763221577974844753957243534456657630 """
""" Return an iterator through the points of this elliptic curve.
EXAMPLES::
sage: E = EllipticCurve(GF(11), [1,2]) sage: for P in E: print("{} {}".format(P, P.order())) (0 : 1 : 0) 1 (1 : 2 : 1) 4 (1 : 9 : 1) 4 (2 : 1 : 1) 8 ... (10 : 0 : 1) 2 """
""" Return the n'th point in self's __points list. This enables users to iterate over the curve's point set.
EXAMPLES::
sage: E=EllipticCurve(GF(97),[2,3]) sage: S=E.points() sage: E[10] (10 : 76 : 1) sage: E[15] (17 : 10 : 1) sage: for P in E: print(P.order()) 1 50 50 50 50 5 5 50 ... """
r""" Returns the abelian group structure of the group of points on this elliptic curve.
.. warning::
The algorithm is definitely *not* intended for use with *large* finite fields! The factorization of the orders of elements must be feasible. Also, baby-step-giant-step methods are used which have space and time requirements which are `O(\sqrt{q})`.
.. SEEALSO::
If you do not need the complete abelian group structure but only generators of the group, use :meth:`gens` which is much faster.
Also, the algorithm uses random points on the curve and hence the generators are likely to differ from one run to another; but the group is cached so the generators will not change in any one run of Sage.
INPUT:
- ``debug`` - (default: False): if True, print debugging messages
OUTPUT:
- an abelian group
- tuple of images of each of the generators of the abelian group as points on this curve
AUTHORS:
- John Cremona
EXAMPLES::
sage: E=EllipticCurve(GF(11),[2,5]) sage: E.abelian_group() Additive abelian group isomorphic to Z/10 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 2*x + 5 over Finite Field of size 11
::
sage: E=EllipticCurve(GF(41),[2,5]) sage: E.abelian_group() Additive abelian group isomorphic to Z/22 + Z/2 ...
::
sage: F.<a>=GF(3^6,'a') sage: E=EllipticCurve([a^4 + a^3 + 2*a^2 + 2*a, 2*a^5 + 2*a^3 + 2*a^2 + 1]) sage: E.abelian_group() Additive abelian group isomorphic to Z/26 + Z/26 ...
::
sage: F.<a>=GF(101^3,'a') sage: E=EllipticCurve([2*a^2 + 48*a + 27, 89*a^2 + 76*a + 24]) sage: E.abelian_group() Additive abelian group isomorphic to Z/1031352 ...
The group can be trivial::
sage: E=EllipticCurve(GF(2),[0,0,1,1,1]) sage: E.abelian_group() Trivial group embedded in Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 + x + 1 over Finite Field of size 2
Of course, there are plenty of points if we extend the field::
sage: E.cardinality(extension_degree=100) 1267650600228231653296516890625
This tests the patch for :trac:`3111`, using 10 primes randomly selected::
sage: E = EllipticCurve('389a') sage: for p in [5927, 2297, 1571, 1709, 3851, 127, 3253, 5783, 3499, 4817]: ....: G = E.change_ring(GF(p)).abelian_group() sage: for p in prime_range(10000): # long time (19s on sage.math, 2011) ....: if p != 389: ....: G = E.change_ring(GF(p)).abelian_group()
This tests that the bug reported in :trac:`3926` has been fixed::
sage: K.<i> = QuadraticField(-1) sage: OK = K.ring_of_integers() sage: P=K.factor(10007)[0][0] sage: OKmodP = OK.residue_field(P) sage: E = EllipticCurve([0,0,0,i,i+3]) sage: Emod = E.change_ring(OKmodP); Emod Elliptic Curve defined by y^2 = x^3 + ibar*x + (ibar+3) over Residue field in ibar of Fractional ideal (10007) sage: Emod.abelian_group() #random generators (Multiplicative Abelian group isomorphic to C50067594 x C2, ((3152*ibar + 7679 : 7330*ibar + 7913 : 1), (8466*ibar + 1770 : 0 : 1))) """
# Before computing the group structure we compute the # cardinality. While this is not strictly necessary, it makes # the code simpler and also makes computation of orders of # points faster.
# j=0,1728
print("Lower and upper bounds on group order: [",lower,",",upper,"]")
print("Group order already known to be ", N) print("Computing group order naively") print("Computing group order using PARI") else: print("Computing group order using bsgs") print("... group order = ", N)
# At all stages the current subgroup is generated by P1, P2 with # orders n1,n2 which are disjoint. We stop when n1*n2 == N
"About to start generating random points"
"Getting a new random point" print("Q = ", Q, ": Order(Q) = ", Q.order())
print("Adding second generator ",P2," of order ",n2) print("Subgroup order now ",n1*n2,"=",n1,"*",n2) else: # we must merge P2 and Q: if n2>oldn2: print("Replacing second generator by ",P2,end="") print(" of order ",n2, " gaining index ",n2//oldn2) print("Subgroup order now ",n1*n2,"=",n1,"*",n2) P3=(n1//n2)*P1 # so P2,P3 are a basis for n2-torsion if debug: assert P3.order()==n2 P3._order=n2 if debug: print("storing generator ",P3," of ",n2,"-torsion") print("Replacing first generator by ",P1," of order ",end="") print(n1,", gaining index ",n1//oldn1) print("Subgroup order now ",n1*n2,"=",n1,"*",n2)
# Now replace P2 by a point of order n2 s.t. it and # (n1//n2)*P1 are still a basis for n2-torsion: a,m = generic.linear_relation(P1,P3,operation='+') if debug: print("linear relation gives m=",m,", a=",a) P3=P3-(a//m)*P1 if debug: assert P3.order()==m P3._order=m if debug: print("First P2 component =",P3) if m==n2: P2=P3 else: a,m = generic.linear_relation(P1,P2,operation='+') if debug: print("linear relation gives m=",m,", a=",a) P2=P2-(a//m)*P1; if debug: assert P2.order()==m P2._order=m if debug: print("Second P2 component =",P2) P2,n2=generic.merge_points((P2,n2),(P3,m), check=debug) if debug: assert P2.order()==n2 P2._order=n2 if debug: print("Combined P2 component =",P2)
if P1.order()!=n1: print("Generator P1 = ",P1," has order ",P1.order(),end="") print(" and not ",n1) raise ValueError if P2.order()!=n2: print("Generator P2 = ",P2," has order ",P2.order()) print(" and not ", n2) raise ValueError if n2>1: if generic.linear_relation(P1,P2,operation='+')[1]!=n2: print("Generators not independent!") raise ValueError print("Generators: P1 = ",P1," of order ",n1,end="") print(", P2 = ",P2," of order ",n2) print("Subgroup order is now ",n1*n2,"=",n1,"*",n2)
# Finished: record group order, structure and generators
else: # Cache these gens as self.gens()
""" Returns whether or not self is isogenous to other
INPUT:
- ``other`` -- another elliptic curve.
- ``field`` (default None) -- a field containing the base fields of the two elliptic curves into which the two curves may be extended to test if they are isogenous over this field. By default is_isogenous will not try to find this field unless one of the curves can be extended into the base field of the other, in which case it will test over the larger base field.
- ``proof`` (default True) -- this parameter is here only to be consistent with versions for other types of elliptic curves.
OUTPUT:
(bool) True if there is an isogeny from curve ``self`` to curve ``other`` defined over ``field``.
EXAMPLES::
sage: E1 = EllipticCurve(GF(11^2,'a'),[2,7]); E1 Elliptic Curve defined by y^2 = x^3 + 2*x + 7 over Finite Field in a of size 11^2 sage: E1.is_isogenous(5) Traceback (most recent call last): ... ValueError: Second argument is not an Elliptic Curve. sage: E1.is_isogenous(E1) True
sage: E2 = EllipticCurve(GF(7^3,'b'),[3,1]); E2 Elliptic Curve defined by y^2 = x^3 + 3*x + 1 over Finite Field in b of size 7^3 sage: E1.is_isogenous(E2) Traceback (most recent call last): ... ValueError: The base fields must have the same characteristic.
sage: E3 = EllipticCurve(GF(11^2,'c'),[4,3]); E3 Elliptic Curve defined by y^2 = x^3 + 4*x + 3 over Finite Field in c of size 11^2 sage: E1.is_isogenous(E3) False
sage: E4 = EllipticCurve(GF(11^6,'d'),[6,5]); E4 Elliptic Curve defined by y^2 = x^3 + 6*x + 5 over Finite Field in d of size 11^6 sage: E1.is_isogenous(E4) True
sage: E5 = EllipticCurve(GF(11^7,'e'),[4,2]); E5 Elliptic Curve defined by y^2 = x^3 + 4*x + 2 over Finite Field in e of size 11^7 sage: E1.is_isogenous(E5) Traceback (most recent call last): ... ValueError: Curves have different base fields: use the field parameter.
When the field is given:
sage: E1 = EllipticCurve(GF(13^2,'a'),[2,7]); E1 Elliptic Curve defined by y^2 = x^3 + 2*x + 7 over Finite Field in a of size 13^2 sage: E1.is_isogenous(5,GF(13^6,'f')) Traceback (most recent call last): ... ValueError: Second argument is not an Elliptic Curve. sage: E6 = EllipticCurve(GF(11^3,'g'),[9,3]); E6 Elliptic Curve defined by y^2 = x^3 + 9*x + 3 over Finite Field in g of size 11^3 sage: E1.is_isogenous(E6,QQ) Traceback (most recent call last): ... ValueError: The base fields must have the same characteristic. sage: E7 = EllipticCurve(GF(13^5,'h'),[2,9]); E7 Elliptic Curve defined by y^2 = x^3 + 2*x + 9 over Finite Field in h of size 13^5 sage: E1.is_isogenous(E7,GF(13^4,'i')) Traceback (most recent call last): ... ValueError: Field must be an extension of the base fields of both curves sage: E1.is_isogenous(E7,GF(13^10,'j')) False sage: E1.is_isogenous(E7,GF(13^30,'j')) False """ return True else: else: return False if other.cardinality(extension_degree=self.base_field().degree()//other.base_field().degree()) == self.cardinality(): return True else: return False else: else: else: self.cardinality(extension_degree=field.degree()//self.base_field().degree())\ == other.cardinality(extension_degree=field.degree()//other.base_field().degree()): return True else:
r""" Return True if this elliptic curve is supersingular, else False.
INPUT:
- ``proof`` (boolean, default True) -- If True, returns a proved result. If False, then a return value of False is certain but a return value of True may be based on a probabilistic test. See the documentation of the function :meth:`is_j_supersingular` for more details.
EXAMPLES::
sage: F = GF(101) sage: EllipticCurve(j=F(0)).is_supersingular() True sage: EllipticCurve(j=F(1728)).is_supersingular() False sage: EllipticCurve(j=F(66)).is_supersingular() True sage: EllipticCurve(j=F(99)).is_supersingular() False
TESTS::
sage: from sage.schemes.elliptic_curves.ell_finite_field import supersingular_j_polynomial, is_j_supersingular sage: F = GF(103) sage: ssjlist = [F(1728)] + supersingular_j_polynomial(103).roots(multiplicities=False) sage: Set([j for j in F if is_j_supersingular(j)]) == Set(ssjlist) True
"""
r""" Return True if this elliptic curve is ordinary, else False.
INPUT:
- ``proof`` (boolean, default True) -- If True, returns a proved result. If False, then a return value of True is certain but a return value of False may be based on a probabilistic test. See the documentation of the function :meth:`is_j_supersingular` for more details.
EXAMPLES::
sage: F = GF(101) sage: EllipticCurve(j=F(0)).is_ordinary() False sage: EllipticCurve(j=F(1728)).is_ordinary() True sage: EllipticCurve(j=F(66)).is_ordinary() False sage: EllipticCurve(j=F(99)).is_ordinary() True
"""
r""" Set the value of self._order to value.
Use this when you know a priori the order of the curve to avoid a potentially expensive order calculation.
INPUT:
- ``value`` - Integer in the Hasse-Weil range for this curve.
- ``num_checks`` - Integer (default: 8) number of times to check whether value*(a random point on this curve) is equal to the identity.
OUTPUT:
None
EXAMPLES:
This example illustrates basic usage.
::
sage: E = EllipticCurve(GF(7), [0, 1]) # This curve has order 6 sage: E.set_order(6) sage: E.order() 6 sage: E.order() * E.random_point() (0 : 1 : 0)
We now give a more interesting case, the NIST-P521 curve. Its order is too big to calculate with Sage, and takes a long time using other packages, so it is very useful here.
::
sage: p = 2^521 - 1 sage: prev_proof_state = proof.arithmetic() sage: proof.arithmetic(False) # turn off primality checking sage: F = GF(p) sage: A = p - 3 sage: B = 1093849038073734274511112390766805569936207598951683748994586394495953116150735016013708737573759623248592132296706313309438452531591012912142327488478985984 sage: q = 6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449 sage: E = EllipticCurve([F(A), F(B)]) sage: E.set_order(q) sage: G = E.random_point() sage: E.order() * G # This takes practically no time. (0 : 1 : 0) sage: proof.arithmetic(prev_proof_state) # restore state
It is an error to pass a value which is not an integer in the Hasse-Weil range::
sage: E = EllipticCurve(GF(7), [0, 1]) # This curve has order 6 sage: E.set_order("hi") Traceback (most recent call last): ... ValueError: Value hi illegal (not an integer in the Hasse range) sage: E.set_order(3.14159) Traceback (most recent call last): ... ValueError: Value 3.14159000000000 illegal (not an integer in the Hasse range) sage: E.set_order(0) Traceback (most recent call last): ... ValueError: Value 0 illegal (not an integer in the Hasse range) sage: E.set_order(1000) Traceback (most recent call last): ... ValueError: Value 1000 illegal (not an integer in the Hasse range)
It is also very likely an error to pass a value which is not the actual order of this curve. How unlikely is determined by num_checks, the factorization of the actual order, and the actual group structure::
sage: E = EllipticCurve(GF(7), [0, 1]) # This curve has order 6 sage: E.set_order(11) Traceback (most recent call last): ... ValueError: Value 11 illegal (multiple of random point not the identity)
However, set_order can be fooled, though it's not likely in "real cases of interest". For instance, the order can be set to a multiple of the actual order::
sage: E = EllipticCurve(GF(7), [0, 1]) # This curve has order 6 sage: E.set_order(12) # 12 just fits in the Hasse range sage: E.order() 12
Or, the order can be set incorrectly along with num_checks set too small::
sage: E = EllipticCurve(GF(7), [0, 1]) # This curve has order 6 sage: E.set_order(4, num_checks=0) WARNING: No checking done in set_order sage: E.order() 4
The value of num_checks must be an integer. Negative values are interpreted as zero, which means don't do any checking::
sage: E = EllipticCurve(GF(7), [0, 1]) # This curve has order 6 sage: E.set_order(4, num_checks=-12) WARNING: No checking done in set_order sage: E.order() 4
NOTES:
The implementation is based on the fact that orders of elliptic curves are cached in the (pseudo-private) _order slot.
AUTHORS:
- Mariah Lenox (2011-02-16) """ # Is value in the Hasse range? #a = q + 1 - 2*q.isqrt() #b = q + 1 + 2*q.isqrt() # Is value*random == identity?
""" Return a polynomial whose roots are the supersingular `j`-invariants in characteristic `p`, other than 0, 1728.
INPUT:
- `p` (integer) -- a prime number.
ALGORITHM:
First compute H(X) whose roots are the Legendre `\lambda`-invariants of supersingular curves (Silverman V.4.1(b)) in characteristic `p`. Then, using a resultant computation with the polynomial relating `\lambda` and `j` (Silverman III.1.7(b)), we recover the polynomial (in variable ``j``) whose roots are the `j`-invariants. Factors of `j` and `j-1728` are removed if present.
EXAMPLES::
sage: from sage.schemes.elliptic_curves.ell_finite_field import supersingular_j_polynomial sage: f = supersingular_j_polynomial(67); f j^5 + 53*j^4 + 4*j^3 + 47*j^2 + 36*j + 8 sage: f.factor() (j + 1) * (j^2 + 8*j + 45) * (j^2 + 44*j + 24)
::
sage: [supersingular_j_polynomial(p) for p in prime_range(30)] [1, 1, 1, 1, 1, j + 8, j + 9, j + 12, j + 4, j^2 + 2*j + 21]
TESTS::
sage: supersingular_j_polynomial(6) Traceback (most recent call last): ... ValueError: p (=6) should be a prime number
""" except TypeError: raise ValueError("p (=%s) should be a prime number"%p)
# For p in [13..300] we have precomputed these polynomials and store # them (as lists of their coefficients in ZZ) in a dict:
r""" Return True if `j` is a supersingular `j`-invariant.
INPUT:
- ``j`` (finite field element) -- an element of a finite field
- ``proof`` (boolean, default True) -- If True, returns a proved result. If False, then a return value of False is certain but a return value of True may be based on a probabilistic test. See the ALGORITHM section below for more details.
OUTPUT:
(boolean) True if `j` is supersingular, else False.
ALGORITHM:
For small characteristics `p` we check whether the `j`-invariant is in a precomputed list of supersingular values. Otherwise we next check the `j`-invariant. If `j=0`, the curve is supersingular if and only if `p=2` or `p\equiv3\pmod{4}`; if `j=1728`, the curve is supersingular if and only if `p=3` or `p\equiv2\pmod{3}`. Next, if the base field is the prime field `{\rm GF}(p)`, we check that `(p+1)P=0` for several random points `P`, returning False if any fail: supersingular curves over `{\rm GF}(p)` have cardinality `p+1`. If Proof is false we now return True. Otherwise we compute the cardinality and return True if and only if it is divisible by `p`.
EXAMPLES::
sage: from sage.schemes.elliptic_curves.ell_finite_field import is_j_supersingular, supersingular_j_polynomials sage: [(p,[j for j in GF(p) if is_j_supersingular(j)]) for p in prime_range(30)] [(2, [0]), (3, [0]), (5, [0]), (7, [6]), (11, [0, 1]), (13, [5]), (17, [0, 8]), (19, [7, 18]), (23, [0, 3, 19]), (29, [0, 2, 25])]
sage: [j for j in GF(109) if is_j_supersingular(j)] [17, 41, 43] sage: PolynomialRing(GF(109),'j')(supersingular_j_polynomials[109]).roots() [(43, 1), (41, 1), (17, 1)]
sage: [p for p in prime_range(100) if is_j_supersingular(GF(p)(0))] [2, 3, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89] sage: [p for p in prime_range(100) if is_j_supersingular(GF(p)(1728))] [2, 3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83] sage: [p for p in prime_range(100) if is_j_supersingular(GF(p)(123456))] [2, 3, 59, 89]
""" raise ValueError("%s must be an element of a finite field"%j)
# From now on we know that j != 0, 1728
# supersingular j-invariants have degree at most 2:
return False
# if p occurs in the precomputed list, use that:
except KeyError: pass
# Over GF(p), supersingular elliptic curves have cardinality # exactly p+1, so we check some random points in order to detect # non-supersingularity. Over GF(p^2) (for p at least 5) the # cardinality is either (p-1)^2 or (p+1)^2, and the group has # exponent p+1 or p-1, so we can do a similar random check: unless # (p+1)*P=0 for all the random points, or (p-1)*P=0 for all of # them, we can certainly return False.
# First we replace j by an element of GF(p) or GF(p^2) (since F # might be a proper extension of these):
if degj==1: j = -jpol(0) # = j, but in GF(p) elif d>2: F = GF(p^2,'a') j = jpol.roots(F,multiplicities=False)[0] # j, but in GF(p^2)
E = EllipticCurve(j=j) if degj==1: for i in range(10): P = E.random_element() if not ((p+1)*P).is_zero(): return False else: n = None # will hold either p+1 or p-1 later for i in range(10): P = E.random_element() # avoid 2-torsion; we know that a1=a3=0 and #E>4! while P[2].is_zero() or P[1].is_zero(): P = E.random_element()
if n is None: # not yet decided between p+1 and p-1 pP = p*P if not pP[0]==P[0]: # i.e. pP is neither P nor -P return False if pP[1]==P[1]: # then p*P == P != -P n=p-1 else: # then p*P == -P != P n=p+1 else: if not (n*P).is_zero(): return False
# when proof is False we return True for any curve which passes # the probabilistic test:
if not proof: return True
# otherwise we check the trace of Frobenius (which could be # expensive since it involves counting the number of points on E):
return E.trace_of_frobenius() % p == 0
|