r""" Implementation of necklaces on elliptic curves. Version March 2025 The aim is to provide functionality for working explicitly with points on the modular curve X+_{nsp}(p) using the moduli interpretation via necklaces. One task that we can now perform is to check if two distinct rational points on the curve have equal reduction modulo a prime ell. Usage: v = Necklace(E,p) for an elliptic curve E/Q and a prime p has these useful methods v.isogeny_field() gives a number field K v.list_of_j_invariants() gives a list of elements in K this represents in necklace in that order v.list_of_isogenies() gives the actual isogenies v.find_splitting_prime() gives a prime ell s.t. the isogenies are defined over F_ell vt = v.reduction(ell) gives a reduced necklace at ell vt = ReducedCMNecklace(E,p,ell) same but for a cm curve E vt.isogeny_field() gives a finite field FF of char ell vt.list_of_j_invariants() gives now elements in FF vt.list_of_reduced_isogenies() gives the isogenies over FF vt.list_of_pearls() gives the pearls as polynomials vt == vt2 proves if the two necklaces represent the same point on X(F_ell) list_of_interesting_examples(p) gives labels of curves with a necklace in E[p] defined over Q Currently, this only works if executed in a directory containing a subdir called modpolys in which the relevant files of Phi by Sutherland. For curves with cm it is much quicker to use ReducedCMNecklace(E,p,ell) as this avoids the computation of any hard global information about the necklace. For the curves with j=0 and j=1728, the global approach is not implemented. EXAMPLES:: sage: E = EllipticCurve('4900j1') sage: v = Necklace(E,5) sage: v.isogeny_field() Number Field in s with defining polynomial x^12 + x^11 + 12*x^10 + 9*x^9 + 50*x^8 - 17*x^7 + 101*x^6 + 70*x^5 + 42*x^4 - 288*x^3 + 768*x^2 - 1104*x + 716 sage: js = v.list_of_j_invariants() sage: len(js) 6 sage: phis = v.list_of_isogenies() sage: phis[0].degree() 5 sage: E2 = phis[1].codomain() sage: E2.j_invariant() in js True sage: v.find_splitting_prime() 179 sage: vt = v.reduction(179) sage: vt.isogeny_field().order() 179 sage: vt.list_of_j_invariants() [164, 25, 115, 162, 27, 79] sage: psis = vt.list_of_reduced_isogenies() sage: psis[0].degree() 5 sage: vt = v.reduction(3) sage: vt Reduced necklace with j-invariants [z^5 + z^4 + z^3 + 2*z^2 + 2*z + 1, z^5 + z^4 + 2*z^3 + 2*z^2 + 1, z^5 + 2*z^4 + z + 1, 2*z^4 + z^2 + z + 2, z^5 + 2*z^3 + z^2, 2*z^5 + z^3 + 2*z + 2] in the 5-torsion of Elliptic Curve defined by y^2 = x^3 + 2*x^2 + x + 2 over Finite Field of size 3 sage: vt.isogeny_field().order() 729 sage: v = Necklace(EllipticCurve("232544h1"),11) sage: v Necklace in the 11-torsion of Elliptic Curve defined by y^2 = x^3 - 6682520*x - 39157150032 over Rational Field sage: v.find_splitting_prime() 353 sage: v.reduction(353) Reduced necklace with j-invariants [195, 31, 21, 232, 224, 305, 61, 131, 180, 335, 297, 291] in the 11-torsion of Elliptic Curve defined by y^2 = x^3 + 123*x + 131 over Finite Field of size 353 sage: vt = v.reduction(5) sage: phis = vt.list_of_reduced_isogenies() sage: vt Reduced necklace with j-invariants [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] in the 11-torsion of Elliptic Curve defined by y^2 = x^3 + 3 over Finite Field of size 5 sage: [phi.kernel_polynomial() for phi in phis] [x^5 + (4*z + 3)*x^4 + (3*z + 2)*x^3 + 4*x^2 + (2*z + 1)*x + z, x^5 + (2*z + 3)*x^4 + (2*z + 3)*x^3 + 4*x^2 + x + 2*z + 4, x^5 + (z + 4)*x^4 + (4*z + 2)*x^3 + 3*x^2 + x + 4*z + 1, x^5 + 2*z*x^4 + (z + 2)*x^3 + 4*x^2 + (2*z + 1)*x + 4*z, x^5 + (3*z + 1)*x^4 + (z + 1)*x^3 + 3*x^2 + (3*z + 3)*x + 4*z, x^5 + (4*z + 1)*x^4 + 2*x^3 + 3*x^2 + (3*z + 3)*x + 3*z + 1, x^5 + (z + 2)*x^4 + 2*z*x^3 + 4*x^2 + (3*z + 3)*x + 4*z + 1, x^5 + 3*z*x^4 + 3*z*x^3 + 4*x^2 + x + 3*z + 1, x^5 + 4*z*x^4 + (z + 1)*x^3 + 3*x^2 + x + z, x^5 + (3*z + 2)*x^4 + (4*z + 3)*x^3 + 4*x^2 + (3*z + 3)*x + z + 4, x^5 + (2*z + 4)*x^4 + (4*z + 2)*x^3 + 3*x^2 + (2*z + 1)*x + z + 4, x^5 + z*x^4 + 2*x^3 + 3*x^2 + (2*z + 1)*x + 2*z + 4] sage: v = Necklace(EllipticCurve("4489a1"),13) sage: v Necklace in the 13-torsion of Elliptic Curve defined by y^2 + y = x^3 - 7370*x + 243528 over Rational Field sage: v.reduction(5) Reduced necklace with j-invariants [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] in the 13-torsion of Elliptic Curve defined by y^2 + y = x^3 + 3 over Finite Field of size 5 # check all cm cases that are equal for ell>3: sage: def checkcm(la,la2,p,ell): ....: return ReducedCMNecklace(EllipticCurve(la),p,ell) == ReducedCMNecklace(EllipticCurve(la2),p,ell) ....: sage: checkcm("49a1","26569a1",5,7) True sage: checkcm("26569a1","49a1",5,7) True sage: checkcm("1849a1","4489a1",5,7) True sage: checkcm("4489a1","1849a1",5,7) True sage: checkcm("27a4","26569a1",5,11) True sage: checkcm("26569a1","27a4",5,11) True sage: checkcm("26569a1","256d1",5,13) True sage: checkcm("256d1","26569a1",5,13) True sage: checkcm("49a2","4489a1",5,13) True sage: checkcm("4489a1","49a2",5,13) True sage: checkcm("36a2","26569a1",5,17) True sage: checkcm("26569a1","36a2",5,17) True sage: checkcm("256d1","26569a1",7,5) True sage: checkcm("26569a1","256d1",7,5) True sage: checkcm("26569a1","4489a1",7,13) True sage: checkcm("4489a1","26569a1",7,13) True """ import ast from sage.all import * from sage.misc.verbose import verbose from sage.structure.unique_representation import CachedRepresentation from sage.schemes.elliptic_curves.hom_sum import EllipticCurveHom_sum from sage.schemes.elliptic_curves.hom_scalar import EllipticCurveHom_scalar from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite from sage.schemes.elliptic_curves.weierstrass_morphism import \ WeierstrassIsomorphism from sage.rings.morphism import RingHomomorphism def list_of_interesting_examples(p): """ Return a list of labels of curves which have necklaces for the given prime p such that we should be able to calculate it. For every j-invariant there is at most one label. """ if p < 3 or not p.is_prime(): raise ValueError("p must be an odd prime.") # non cm is downloaded from lmfbd if p == 3: return ['32a2', '32a3', '49a1', '49a2', '361a1', '1849a1', '4489a1', '26569a1', '245a1', '352f1', '722b1', '864i1', '864a1', '1184h1', '1323s1', '1323p1', '1369f2', '1369f1', '1568f2', '1568f1', '1888d1', '1952d1', '2205b2', '2205b1', '2656f1', '3168o1', '3168o2', '3283c1', '3328f1', '4107b2', '4107b1', '4165g1', '4165d2', '4165d1', '4192c1', '4225n2', '4225n1', '4704w2', '4704w1', '4949b1', '5344a1', '5408g1', '5888c2', '5888c1', '6241b1', '6498b2', '6498b1', '6615g1', '6727b1', '6727b2', '6912b1', '8032c1', '8096c1', '8281m1', '8477d1', '8800ba1', '9504k1', '9952b1'] elif p == 5: return ['27a1', '49a1', '256a1', '675b1', '1044a1', '1849a1', '3132a1', '4489a1', '4900j1', '6372a1', '6507a1', '6588e1', '9693c1', '9756c1', '13225i1', '13671b1', '16173d1', '18324c1', '19575k1', '27225k1', '33536d1', '34349h1', '43659s1', '52900b1', '81356f1', '93100o1', '96921b1', '100575e1', '101925e1', '112225h1', '120825h1', '150871a1', '174717e1', '185269d1', '197748a1', '207616a1', '213559b1', '234171p1', '249777j1', '269059d1', '269059q1', '280525h1', '295119f1', '303236c1', '306779b1', '313600bz1', '396900b1', '401261f1', '421596m1', '431433g1', '470988i1', '475983c1', '490284a1', '495477a1'] elif p == 7: return ['32a2', '32a3', '121b1', '256d1', '1849a1', '4489a1', '26569a1', '15341b1', '32544be1', '39325p1', '65533a1', '163072bq1', '189728cg1'] elif p == 11: return ['27a3', '27a4', '32a2', '32a3', '36a2', '4489a1', '26569a1', "232544f1"] else: return rational_cm_points(p) def rational_cm_points(p): """ Return the cm points on X+_nsp(p) defined over Q. For p>11, we expect this to be all rational points. It returns a list of Cremona labels EXAMPLES:: sage: rational_cm_points(13) ['49a1', '49a2', '121b1', '256d1', '361a1', '4489a1', '26569a1'] sage: rational_cm_points(17) ['27a3', '27a4', '36a2', '49a1', '49a2', '121b1', '26569a1'] sage: for p in prime_range(19,50): ....: print (p, len(rational_cm_points(p))) ....: 19 7 23 7 29 8 31 8 37 4 41 8 43 4 47 8 The first curve with no known rational points on it:: sage: rational_cm_points(15073) [] """ if p < 3 or not p.is_prime(): raise ValueError("p must be an odd prime.") # cremona label for each j-invariant of a cm # curve defined over QQ cmlabels = ['27a3', '27a4', '32a2', '32a3', '36a2', '49a1', '49a2', '121b1', '256d1', '361a1', '1849a1', '4489a1', '26569a1'] res = [] for la in cmlabels: A = EllipticCurve(la) if A.conductor() % p != 0 and A.ap(p) == 0: res.append(la) return res def modular_polynomial(p): """ Load the modular polynomial Phi_p(X,Y) from Sutherland's files from https://math.mit.edu/~drew/ClassicalModPolys.html EXAMPLES:: sage: modular_polynomial(5) -X^5*Y^5 + 3720*X^5*Y^4 + 3720*X^4*Y^5 - 4550940*X^5*Y^3 + 1665999364600*X^4*Y^4 - 4550940*X^3*Y^5 + 2028551200*X^5*Y^2 + 107878928185336800*X^4*Y^3 + 107878928185336800*X^3*Y^4 + 2028551200*X^2*Y^5 + X^6 - 246683410950*X^5*Y + 383083609779811215375*X^4*Y^2 - 441206965512914835246100*X^3*Y^3 + 383083609779811215375*X^2*Y^4 - 246683410950*X*Y^5 + Y^6 + 1963211489280*X^5 + 128541798906828816384000*X^4*Y + 26898488858380731577417728000*X^3*Y^2 + 26898488858380731577417728000*X^2*Y^3 + 128541798906828816384000*X*Y^4 + 1963211489280*Y^5 + 1284733132841424456253440*X^4 - 192457934618928299655108231168000*X^3*Y + 5110941777552418083110765199360000*X^2*Y^2 - 192457934618928299655108231168000*X*Y^3 + 1284733132841424456253440*Y^4 + 280244777828439527804321565297868800*X^3 + 36554736583949629295706472332656640000*X^2*Y + 36554736583949629295706472332656640000*X*Y^2 + 280244777828439527804321565297868800*Y^3 + 6692500042627997708487149415015068467200*X^2 - 264073457076620596259715790247978782949376*X*Y + 6692500042627997708487149415015068467200*Y^2 + 53274330803424425450420160273356509151232000*X + 53274330803424425450420160273356509151232000*Y + 141359947154721358697753474691071362751004672000 """ finame = "modpolys/phi_j_"+str(p)+".txt" if not os.path.isfile(finame): raise ValueError("File path {} does not exist." + "We need Sutherland's files.".format(finame) ) R = PolynomialRing(QQ, 2, names="XY") X = R.gens()[0] Y = R.gens()[1] res = R(0) with open(finame) as fp: for line in fp: li = line.strip().split(' ') coeff = ZZ(li[1]) expo = ast.literal_eval(li[0]) n = expo[0] m = expo[1] if n == m: res += coeff * X**n * Y**m else: res += coeff * (X**n * Y**m + Y**n * X**m) return res class Necklace(CachedRepresentation): r""" This class represents a necklace of an elliptic curve over Q. """ def __init__(self, E, p, gamma=0, optimise=True): r""" Create a necklace in the p-torsion of an elliptic curve over Q. Input: - E : an elliptic curve over QQ - p : an odd prime such that E has a necklace in E[p] - gamma (optional) : a multiplicative generator of GF(p^2) - optimise (default=True) : boolean Optimise determines if polynomials of splitting fields are simplified. (I am not sure which one is faster.) Limitation: For j=0 and j=1728 no global algorithm is implemented. One can still reduce it but it produces a ReducedCMNecklace. EXAMPLES:: sage: v = Necklace(EllipticCurve("722b1"),3) sage: v.isogeny_field() Number Field in s with defining polynomial x^8 - 12*x^6 + 48*x^4 + 99*x^2 + 36 sage: v.list_of_j_invariants() [11604049627/18944*s^6 - 18968732193/2368*s^4 + 43751799783/1184*s^2 + 390701915505/18944, -11161520979/37888*s^7 + ... - 61779862593/9472, -12270725525/18944*s^6 + ... - 227706286527/4736, 11161520979/37888*s^7 + ... - 61779862593/9472] sage: v.reduction(5) Reduced necklace with j-invariants [2*z^3 + z^2 + 3*z + 3, 3*z^3 + z^2 + z + 1, z^2 + 4*z + 2, 2*z^2 + 2*z + 4] in the 3-torsion of Elliptic Curve defined by y^2 + x*y = x^3 + 4*x^2 + 4*x + 4 over Finite Field of size 5 sage: v.reduction(73) Reduced necklace with j-invariants [13, 57, 33, 45] in the 3-torsion of Elliptic Curve defined by y^2 + x*y = x^3 + 72*x^2 + 72*x + 62 over Finite Field of size 73 """ p = ZZ(p) if p < 3 or not p.is_prime(): raise ValueError("p must be an odd prime.") self._E = E self._p = p if not self._checkifnecklace(): raise ValueError("E contains no necklace defined over Q.") # compute the polynomial in Z[x] whose roots are j(E/C) as C # runs through all pearls Phi = modular_polynomial(p) jE = E.j_invariant() R = PolynomialRing(QQ, "x") x = R.gens()[0] f = Phi(x, jE) f = f.denominator() * f self._f = f verbose(f"integral isogeny polynomial {f}", level=3) # construct the field of def of all p-isogenies, # but take a simplified polynomial to do so if optimise: g = prod(R(ff[0].__pari__().polredbest())**ff[1] for ff in f.factor()) verbose(f"isogeny field is the splitting field of {g}", level=3) K = g.splitting_field("s", degree_multiple=2*(p+1), simplify=True) # simplify_all = True seems really slower else: K = f.splitting_field("s", degree_multiple=2*(p+1), simplify=False) verbose(f"found splitting field of degree {K.degree()}", level=3) self._K = K RK = PolynomialRing(K, "X") fK = RK(f) ro = fK.roots() # check that there are no repeated roots unless # j=0 or 1728, when each root appears "folding" times if E.j_invariant() == 0 and p % 3 == 2: # repeated js expected Aut has 6 elements here folding = ZZ(3) elif E.j_invariant() == 1728 and p % 4 == 3: # same but Aut has 4 elements folding = ZZ(2) else: folding = ZZ(1) assert len(ro) == ZZ((p + 1) / folding) assert ro[0][1] == folding # list of j(E/C) js = [r[0] for r in ro] verbose(f"found all {len(js)} j(E/C) like {js[0]}", level=3) if gamma == 0: gamma = GF(p**2).multiplicative_generator() verbose(f"gamma chosen has minimal polynomial {gamma.minpoly()}", level=3) self._gamma = gamma tt = gamma.trace() nn = gamma.norm() if folding == 1: # find a Frobenius which is gamma or gamma^-1 q = ZZ(2) while True: q = q.next_prime() if E.conductor() % q != 0 and q % p == nn and E.ap(q) % p == tt: qqs = K.primes_above(q) assert len(qqs) == 2 qq = qqs[0] kqq = K.residue_field(qq) jsq = [kqq(j) for j in js] if len(set(jsq)) == len(jsq): break # 3168o3 and p=3 and q=5 has repeated reduced js verbose(f"Frobenius at {q=} has order p+1", level=3) Frobq = kqq.frobenius_endomorphism() j = jsq[0] perm = [0] ne = [js[0]] for i in range(1, p+1): Frj = Frobq(j) ind = jsq.index(Frj) perm.append(ind) ne.append(js[ind]) j = Frj verbose(f" j-invariants were permuted by {perm}", level=3) assert len(set(ne)) == len(ne) else: # j= 0 or 1728, don't calculate anything ne = js verbose(f"not implemented for j=0 and 1728", level=3) self._list_of_js = ne self._list_of_phis = [] # not yet calculated self._folding = folding # remember j=0,1728 def _checkifnecklace(self): r""" Check if the Galois representation of E[p] has image is contained in a normaliser of a non-split Cartan. NON-EXAMPLES:: sage: Necklace(EllipticCurve("675a1"),3) Traceback (most recent call last): ... NotImplementedError: cm with bad reduction at p. sage: Necklace(EllipticCurve("11a1"),3) Traceback (most recent call last): ... ValueError: E contains no necklace defined over Q. """ non_split_str = "normalizer of a non-split Cartan group" E = self._E rho = E.galois_representation() p = self._p if E.has_cm() and E.conductor() % p == 0: # image_type is not implemented raise NotImplementedError("cm with bad reduction at p.") if p > 3 and non_split_str in rho.image_type(p): # might be too naive. return True elif p == 3: f = self._E.division_polynomial(3) ff = f.factor() if len(ff) > 1: if len(ff) == 3: raise NotImplementedError("There is a unique necklace, " + "but the rep is reducible.") else: return False else: G = f.galois_group() if G.order() == 8: if G.is_isomorphic(DihedralGroup(4)): return True else: raise NotImplementedError("Buggg?") elif G.order() in [2, 4]: raise NotImplementedError("There is more than one necklace") else: return False else: return False def list_of_j_invariants(self): r""" Represent the necklace as a list of p+1 j-invariants over the isogeny field EXAMPLE:: sage: v = Necklace(EllipticCurve("36a2"),11) sage: js = v.list_of_j_invariants() sage: len(js) 12 sage: js[0].trace() 19532221320740131303606449458810251733026514535696000 """ if self._folding == 1: return self._list_of_js else: raise NotImplementedError(f"Can't order them for" f"j={self._E.j_invariant()}") def isogeny_field(self): r""" Return the extension of Q over which all isogenies of degree p are defined. EXAMPLES:: sage: E = EllipticCurve('1323p1') sage: v = Necklace(E,3) sage: v.isogeny_field() Number Field in s with defining polynomial x^8 + 2*x^7 - 2*x^6 - 10*x^5 + x^4 + 32*x^3 + 43*x^2 + 35*x + 25 """ if self._folding == 1: return self._K else: raise NotImplementedError(f"Can't work it out for " f"j={self._E.j_invariant()}") def list_of_isogenies(self): r""" Return the list of p+1 isogenies representing the necklace. EXAMPLES:: sage: E = EllipticCurve("722b1") sage: v = Necklace(E,3) sage: isos = v.list_of_isogenies() sage: len(isos) 4 sage: isos[0] Isogeny of degree 3 from Elliptic Curve defined by y^2 + x*y = x^3 + (-1)*x^2 + (-1)*x + (-11) over Number Field in s with defining polynomial x^8 - 12*x^6 + 48*x^4 + 99*x^2 + 36 to Elliptic Curve defined by y^2 + x*y = x^3 + (-1)*x^2 + (1045/111*s^6-4370/37*s^4+21660/37*s^2+12408/37)*x + (9215/111*s^6-350398/333*s^4+512164/111*s^2+320848/111) over Number Field in s with defining polynomial x^8 - 12*x^6 + 48*x^4 + 99*x^2 + 36 sage: E = EllipticCurve('189728cg1') sage: v = Necklace(E,7) sage: isos = v.list_of_isogenies() sage: [phi.degree() for phi in isos] [7, 7, 7, 7, 7, 7, 7, 7] """ if self._folding != 1: raise NotImplementedError(f"Can't work it out for" f" j={self._E.j_invariant()}") # cached if len(self._list_of_phis) > 0: return self._list_of_phis EK = self._E.base_extend(self._K) isos = EK.isogenies_prime_degree(self._p, minimal_models=False) js = self._list_of_js phis = (self._p+1) * [None] # list of Nones for phi in isos: j = phi.codomain().j_invariant() # print("put into ",js.index(j)) phis[js.index(j)] = phi assert None not in phis, "list of phis is "+str(phis) self._list_of_phis = phis return phis def find_splitting_prime(self): r""" Find a prime ell such that the Frobenius at ell acts as a scalar matrix on E[p]. This means that all pearls are F_ell rational. EXAMPLES:: sage: v = Necklace(EllipticCurve("189728cg1"),7) sage: v.find_splitting_prime() 107 sage: v = Necklace(EllipticCurve("36a2"),11) sage: v.find_splitting_prime() 367 """ ell = self._p p = self._p E = self._E ros = [] while len(ros) < (p+1)/self._folding: ell = ell.next_prime() while (E.ap(ell)**2 - 4*ell) % p != 0: ell = ell.next_prime() Rell = PolynomialRing(GF(ell), "T") fell = Rell(self._f) ros = fell.roots() return ell def __key__(self): return self._p, self._E.j_invariant() def __hash__(self): return hash(self.__key__()) def __eq__(self, other): r""" Return if the necklaces are equal. (i.e. they are the same point on X+_nsp(p)(Q) EXAMPLE:: sage: v = Necklace(EllipticCurve("4900u1"),5) sage: v2 = Necklace(EllipticCurve("4489a1"),5) sage: v == v2 False sage: v == v True sage: v2 ==v2 True """ # Silly as we imposed that there is only one necklace, # so we just check if curves and prime are equal if isinstance(other, Necklace): return self.__key__() == other.__key__() return False def __repr__(self): r""" How to print a necklace. """ return f"Necklace in the {self._p}-torsion of {self._E}" def elliptic_curve(self): r""" Return the curve on which this necklace is. """ return self._E def prime_of_necklace(self): r""" Return the prime p such that this is a necklace in E[p] for some elliptic curve. """ return self._p def reduction(self, ell): r""" Reduce the curve and the necklace modulo the prime ell """ if self._folding == 1: return ReducedNecklace(self, ell) else: # can't work with j=0 or 1728 otherwise return ReducedCMNecklace(self._E, self._p, ell) class ReducedNecklace(CachedRepresentation): r""" This class represents the reduction of a necklace over Q in E[p] to a prime ell different from p. """ def __init__(self, v, ell): r""" Create a reduced necklace. Input: - a necklace v over Q - a prime ell The necklace v is in E[p] for an odd prime p. The prime ell must be odd, different from p and E must have good reduction at ell. EXAMPLES:: sage: E = EllipticCurve("32a3") sage: v = Necklace(E,3) sage: v Necklace in the 3-torsion of Elliptic Curve defined by y^2 = x^3 - 11*x - 14 over Rational Field sage: vt = v.reduction(5) sage: vt Reduced necklace with j-invariants [3*z^3 + z^2 + z + 1, 2*z^3 + z^2 + 3*z + 3, 2*z^2 + 2*z + 4, z^2 + 4*z + 2] in the 3-torsion of Elliptic Curve defined by y^2 = x^3 + 4*x + 1 over Finite Field of size 5 sage: phis = vt.list_of_reduced_isogenies() sage: phis[0].degree() 3 sage: vt.isogeny_field().order() 625 """ ell = ZZ(ell) if ell < 3 or not ell.is_prime(): raise ValueError("ell must be an odd prime.") self._ell = ell self._v = v E = v._E p = v._p self._p = p if ell == p: raise ValueError(f"{ell=} must be a prime different from {p=}") # create finite field K = v._K las = K.primes_above(ell) verbose(f"{len(las)} primes above {ell} in K", level=3) # pick one randomly la = las[0] Fla = K.residue_field(la) self._FF = FF = GF(Fla.order(), "z") self._iota = iota = Hom(Fla, FF)[0] # reduce j-invariants jsred = [iota(Fla(j)) for j in v._list_of_js] # check if we have repeated values in the reduced js self._has_rep = ( len(jsred) != len(Set(jsred)) ) self._has_good_red = (E.conductor() % ell != 0) if self._has_good_red: self._Etilde = E.reduction(ell) else: EK = E.base_extend(K) if EK.has_good_reduction(la): self._Etilde = EK.reduction(la).base_extend(iota) self._twisted_E = E else: uu = next(tt for tt in la.gens() if tt.valuation(la) == 1) E_twisted = EK.quadratic_twist(uu) if E_twisted.has_good_reduction(la): self._twisted_E = E_twisted.local_data(la).minimal_model() self._Etilde = E_twisted.reduction(la).base_extend(iota) else: raise NotImplementedError("No good reduction after twisting." "Check!") # to indicate that we have not determined this yet: self._reduced_js = jsred self._prime_ideal = la self._E = E self._global_js = v._list_of_js self._global_phis = v._list_of_phis self._reduced_phis = [] # not yet calculated def __repr__(self): r""" How to print a reduced necklace. EXAMPLES:: sage: E = EllipticCurve("3168o2") sage: v = Necklace(E,3) sage: vt = v.reduction(5); vt Reduced necklace with j-invariants [2*z^3 + 2*z^2 + 2*z + 3, 3*z^3 + 3*z^2 + 3*z + 3, 2*z^3 + 2*z^2 + 2*z + 3, 3*z^3 + 3*z^2 + 3*z + 3] in the 3-torsion of Elliptic Curve defined by y^2 = x^3 + 4*x over Finite Field of size 5 sage: phis = vt.list_of_reduced_isogenies() sage: vt Reduced necklace with j-invariants [2*z^3 + 2*z^2 + 2*z + 3, 3*z^3 + 3*z^2 + 3*z + 3, 2*z^3 + 2*z^2 + 2*z + 3, 3*z^3 + 3*z^2 + 3*z + 3] in the 3-torsion of Elliptic Curve defined by y^2 = x^3 + 4*x over Finite Field of size 5 sage: v.reduction(17) Reduced necklace with j-invariants [10*z^3 + 9*z^2 + z + 2, 13*z^3 + 4*z^2 + 11*z + 7, 5*z^3 + 4*z^2 + 3*z + 15, 6*z^3 + 2*z] in the 3-torsion of Elliptic Curve defined by y^2 = x^3 + 5*x + 4 over Finite Field of size 17 sage: v.reduction(7) Reduced necklace with j-invariants [6, 6, 6, 6] in the 3-torsion of Elliptic Curve defined by y^2 = x^3 + 6*x over Finite Field of size 7 """ res = "Reduced " js_print = self._reduced_js res += f"necklace with j-invariants {js_print} " res += f"in the {self._p}-torsion of {self._Etilde}" return res def __eq__(self, other): r""" Return true if the two reduced necklaces are equal. They are considered equal even if the chosen gamma is different EXAMPLES:: sage: v1 = Necklace(EllipticCurve("4900u1"),5) sage: v2 = Necklace(EllipticCurve("4489a1"),5) sage: v2l = v2.reduction(28571) sage: v1l = v1.reduction(28571) sage: v1l == v2l False sage: v1l Reduced necklace with j-invariants [20351, 25037, 8325, 16645, 24894, 4370] in the 5-torsion of Elliptic Curve defined by y^2 = x^3 + x^2 + 14255*x + 12673 over Finite Field of size 28571 sage: v2l Reduced necklace with j-invariants [16645, 24894, 8325, 25037, 4370, 20351] in the 5-torsion of Elliptic Curve defined by y^2 + y = x^3 + 21201*x + 14960 over Finite Field of size 28571 sage: E1 = EllipticCurve("352f1"); E2 = EllipticCurve("4107b1") sage: v1 = Necklace(E1,3); v2 = Necklace(E2,3) sage: v1t = v1.reduction(7); v2t = v2.reduction(7) sage: v1t == v2t True sage: v1t.list_of_pearls() [x + 4*z + 4, x + 3*z + 1, x + 4*z + 6, x + 3*z + 3] sage: v2t.list_of_pearls() [x + 5*z + 3, x + 5*z + 5, x + 2*z + 1, x + 2*z + 3] # example with bad reduction at ell sage: E = EllipticCurve("49a1") sage: v = Necklace(E,3) sage: vt = v.reduction(7) sage: vc = ReducedCMNecklace(E,3,7) sage: vc == vt True """ if not isinstance(other, ReducedNecklace) and \ not isinstance(other, ReducedCMNecklace): return False ell = self._ell if other._ell != ell: return False if other._p != self._p: return False E = self._Etilde E2 = other._Etilde if E.j_invariant() != E2.j_invariant(): verbose(f"j-invariants are distinct : " f"{self._Etilde.j_invariant()} and " f"{other._Etilde.j_invariant()}") return False FF = self._FF FF2 = other._FF if FF != FF2: verbose(f"isogeny fields are not equal of sizes: " f"{FF.order()} and " f"{FF2.order()}") return False if not self._has_rep: ne = self._reduced_js ne2 = other._reduced_js return _are_two_lists_of_js_the_same_necklace(ne, ne2) fs = self.list_of_pearls() fs2 = other.list_of_pearls() E = E.base_extend(FF) E2 = E2.base_extend(FF) # if there are extra automorphism, we need to apply it boo1 = _are_two_lists_of_pearls_the_same_necklace(E, E2, fs, fs2) au = E2.automorphisms() if len(au) == 2: return boo1 R = PolynomialRing(FF, "x") x = R.gens()[0] if len(au) == 6: alpha = next(alpha for alpha in au if alpha.order() == 3) fs2alpha = [f.subs(alpha.u**2 * x + alpha.r) for f in fs2] boo2 = _are_two_lists_of_pearls_the_same_necklace(E, E2, fs, fs2alpha) fs2asq = [f.subs(alpha.u**2 * x + alpha.r) for f in fs2alpha] boo3 = _are_two_lists_of_pearls_the_same_necklace(E, E2, fs, fs2asq) return boo1 or boo2 or boo3 else: # len(au) == 4: alpha = next(alpha for alpha in au if alpha.order() == 4) fs2alpha = [f.subs(alpha.u**2 * x + alpha.r) for f in fs2] boo2 = _are_two_lists_of_pearls_the_same_necklace(E, E2, fs, fs2alpha) return boo1 or boo2 def list_of_j_invariants(self): r""" Represent the necklace as a list of p+1 j-invariants over the isogeny field of the reduced curve. EXAMPLES:: sage: v = Necklace(EllipticCurve("189728cg1"), 7) sage: vt = v.reduction(5) sage: vt.list_of_j_invariants() [0, 0, 0, 0, 0, 0, 0, 0] sage: vt = v.reduction(13) sage: vt.list_of_j_invariants() [10*z^7 + 10*z^6 + 9*z^5 + 12*z^4 + 7*z^2 + 5*z, 5*z^7 + 4*z^6 + 8*z^5 + 8*z^4 + 11*z^3 + 4*z^2 + 3*z + 8, 5*z^7 + 8*z^6 + 4*z^5 + 6*z^4 + 4*z^3 + 5*z^2 + 9*z + 2, 2*z^7 + 6*z^6 + 3*z^5 + 8*z^3 + 11*z^2 + 7*z + 10, 11*z^7 + 11*z^6 + 5*z^5 + 8*z^4 + 5*z^3 + 4*z^2 + 6*z + 2, 8*z^7 + 2*z^6 + 8*z^5 + 2*z^4 + 3*z^3 + z^2 + 11*z + 10, 5*z^7 + 9*z^6 + z^5 + 2*z^4 + 10*z^3 + 12*z^2 + 4*z + 4, 6*z^7 + 2*z^6 + z^5 + z^4 + 11*z^3 + 8*z^2 + 7*z + 10] """ return self._reduced_js def list_of_reduced_isogenies(self): r""" Return the list of p+1 isogenies defined on the reduced curve representing the necklace. EXAMPLE:: sage: E = EllipticCurve("4900j1") sage: v = Necklace(E,5) sage: vt = v.reduction(19) sage: vt.list_of_reduced_isogenies() [Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 18*x^2 + 11*x + 14 over Finite Field in z of size 19^2 to Elliptic Curve defined by y^2 = x^3 + (9*z+4)*x over Finite Field in z of size 19^2, ... Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 18*x^2 + 11*x + 14 over Finite Field in z of size 19^2 to Elliptic Curve defined by y^2 = x^3 + 9*x over Finite Field in z of size 19^2] """ if len(self._reduced_phis) > 0: return self._reduced_phis if self._has_good_red or self._twisted_E == self._E: phis = self._v.list_of_isogenies() else: # need to create isogenies globally on twisted curve Et = self._twisted_E isogs = Et.isogenies_prime_degree(self._p, minimal_models=False) js = self._global_js phis = (self._p+1) * [None] for phi in isogs: j = phi.codomain().j_invariant() phis[js.index(j)] = phi assert None not in phis, "list of phis is "+str(phis) la = self._prime_ideal p = self._p re_isos = [reduce_an_isogeny_modulo_a_prime_ideal(phi, la) for phi in phis] verbose(f"poly after reducing at {la=} are " f"{[phi.kernel_polynomial() for phi in re_isos]}", level=3) re_isos = [isogeny_change_base(phi, self._iota) for phi in re_isos] verbose(f"polys after {self._iota=} are " f"{[phi.kernel_polynomial() for phi in re_isos]}", level=3) self._reduced_phis = re_isos return self._reduced_phis def isogeny_field(self): r""" Return the extension of F_{ell} over which all isogenies of degree p are defined. EXAMPLES:: sage: v = Necklace(EllipticCurve("36a2"),11) sage: vt = v.reduction(5) sage: vt.isogeny_field().cardinality() 25 sage: v = Necklace(EllipticCurve("189728cg1"),7) sage: vt = v.reduction(101) sage: vt.isogeny_field().cardinality().factor() 101^8 """ return self._FF def list_of_pearls(self): r""" Return the necklace as a list of polynomials defining the cyclic subgroups of order p in E EXAMPLES:: sage: v = Necklace(EllipticCurve("49a1"),3).reduction(13) sage: v.list_of_pearls() [x + 8*z + 3, x + 5*z + 11, x + 12*z + 6, x + z + 5] sage: v = Necklace(EllipticCurve("32a2"),7).reduction(11) sage: v.list_of_pearls() # random order [x^3 + (9*z + 8)*x^2 + (4*z + 1)*x + 10*z + 1, ... x^3 + (6*z + 9)*x^2 + (5*z + 2)*x + 4*z + 10] sage: v = Necklace(EllipticCurve("121b1"),7).reduction(23) sage: v.list_of_pearls() [x^3 + (15*z^3 + 15*z^2 + 21*z + 15)*x^2 + (9*z^3 + 4*z + 22)*x + 11*z^3 + 13*z^2 + 7*z + 2, ... x^3 + (6*z^3 + 20*z^2 + 12*z + 7)*x^2 + (12*z^3 + 8*z^2 + 14*z + 1)*x + 22*z^3 + 21*z^2 + 19] """ phis = self.list_of_reduced_isogenies() return [f.kernel_polynomial() for f in phis] def elliptic_curve(self): r""" Return the curve defined over F_{ell} on which this necklace is. """ return self._Etilde class ReducedCMNecklace(CachedRepresentation): r""" Class used to create a reduced necklace directly for a cm curve without having to do any global calculations """ def __init__(self, E, p, ell, gamma=0): """ Return the gamma-necklace on E in E[p] reduced modulo ell without calculating any global stuff. Input: E - an elliptic curve over Q with cm p, ell - two distinct primes Output: A list of isogenies on the reduced curve. EXAMPLES:: sage: vt = ReducedCMNecklace(EllipticCurve("121b1"),29,5) sage: vt.isogeny_field().cardinality().factor() 5^5 sage: phi = vt.list_of_reduced_isogenies()[1] sage: phi.degree() 29 sage: js = vt.list_of_j_invariants() sage: js[-1].minpoly() x^5 + ... + 3 sage: vt = ReducedCMNecklace(EllipticCurve("27a3"),11,5) sage: vt Reduced necklace with reduced j-invariants [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] in the 11-torsion of Elliptic Curve defined by y^2 + y = x^3 over Finite Field of size 5 sage: phis = vt.list_of_reduced_isogenies() sage: phis[0] Isogeny of degree 11 from Elliptic Curve defined by y^2 + y = x^3 over Finite Field in z of size 5^2 to Elliptic Curve defined by y^2 + y = x^3 over Finite Field in z of size 5^2 """ # checks p = ZZ(p) ell = ZZ(ell) if p < 3 or not p.is_prime(): raise ValueError(f"{p=} must be an odd prime.") self._p = p if not ell.is_prime or ell == p: raise ValueError(f"{ell=} must be a prime distinct from {p=}.") self._ell = ell if not E.has_cm(): raise ValueError(f"The curve must have complex multiplication.") # if not E.has_good_reduction(ell): # raise NotImplementedError("bad reduction for cm curves is not yet implemented") D = E.cm_discriminant() if kronecker(D, p) != -1: raise ValueError(f"The {p=} is not inert in the endomorphism ring of the curve.") if gamma == 0: gamma = GF(p**2).multiplicative_generator() verbose(f"gamma chosen has minimal polynomial {gamma.minpoly()}", level=3) tt = gamma.trace() nn = gamma.norm() verbose(f"{tt=} and {nn=}, {D=}") da = cm_data(E.j_invariant()) F = NumberField(da[0], "s") la = F.prime_above(ell) EF = E.base_extend(F) j = E.j_invariant() if E.conductor() % ell == 0 and j != 0 and j != 1728: # we can do a quadratic twist over F to achieve good reduction twist_d = 2*F.gens()[0]-1 # =sqrt(-d) Etwisted = EF.quadratic_twist(twist_d) EF = Etwisted.local_data(la).minimal_model() assert EF.has_good_reduction(la) iota1 = Hom(la.residue_field(), GF(ell))[0] self._Etilde = EF.reduction(la).base_extend(iota1) self._bad_reduction = True else: self._Etilde = E.reduction(ell) self._bad_reduction = False # this creates a basis of the # endomorphism ring psi = self._get_an_endo(da[3], EF) # psi corresponds to a + b * F.0 : a, b = list(psi.scaling_factor()) a = ZZ(a) b = ZZ(b) verbose(f" {a=}, {b=}, {psi=}") # to create an endomorphism rho # which generated End(EF)/p # rho = u + v * F.0 c = ZZ(da[2]) # conductor of order u = self._get_a_gamma(tt, nn, a, b, c, F) verbose(f"{u=}") # this is an endomorphism that acts on E[p] as gamma rho = u + psi verbose(f"{rho.scaling_factor()=} min poly : {rho.scaling_factor().minpoly()}") # reduce it modulo ell rhola = reduce_an_isogeny_modulo_a_prime_ideal(rho, la) verbose(f"{la}, {rhola.scaling_factor()=}" f"has min poly {rhola.scaling_factor().minpoly()}") Ekk = rhola.domain() T = self._get_torsion_pt(Ekk) ET = T.curve() FT = ET.base_field() # change field of def of rhola rholaT = isogeny_change_base(rhola, FT) verbose(f"{rholaT.scaling_factor()=} " f"has min poly {rholaT.scaling_factor().minpoly()}", level=3) # build necklace nek = [] i = 0 Q = T md = ZZ(-1) while i < p+1: verbose(f"{Q=}, ={T.weil_pairing(Q, p)}", level=3) phiT = ET.isogeny(Q, degree=p) f = phiT.kernel_polynomial() nek.append(f) mdf = max(aa.minpoly().degree() for aa in list(f)) md = max(md, mdf) Q = rholaT(Q) i += 1 assert Q.order() == p # assert T.weil_pairing(Q,p) != 1 or i % self._reduced_length == 0 verbose(f" degree {md} and polynomials {nek}", level=3) assert T.weil_pairing(Q, p) == 1 FF = self._FF = GF(ell**md, "z") # isogeny field verbose(f"{FF=}, {FT=}", level=3) iota = Hom(FF, FT)[0] # redefine the isogenies over this field EFF = self._Etilde.base_extend(FF) ne = [] RFv = PolynomialRing(FF, "x") for f in nek: fFv = RFv([iota.inverse_image(aa) for aa in list(f)]) verbose(f" Turned {f} into {fFv} ", level=3) ne.append(EFF.isogeny(kernel=fFv, degree=p)) self._reduced_js = [phi.codomain().j_invariant() for phi in ne] self._FF = FF self._E = E self._reduced_phis = ne def _get_an_endo(self, qs, EF): """ return an endomorphism psi such that 1 and psi generate End(EF) We want to avoid that ell divides its degree """ if EF.j_invariant() == 0 or EF.j_invariant() == 1728: # case with extra endos. autos = EF.automorphisms() F = base_field(EF) s = F.gens()[0] psi = next(psi for psi in autos if psi.scaling_factor() == s) else: q = next(q for q in qs if q % self._ell != 0) isogs = EF.isogenies_prime_degree(q, minimal_models=False) f = next(psi.kernel_polynomial() for psi in isogs if psi.codomain().is_isomorphic(EF)) psi = EF.isogeny(f, codomain=EF, degree=q) return psi def _get_a_gamma(self, tt, nn, a, b, c, F): """ return u,v such that u+v*psi acts as an element of order p+1 associated to gamma """ verbose(f"enter get gamma with {tt=}, {nn=}, {a=}, {b=}, {c=}", level=3) p = self._p Fp = F.residue_field(p) Rp = PolynomialRing(Fp, "X") X = Rp.gens()[0] gammas = (X**2 - tt*X + nn).roots() ga = gammas[0][0] ga0, ga1 = list(ga) verbose(f" gamma is ({ga0},{ga1})") x = ga0.lift() y = ga1.lift() assert y % p != 0 z = y.inverse_mod(p) u = (z*b*x-a) % p # old code # shortestvec, secondvec = _find_shortest_vec([p, ZZ(0)], [xx, ZZ(1)]) # verbose(f" {shortestvec=}, {secondvec=}, input: {(xx, 1)}") # u = shortestvec[0] # v = shortestvec[1] return u def _get_torsion_pt(self, Et): """ return a p-torsion point on Et over a finite extension containing all of them """ FF = Et.division_field(self._p) EFF = Et.base_extend(FF) P, _ = EFF.torsion_basis(self._p) return P def __repr__(self): res = "Reduced necklace with reduced j-invariants " res += f"{self._reduced_js} in the " res += f"{self._p}-torsion of {self._Etilde}" return res def __eq__(self, other): r""" Return true if the two reduced necklaces are equal. They are considered equal even if the chosen gamma is different EXAMPLES:: sage: vt = ReducedCMNecklace(EllipticCurve("27a3"),11,5) sage: vt2 = ReducedCMNecklace(EllipticCurve("27a4"),11,5) sage: vt == vt2 False sage: v1 = ReducedCMNecklace(EllipticCurve("4489a1"),7,13) sage: v2 = ReducedCMNecklace(EllipticCurve("26569a1"),7,13) sage: v1 == v2 True """ if isinstance(other, ReducedNecklace): return other == self if not isinstance(other, ReducedCMNecklace): return False ell = self._ell if other._ell != ell: return False if other._p != self._p: return False E = self._Etilde E2 = other._Etilde if E.j_invariant() != E2.j_invariant(): return False FF = self._FF FF2 = other._FF if FF != FF2: return False E = E.base_extend(FF) E2 = E2.base_extend(FF) fs = self.list_of_pearls() fs2 = other.list_of_pearls() boo1 = _are_two_lists_of_pearls_the_same_necklace(E, E2, fs, fs2) au = E2.automorphisms() if len(au) == 2: return boo1 R = PolynomialRing(FF, "x") x = R.gens()[0] # if there are extra automorphism, we need to apply it if len(au) == 6: alpha = next(alpha for alpha in au if alpha.order() == 3) fs2alpha = [f.subs(alpha.u**2 * x + alpha.r) for f in fs2] boo2 = _are_two_lists_of_pearls_the_same_necklace(E, E2, fs, fs2alpha) fs2asq = [f.subs(alpha.u ** 2 * x + alpha.r) for f in fs2alpha] boo3 = _are_two_lists_of_pearls_the_same_necklace(E, E2, fs, fs2asq) return boo1 or boo2 or boo3 else: # len(au) == 4: alpha = next(alpha for alpha in au if alpha.order() == 4) fs2alpha = [f.subs(alpha.u ** 2 * x + alpha.r) for f in fs2] boo2 = _are_two_lists_of_pearls_the_same_necklace(E, E2, fs, fs2alpha) return boo1 or boo2 def list_of_j_invariants(self): r""" Represent the necklace as a list of p+1 j-invariants over the isogeny field of the reduced curve. EXAMPLES:: sage: vt = ReducedCMNecklace(EllipticCurve("27a3"),11,5) sage: vt.list_of_j_invariants() [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] sage: vt = ReducedCMNecklace(EllipticCurve("121b1"),13,5) sage: [jj.norm() for jj in vt.list_of_j_invariants()] [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4] """ return self._reduced_js def list_of_reduced_isogenies(self): r""" Return the list of p+1 isogenies defined on the reduced curve representing the necklace. EXAMPLE:: sage: vt = ReducedCMNecklace(EllipticCurve("121b1"),13,5) sage: vt.list_of_reduced_isogenies()[0] Isogeny of degree 13 from Elliptic Curve defined by y^2 + y = x^3 + 4*x^2 + 3*x over Finite Field in z of size 5^14 to Elliptic Curve ... sage: vt = ReducedCMNecklace(EllipticCurve("27a3"),11,101) sage: phi = vt.list_of_reduced_isogenies()[0] sage: phi.codomain() Elliptic Curve defined by y^2 ... Finite Field in z of size 101^2 sage: phi.degree() 11 """ return self._reduced_phis def isogeny_field(self): r""" Return the extension of F_{ell} over which all isogenies of degree p are defined. EXAMPLES:: sage: vt = ReducedCMNecklace(EllipticCurve("27a3"),11,5) sage: vt.isogeny_field().cardinality().factor() 5^2 sage: vt2 = ReducedCMNecklace(EllipticCurve("27a4"),11,5) sage: vt.isogeny_field().cardinality().factor() 5^2 sage: vt3 = ReducedCMNecklace(EllipticCurve("121b1"),13,109) sage: vt3.isogeny_field().cardinality().factor() 109^2 """ return self._FF def list_of_pearls(self): r""" Return the necklace as a list of polynomials defining the cyclic subgroups of order p in E EXAMPLES:: sage: v = ReducedCMNecklace(EllipticCurve("49a1"),3,13) sage: v.list_of_pearls() # random order [x + 5*z + 11, x + 8*z + 3, x + z + 5, x + 12*z + 6] sage: v = ReducedCMNecklace(EllipticCurve("121b1"),7,23) sage: v.list_of_pearls() # random order [x^3 + (10*z^3 + 11*z^2 + 22*z + 1)*x^2 + (14*z^3 + 9*z^2 + 9*z + 9)*x + 6*z^3 + 5*z^2 + 18*z + 5, ... x^3 + (6*z^3 + 20*z^2 + 12*z + 7)*x^2 + (12*z^3 + 8*z^2 + 14*z + 1)*x + 22*z^3 + 21*z^2 + 19] sage: v = ReducedCMNecklace(EllipticCurve("32a2"),7,11) sage: v.list_of_pearls() # random order [x^3 + 9*z*x^2 + (7*z + 6)*x + 10*z + 3, x^3 + 6*z*x^2 + 6*z*x + 4*z + 7, x^3 + (5*z + 2)*x^2 + (5*z + 2)*x + 7*z + 1, x^3 + (2*z + 3)*x^2 + (4*z + 1)*x + z + 10, x^3 + 2*z*x^2 + (7*z + 6)*x + z + 8, x^3 + 5*z*x^2 + 6*z*x + 7*z + 4, x^3 + (6*z + 9)*x^2 + (5*z + 2)*x + 4*z + 10, x^3 + (9*z + 8)*x^2 + (4*z + 1)*x + 10*z + 1] """ phis = self.list_of_reduced_isogenies() return [f.kernel_polynomial() for f in phis] def elliptic_curve(self): r""" Return the curve defined over F_{ell} on which this necklace is. """ return self._Etilde def _are_two_lists_of_pearls_the_same_necklace(E, E2, fs, fs2): r""" Return true if the two necklaces are equal using kernel polynomials. """ verbose(f"Enter == via isog with {fs=}, {fs2=}", level=3) p = fs[0].degree() * 2 + 1 # common finite field FF = E.base_field() FF2 = E2.base_field() if FF != FF2: verbose(f"not equal isogeny fields {FF}, {FF2}", level=3) return False R2 = PolynomialRing(FF, "x") x = R2.gens()[0] i = E2.isomorphism_to(E) k1 = fs k2 = [f.subs(i.u**2 * x + i.r) for f in fs2] k2 = [f/f.leading_coefficient() for f in k2] verbose(f"kernel polys to compare : {k1} vs {k2}", level=3) if k1[0] not in k2: verbose(f"different as {k1[0]} in {k1=} does not appear in {k2=}", level=3) return False i = k2.index(k1[0]) if k1[1] not in k2: verbose(f"different as {k1[1]} in {k1=} does not appear in {k2=}", level=3) return False j = k2.index(k1[1]) # this is the power of gamma that is used in ne2 n = (j-i) % (p+1) if gcd(n, p+1) != 1: verbose(f"different as power of gamma {n} must be invertible mod {p+1=}", level=3) return False for k in srange(2, p+1): if k2[(n*k+i) % (p+1)] != k1[k]: verbose(f"different as entry {k2[(n*k+i)%(p+1)]} at " f"{(n*k+i)%(p+1)} in {k2=} is not entry {k1[k]} at {k} om {k1=}", level=3) return False return True def _are_two_lists_of_js_the_same_necklace(ne, ne2): r""" Return true if two lists of j are equal. """ # Compare two lists of elements in a finite field to see if # they are equal necklaces for possible two distinct gamma. # they are equal if there is n and i such that # b[n*k+i mod p+1] = a[k] for all k if len(ne) != len(ne2): verbose(f"distinct as of different lengths {ne=}, {ne2}", level=3) return False lengths = len(ne) if ne[0] not in ne2: verbose(f"different as {ne[0]} from {ne=} is not in {ne2=}", level=3) return False i = ne2.index(ne[0]) if ne[1] not in ne2: verbose(f"different as {ne[1]} from {ne=} is not in {ne2=}", level=3) return False j = ne2.index(ne[1]) # this is the power of gamma that is used in ne2 n = (j-i) % lengths if gcd(n, lengths) != 1: return False for k in srange(2, lengths): if ne2[(n*k+i) % lengths] != ne[k]: verbose(f"different as entry {ne2[(n*k+i) % lengths]} at " f"{(n*k+i) % lengths} in {ne2=} is different from entry " f"{ne[k]} at {k} in {ne=}", level=3) return False return True def reduce_an_isogeny_modulo_a_prime_ideal(phi, pp): r""" Return an isogeny between curves over the reduction. Input: - phi an isogeny between elliptic curves defined over a number field - pp a prime ideal in this number field EXAMPLES:: sage: E = EllipticCurve("9756c1") sage: v = Necklace(E,5) sage: K = v.isogeny_field() sage: EK = E.base_extend(K) sage: phi = EK.isogenies_prime_degree(5)[0] sage: pp = K.prime_above(7) sage: reduce_an_isogeny_modulo_a_prime_ideal(phi,pp) Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 6*x + 5 over Residue field in sbar of Fractional ideal (7, ...) to Elliptic Curve defined by y^2 + y = x^3 + ... + 2 over Residue field in sbar of Fractional ideal (7, ...) sage: L. = QuadraticField(-7) sage: EL = EllipticCurve(L,[1,-1,0,-2,-1]) sage: phi = EL.isogenies_prime_degree(7)[0] sage: reduce_an_isogeny_modulo_a_prime_ideal(phi,L.ideal(13)) Isogeny of degree 7 from Elliptic Curve defined by y^2 + x*y = x^3 + 12*x^2 + 11*x + 12 over Residue field in sbar of Fractional ideal (13) to Elliptic Curve defined by y^2 + x*y = x^3 + 12*x^2 + 11*x + 12 over Residue field in sbar of Fractional ideal (13) sage: 2+phi Sum morphism: From: Elliptic Curve defined by y^2 + x*y = x^3 + (-1)*x^2 + (-2)*x + (-1) over Number Field in s with defining polynomial x^2 + 7 with s = 2.645751311064591?*I To: Elliptic Curve defined by y^2 + x*y = x^3 + (-1)*x^2 + (-2)*x + (-1) over Number Field in s with defining polynomial x^2 + 7 with s = 2.645751311064591?*I Via: (Scalar-multiplication endomorphism [2] of Elliptic Curve defined by y^2 + x*y = x^3 + (-1)*x^2 + (-2)*x + (-1) over Number Field in s with defining polynomial x^2 + 7 with s = 2.645751311064591?*I, Isogeny of degree 7 from Elliptic Curve defined by y^2 + x*y = x^3 + (-1)*x^2 + (-2)*x + (-1) over Number Field in s with defining polynomial x^2 + 7 with s = 2.645751311064591?*I to Elliptic Curve defined by y^2 + x*y = x^3 + (-1)*x^2 + (-2)*x + (-1) over Number Field in s with defining polynomial x^2 + 7 with s = 2.645751311064591?*I) sage: reduce_an_isogeny_modulo_a_prime_ideal(2+phi,L.ideal(13)) Sum morphism: From: Elliptic Curve defined by y^2 + x*y = x^3 + 12*x^2 + 11*x + 12 over Residue field in sbar of Fractional ideal (13) To: Elliptic Curve defined by y^2 + x*y = x^3 + 12*x^2 + 11*x + 12 over Residue field in sbar of Fractional ideal (13) Via: (Scalar-multiplication endomorphism [2] of Elliptic Curve defined by y^2 + x*y = x^3 + 12*x^2 + 11*x + 12 over Residue field in sbar of Fractional ideal (13), Isogeny of degree 7 from Elliptic Curve defined by y^2 + x*y = x^3 + 12*x^2 + 11*x + 12 over Residue field in sbar of Fractional ideal (13) to Elliptic Curve defined by y^2 + x*y = x^3 + 12*x^2 + 11*x + 12 over Residue field in sbar of Fractional ideal (13)) """ if isinstance(phi, EllipticCurveHom_sum): return _reduce_sum_isogeny(phi, pp) if isinstance(phi, EllipticCurveHom_composite): return _reduce_composite_isogeny(phi, pp) if isinstance(phi, EllipticCurveHom_scalar): return _reduce_scalar_isogeny(phi, pp) if isinstance(phi, WeierstrassIsomorphism): return _reduce_automorphis(phi, pp) verbose(f" Start reducing {phi=} modulo {pp=}") E1 = phi.domain() E2 = phi.codomain() K = E1.base_ring() assert K == pp.number_field() FFpp = pp.residue_field() # iota = FFpp.coerce_map_from(K.ring_of_integers()) f = phi.kernel_polynomial() d = phi.degree() E1t = E1.reduction(pp) E2t = E2.reduction(pp) Rqq = PolynomialRing(FFpp, "x") ft = Rqq(f) phit = E1t.isogeny(codomain=E2t, degree=d, kernel=ft) sc = FFpp(phi.scaling_factor()) sct = phit.scaling_factor() if sc == sct: return phit elif sc == - sct: return -phit # now assume E2t = E1t and degree of phi # is a nice prime assert E1t == E2t Et = E1t assert d.is_prime() someisogs = Et.isogenies_prime_degree(d) kers = [a.kernel_polynomial() for a in someisogs if a.codomain().is_isomorphic(Et)] someendos = [Et.isogeny(codomain=Et, kernel=f, degree=d) for f in kers] autos = Et.automorphisms() allisogs = flatten([[a*b for a in someendos] for b in autos]) # print(Et, someisogs, autos, allisogs) # this may fail at times to give one phit = next(a for a in allisogs if a.scaling_factor() == sc and a.kernel_polynomial() == ft) return phit def _reduce_scalar_isogeny(phi, pp): """ case when phi is [m] """ m = phi._m E = phi.domain() Et = E.reduction(pp) return EllipticCurveHom_scalar(Et, m) def _reduce_automorphis(phi, pp): """ case when phi is an automorphism """ E = phi.domain() u = phi.tuple() Et = E.reduction(pp) Ft = Et.base_field() ut = [Ft(uu) for uu in u] return WeierstrassIsomorphism(Et, ut) def _reduce_sum_isogeny(phi, pp): """ case when phi is a sum of endomorphisms """ phis = phi._phis phist = [reduce_an_isogeny_modulo_a_prime_ideal(psi, pp) for psi in phis] return EllipticCurveHom_sum(phist) def _reduce_composite_isogeny(phi, pp): """ case when phi is a composite of two isogenies """ phis = phi._phis phist = [reduce_an_isogeny_modulo_a_prime_ideal(psi, pp) for psi in phis] return EllipticCurveHom_composite.from_factors(phist) def isogeny_change_base(phi, L): r""" Return the isogeny phi, but on the corresponding curves defined over L. This allows for phi(P) for P in E(L). """ if isinstance(phi, EllipticCurveHom_sum): return _isogeny_change_base_sum(phi, L) if isinstance(phi, EllipticCurveHom_composite): return _isogeny_base_change_composite(phi, L) if isinstance(phi, EllipticCurveHom_scalar): return _isogeny_base_change_scalar(phi, L) if isinstance(phi, WeierstrassIsomorphism): return _automorphism_base_change(phi, L) if isinstance(L, RingHomomorphism): iota = L L = iota.codomain() K = iota.domain() assert phi.domain().base_field() == K else: # if isinstance(L, FiniteField_givaro_with_category): K = phi.domain().base_field() iota = Hom(K, L)[0] # in the remaining cases the kernel polynomial should # be available verbose(f"Enter base change to {L=} for isogeny {phi=}") f = phi.kernel_polynomial() RL = PolynomialRing(L, "X") fL = RL([iota(a) for a in list(f)]) E1 = phi.domain() E2 = phi.codomain() d = phi.degree() E1L = E1.base_extend(iota) E2L = E2.base_extend(iota) phiL = E1L.isogeny(kernel=fL, codomain=E2L, degree=d) sc = iota(phi.scaling_factor()) scL = phiL.scaling_factor() # print(sc,scL) if sc == scL: return phiL elif sc == -scL: return -phiL # now the code that only works for some assert d.is_prime() someisogs = E1L.isogenies_prime_degree(d) kers = [a.kernel_polynomial() for a in someisogs if a.codomain().is_isomorphic(E2L)] someendos = [E1L.isogeny(codomain=E2L, kernel=ff, degree=d) for ff in kers] autos = E1L.automorphisms() allisogs = flatten([[a*b for a in someendos] for b in autos]) # print(E1L, E2L, someisogs, autos, allisogs) # print([a.scaling_factor() for a in allisogs]) # print([a.kernel_polynomial() for a in allisogs]) # this may fail at times to give one phiL = next(a for a in allisogs if a.scaling_factor() == sc and RL(a.kernel_polynomial()) == fL) return phiL def _automorphism_base_change(phi, L): """ Case then phi is an automorphism """ E = phi.domain() u = phi.tuple() EL = E.base_extend(L) uL = [L(uu) for uu in u] return WeierstrassIsomorphism(EL, uL) def _isogeny_base_change_scalar(phi, L): """ Case when phi is [m] """ E = phi.domain() EL = E.base_extend(L) m = phi._m return EllipticCurveHom_scalar(EL, m) def _isogeny_base_change_composite(phi, L): """ Case when phi is a composition of isogenies """ phis = phi._phis phisL = [isogeny_change_base(psi, L) for psi in phis] return EllipticCurveHom_composite.from_factors(phisL) def _isogeny_change_base_sum(phi, L): """ case when phi is a sum of endomorphisms """ phis = phi._phis phisL = [isogeny_change_base(psi, L) for psi in phis] return EllipticCurveHom_sum(phisL) def cm_data(j): r""" For each j-invariant of a cm elliptic curve over Q, this returns a list [h,d,c,qs] such that h : a poly such that O_F is Z[X]/(h) d : F is sqrt(d) and d is squarefree c : End(E) is Z + c. O_F q : a list of primes such that there is an endomorphism of degree q """ V = PolynomialRing(QQ, "X") X = V.gens()[0] cm_data = dict( [[0, [X**2 - X + 1, -3, 1, [3, 7, 13]]], [-12288000, [X**2 - X + 1, -3, 3, [7, 13, 19]]], [1728, [X**2 + 1, -1, 1, [2, 5, 13]]], [287496, [X**2 + 1, -1, 2, [5, 13, 17]]], [54000, [X**2 - X + 1, -3, 2, [3, 7, 13]]], [-3375, [X**2 - X + 2, -7, 1, [2, 7, 11]]], [16581375, [X**2 - X + 2, -7, 2, [7, 11, 23]]], [-32768, [X**2 - X + 3, -11, 1, [3, 5, 11]]], [8000, [X**2 + 2, -2, 1, [2, 3, 11]]], [-884736, [X**2 - X + 5, -19, 1, [5, 7, 11]]], [-884736000, [X**2 - X + 11, -43, 1, [11, 13, 17]]], [-147197952000, [X**2 - X + 17, -67, 1, [17, 19, 23]]], [-262537412640768000, [X**2 - X + 41, -163, 1, [41, 43, 47]]]] ) return cm_data[j] def _find_shortest_vec(avec, bvec): r""" Return shortest vector in lattice spanned by avec and bvec Cohen 1.3.14 Also return a second vector such they form a basis """ verbose(f" find shortest vector in lattice generated" + f" by {avec} and {bvec}", level=3) A = avec[0]**2 + avec[1]**2 B = bvec[0]**2 + bvec[1]**2 if A < B: avec, bvec = bvec, avec A, B = B, A while A > B: verbose(f"{A=}, {B=}, {avec=}, {bvec=}") n = avec[0]*bvec[0] + avec[1]*bvec[1] verbose(f"{n=}, {n/B}, {round(n/B)}, {A=}, {B=}, {avec=}, {bvec=}", level=3) r = (ZZ(n)/B).round(mode="even") T = A - 2*r*n + r**2*B tvec = [avec[0] - r*bvec[0], avec[1] - r*bvec[1]] avec, bvec, A, B = bvec, tvec, B, T return avec, bvec