Created
March 10, 2017 14:59
-
-
Save defeo/d76b969ad27c8acf59245256d6c842bc to your computer and use it in GitHub Desktop.
Old code for supporting non-normalized isogenies in Sage
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # HG changeset patch | |
| # User Luca De Feo <luca.defeo@polytechnique.edu> | |
| # Date 1309987774 14400 | |
| # Node ID c1ea68aa11f5be87be8503894782b7e86d0fc25b | |
| # Parent 308b228f1089ab3ae54b36d7838697e1454d8497 | |
| Non normalized isogenies. | |
| diff -r 308b228f1089 -r c1ea68aa11f5 sage/schemes/elliptic_curves/ell_curve_isogeny.py | |
| --- a/sage/schemes/elliptic_curves/ell_curve_isogeny.py Thu Apr 28 17:00:51 2011 +0200 | |
| +++ b/sage/schemes/elliptic_curves/ell_curve_isogeny.py Wed Jul 06 17:29:34 2011 -0400 | |
| @@ -86,6 +86,8 @@ | |
| from sage.schemes.elliptic_curves import ell_isogeny_char_zero | |
| +from sage.databases.db_modular_polynomials import AtkinModularPolynomialDatabase | |
| + | |
| # | |
| # Private function for parsing input to determine the type of | |
| # algorithm | |
| @@ -511,6 +513,18 @@ | |
| rationals, then the codomain is set to be the unique global | |
| minimum model. | |
| + - ``normalized`` - a boolean or an element of the base field (default:``True``). | |
| + This parameter is only considered when the codomain parameter | |
| + is not ``None``. If an element `u` of the base field is | |
| + given, then the isogeny `\varphi` between ``domain`` and | |
| + ``codomain`` is assumed to be normalized by a factor `u`, | |
| + i.e. the pullback `\varphi^\ast` is such that | |
| + `\varphi^\ast \omega_\text{codomain} = u \omega_\text{codomain}`. | |
| + The default ``True`` is equivalent to 1. ``False`` or 0 | |
| + means that the normalization factor is unknown and must | |
| + be computed by evaluating the derivatives of the modular | |
| + polynomial of level ``degree`` (this may be time consuming). | |
| + | |
| - ``check`` (default: ``True``) checks if the input is valid to define an isogeny | |
| EXAMPLES: | |
| @@ -704,15 +718,23 @@ | |
| sage: phi_s.rational_maps() == phi.rational_maps() | |
| True | |
| - However only normalized isogenies can be constructed this | |
| - way. So it won't find the multiplication-by-3 endomorphism:: | |
| + However only normalized isogenies can be constructed by default. | |
| + So it won't find the multiplication-by-3 endomorphism:: | |
| - sage: E.isogeny(None, codomain=E,degree=9) | |
| + sage: E.isogeny(None, codomain=E, degree=9) | |
| Traceback (most recent call last): | |
| ... | |
| ValueError: The two curves are not linked by a normalized isogeny of degree 9 | |
| - | |
| - nor the dual isogeny:: | |
| + | |
| + It is well known, however, that the multiplication-by-m endomorphism is | |
| + such that `[m]^\ast\omega = m\omega`, thus we can use the ``normalized`` | |
| + parameter:: | |
| + | |
| + sage: E.isogeny(None, codomain=E, degree=9, normalized=3) | |
| + Isogeny of degree 9 from Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field | |
| + | |
| + Similarly, the dual isogeny is not normalized, but its normalization factor | |
| + is easily obtained as above:: | |
| sage: E2.isogeny(None,codomain=E,degree=5) | |
| Traceback (most recent call last): | |
| @@ -720,8 +742,8 @@ | |
| ValueError: The two curves are not linked by a normalized isogeny of degree 5 | |
| sage: phi.dual() | |
| Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field | |
| - sage: phi.dual().is_normalized() | |
| - False | |
| + sage: phi.dual().normalization_factor() | |
| + 5 | |
| Here an example of a construction of a endomorphisms with cyclic | |
| kernel on a CM-curve:: | |
| @@ -839,7 +861,8 @@ | |
| # Python Special Functions | |
| # | |
| - def __init__(self, E, kernel, codomain=None, degree=None, model=None, check=True): | |
| + def __init__(self, E, kernel, codomain=None, degree=None, model=None, | |
| + normalized=True, check=True): | |
| r""" | |
| Constructor for EllipticCurveIsogeny class. | |
| @@ -898,8 +921,15 @@ | |
| # save the domain/codomain: really used now (trac #7096) | |
| old_domain = E | |
| old_codomain = codomain | |
| - | |
| - (pre_isom, post_isom, E, codomain, kernel) = compute_sequence_of_maps(E, codomain, degree) | |
| + | |
| + if not normalized: | |
| + u = compute_normalization_factor(E, codomain, degree) | |
| + else: | |
| + u = E.base_field()(normalized) | |
| + | |
| + (pre_isom, post_isom, E, codomain, | |
| + kernel) = compute_sequence_of_maps(E, codomain, degree, | |
| + normalization_factor=u) | |
| self.__init_algebraic_structs(E) | |
| @@ -2913,8 +2943,8 @@ | |
| sage: phi2.get_post_isomorphism() | |
| Generic morphism: | |
| From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 65*x + 69 over Finite Field of size 83 | |
| - To: Abelian group of points on Elliptic Curve defined by y^2 + x*y + 77*y = x^3 + 49*x + 28 over Finite Field of size 83 | |
| - Via: (u,r,s,t) = (1, 7, 42, 80) | |
| + To: Abelian group of points on Elliptic Curve defined by y^2 + x*y + y = x^3 + 4*x + 16 over Finite Field of size 83 | |
| + Via: (u,r,s,t) = (1, 7, 42, 42) | |
| """ | |
| return self.__post_isomorphism | |
| @@ -2976,7 +3006,30 @@ | |
| """ | |
| self.set_post_isomorphism(WeierstrassIsomorphism(self.__E2, (-1,0,-self.__E2.a1(),-self.__E2.a3()))) | |
| - def is_normalized(self, via_formal=True, check_by_pullback=True): | |
| + def normalization_factor(self): | |
| + r""" | |
| + Returns the element `u` of the base field such that | |
| + `\varphi^\ast\omega_{\text{codomain}} = u\omega_{\text{domain}}`. | |
| + | |
| + EXAMPLES:: | |
| + sage: E = EllipticCurve('11a1') | |
| + sage: phi = E.isogeny(None, E, 4, normalized=2) | |
| + sage: phi.normalization_factor() | |
| + 2 | |
| + sage: phi.dual().normalization_factor() | |
| + 2 | |
| + | |
| + sage: E = EllipticCurve(GF(17), [-2, 3, -5, 7, -11]) | |
| + sage: R.<x> = GF(17)[] | |
| + sage: f = x+6 | |
| + sage: phi = EllipticCurveIsogeny(E, f) | |
| + sage: phi.normalization_factor() | |
| + 1 | |
| + | |
| + """ | |
| + return self.formal(prec=1)[1] | |
| + | |
| + def is_normalized(self): | |
| r""" | |
| Returns ``True`` if this isogeny is normalized. An isogeny | |
| `\varphi\colon E\to E_2` between two given Weierstrass | |
| @@ -2985,15 +3038,6 @@ | |
| `omega_2` are the invariant differentials on `E` and `E_2` | |
| corresponding to the given equation. | |
| - INPUT: | |
| - | |
| - - ``via_formal`` - (default: ``True``) If ``True`` it simply checks if | |
| - the leading term of the formal series is 1. Otherwise | |
| - it uses a deprecated algorithm involving the second | |
| - optional argument. | |
| - | |
| - - ``check_by_pullback`` - (default:``True``) Deprecated. | |
| - | |
| EXAMPLES:: | |
| sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism | |
| @@ -3054,85 +3098,7 @@ | |
| True | |
| """ | |
| - # easy algorithm using the formal expansion. | |
| - if via_formal: | |
| - phi_formal = self.formal(prec=5) | |
| - return phi_formal[1] == 1 | |
| - | |
| - # this is the old algorithm. it should be deprecated. | |
| - check_prepost_isomorphism = False | |
| - | |
| - f_normalized = True | |
| - | |
| - if (check_by_pullback): | |
| - | |
| - (Xmap, Ymap) = self.rational_maps() | |
| - | |
| - E1 = self.__E1 | |
| - E2 = self.__E2 | |
| - | |
| - a1 = E1.a1() | |
| - a3 = E1.a3() | |
| - | |
| - a1pr = E2.a1() | |
| - a3pr = E2.a3() | |
| - | |
| - x = self.__x_var | |
| - y = self.__y_var | |
| - | |
| - Xmap_pr = Xmap.derivative(x) | |
| - | |
| - domain_inv_diff = 1/(2*y + a1*x + a3) | |
| - codomain_inv_diff = Xmap_pr/(2*Ymap + a1pr*Xmap + a3pr) | |
| - | |
| - inv_diff_quo = domain_inv_diff/codomain_inv_diff | |
| - | |
| - if (1 == inv_diff_quo): | |
| - f_normalized = True | |
| - else: | |
| - # For some reason, in certain cases, when the isogeny | |
| - # is pre or post composed with a translation the | |
| - # resulting rational functions are too complicated for | |
| - # sage to simplify down to a constant in this case, we | |
| - # do some cheating by checking if the post-composition | |
| - # by isogeny has a non 1 scaling factor | |
| - if ( inv_diff_quo.numerator().is_constant() and (inv_diff_quo.denominator().is_constant) ): | |
| - f_normalized = False | |
| - else: | |
| - check_prepost_isomorphism = True | |
| - else: | |
| - check_prepost_isomorphism = True | |
| - | |
| - # If we skip checking by the pullback of the invariant | |
| - # differential OR if that was inconclusive We explicitly check | |
| - # if there is a post isomorphism and if it has a non 1 scaling | |
| - # factor or if it is a just a translation. NOTE: This only | |
| - # works because we are using algorithms for calculating the | |
| - # isogenies that calculate a separable normalized isogeny, if | |
| - # this changes, this check will no longer be correct. | |
| - # | |
| - if (check_prepost_isomorphism): | |
| - post_isom = self.__post_isomorphism | |
| - if (post_isom is not None): | |
| - if (1 == self.__base_field(post_isom.u)): | |
| - f_post_normalized = True | |
| - else: | |
| - f_post_normalized = False | |
| - else: | |
| - f_post_normalized = True | |
| - | |
| - pre_isom = self.__pre_isomorphism | |
| - if (pre_isom is not None): | |
| - if (1 == self.__base_field(pre_isom.u)): | |
| - f_pre_normalized = True | |
| - else: | |
| - f_pre_normalized = False | |
| - else: | |
| - f_pre_normalized = True | |
| - | |
| - f_normalized = f_pre_normalized and f_post_normalized | |
| - | |
| - return f_normalized | |
| + return self.normalization_factor() == 1 | |
| def dual(self): | |
| r""" | |
| @@ -3217,63 +3183,65 @@ | |
| """ | |
| - if (self.__base_field.characteristic() in [2,3]): | |
| - raise NotImplemented | |
| - | |
| if (self.__dual is not None): | |
| return self.__dual | |
| + F = self.__base_field | |
| + d = self.__degree | |
| + | |
| # trac 7096 | |
| - (E1, E2pr, pre_isom, post_isom) = compute_intermediate_curves(self.codomain(), self.domain()) | |
| - | |
| - F = self.__base_field | |
| - | |
| - d = self.__degree | |
| - | |
| - # trac 7096 | |
| - if F(d) == 0: | |
| - raise NotImplementedError, "The dual isogeny is not separable, but only separable isogenies are implemented so far" | |
| + #if F(d) == 0: | |
| + # raise NotImplementedError, "The dual isogeny is not separable, but only separable isogenies are implemented so far" | |
| + | |
| + u = F(d) / self.normalization_factor() | |
| + phi_hat = EllipticCurveIsogeny(self.codomain(), None, self.domain(), | |
| + d, normalized=u) | |
| + phi_hat.__dual = self | |
| + return phi_hat | |
| - # trac 7096 | |
| - # this should take care of the case when the isogeny is not normalized. | |
| - u = self.formal(prec=5)[1] | |
| - isom = WeierstrassIsomorphism(E2pr, (u/F(d), 0, 0, 0)) | |
| - | |
| - E2 = isom.codomain().codomain() | |
| - | |
| - pre_isom = self.__E2.isomorphism_to(E1) | |
| - post_isom = E2.isomorphism_to(self.__E1) | |
| - | |
| - phi_hat = EllipticCurveIsogeny(E1, None, E2, d) | |
| - | |
| - phi_hat.set_pre_isomorphism(pre_isom) | |
| - phi_hat.set_post_isomorphism(post_isom) | |
| - phi_hat.__perform_inheritance_housekeeping() | |
| - | |
| - assert phi_hat.codomain() == self.domain() | |
| - | |
| - # trac 7096 : this adjust a posteriori the automorphism | |
| - # on the codomain of the dual isogeny. | |
| - # we used _a_ Weierstrass isomorphism to get to the original | |
| - # curve, but we may have to change it my an automorphism. | |
| - # we impose that the composition has the degree | |
| - # as a leading coefficient in the formal expansion. | |
| - | |
| - phi_sc = self.formal(prec=5)[1] | |
| - phihat_sc = phi_hat.formal(prec=5)[1] | |
| - | |
| - sc = phi_sc * phihat_sc/F(d) | |
| - | |
| - if sc != 1: | |
| - auts = phi_hat.codomain().automorphsims() | |
| - aut = [a for a in auts if a.u == sc] | |
| - if len(aut) != 1: | |
| - raise ValueError, "There is a bug in dual()." | |
| - phi_hat.set_post_isomorphism(a[0]) | |
| - | |
| - self.__dual = phi_hat | |
| - | |
| - return phi_hat | |
| +# # trac 7096 | |
| +# (E1, E2pr, pre_isom, post_isom) = compute_intermediate_curves(self.codomain(), self.domain()) | |
| +# | |
| +# # trac 7096 | |
| +# # this should take care of the case when the isogeny is not normalized. | |
| +# u = self.formal(prec=5)[1] | |
| +# isom = WeierstrassIsomorphism(E2pr, (u/F(d), 0, 0, 0)) | |
| +# | |
| +# E2 = isom.codomain().codomain() | |
| +# | |
| +# pre_isom = self.__E2.isomorphism_to(E1) | |
| +# post_isom = E2.isomorphism_to(self.__E1) | |
| +# | |
| +# phi_hat = EllipticCurveIsogeny(E1, None, E2, d) | |
| +# | |
| +# phi_hat.set_pre_isomorphism(pre_isom) | |
| +# phi_hat.set_post_isomorphism(post_isom) | |
| +# phi_hat.__perform_inheritance_housekeeping() | |
| +# | |
| +# assert phi_hat.codomain() == self.domain() | |
| +# | |
| +# # trac 7096 : this adjust a posteriori the automorphism | |
| +# # on the codomain of the dual isogeny. | |
| +# # we used _a_ Weierstrass isomorphism to get to the original | |
| +# # curve, but we may have to change it my an automorphism. | |
| +# # we impose that the composition has the degree | |
| +# # as a leading coefficient in the formal expansion. | |
| +# | |
| +# phi_sc = self.formal(prec=5)[1] | |
| +# phihat_sc = phi_hat.formal(prec=5)[1] | |
| +# | |
| +# sc = phi_sc * phihat_sc/F(d) | |
| +# | |
| +# if sc != 1: | |
| +# auts = phi_hat.codomain().automorphsims() | |
| +# aut = [a for a in auts if a.u == sc] | |
| +# if len(aut) != 1: | |
| +# raise ValueError, "There is a bug in dual()." | |
| +# phi_hat.set_post_isomorphism(a[0]) | |
| +# | |
| +# self.__dual = phi_hat | |
| +# | |
| +# return phi_hat | |
| def formal(self,prec=20): | |
| r""" | |
| @@ -3282,33 +3250,32 @@ | |
| INPUT: | |
| - - ``prec`` - (default = 20), the precision with which the computations | |
| - in the formal group are carried out. | |
| + - ``prec`` - (default = 20), the precision with which the power series | |
| + is computed. | |
| EXAMPLES:: | |
| sage: E = EllipticCurve(GF(13),[1,7]) | |
| sage: phi = E.isogeny(E(10,4)) | |
| sage: phi.formal() | |
| - t + 12*t^13 + 2*t^17 + 8*t^19 + 2*t^21 + O(t^23) | |
| + t + 12*t^13 + 2*t^17 + 8*t^19 + O(t^20) | |
| sage: E = EllipticCurve([0,1]) | |
| sage: phi = E.isogeny(E(2,3)) | |
| - sage: phi.formal(prec=10) | |
| + sage: phi.formal(prec=13) | |
| t + 54*t^5 + 255*t^7 + 2430*t^9 + 19278*t^11 + O(t^13) | |
| sage: E = EllipticCurve('11a2') | |
| sage: R.<x> = QQ[] | |
| sage: phi = E.isogeny(x^2 + 101*x + 12751/5) | |
| - sage: phi.formal(prec=7) | |
| + sage: phi.formal(prec=10) | |
| t - 2724/5*t^5 + 209046/5*t^7 - 4767/5*t^8 + 29200946/5*t^9 + O(t^10) | |
| - | |
| """ | |
| Eh = self.__E1.formal() | |
| f, g = self.rational_maps() | |
| - xh = Eh.x(prec=prec) | |
| - yh = Eh.y(prec=prec) | |
| + xh = Eh.x(prec=prec-3) | |
| + yh = Eh.y(prec=prec-3) | |
| fh = f(xh,yh) | |
| gh = g(xh,yh) | |
| return -fh/gh | |
| @@ -3470,23 +3437,28 @@ | |
| # def starks_find_r_and_t(T, Z): | |
| -def compute_intermediate_curves(E1, E2): | |
| +def compute_intermediate_curves(E1, E2, normalization_factor=1): | |
| r""" | |
| - Computes isomorphism from ``E1`` to an intermediate domain and an | |
| - isomorphism from an intermediate codomain to ``E2``. | |
| + Gives canonical models for E1 and E2 and the related isomorphisms. | |
| - Intermediate domain and intermediate codomain, are in short | |
| - Weierstrass form. | |
| + If the caracteristic of the base field is not 2 or 3, these are the short | |
| + Weierstrass models. | |
| - This is used so we can compute `\wp` functions from the short | |
| - Weierstrass model more easily. | |
| - | |
| - The underlying field must be of characteristic not equal to 2,3. | |
| - | |
| + In characteristic 3, this is the model `y^2 = x^3 + a_2 x^2 + a_4 x + a_6` | |
| + obtained by completing the square. | |
| + | |
| + In characteristic 2 these are just ``E1`` and ``E2`` themselves. | |
| + | |
| + The ``normalization_factor`` can be used to scale the model of ``E2``. If it | |
| + is different from 1, then the normalized model is scaled by | |
| + ``1/normalization_factor`` (i.e., via the isomorphism with | |
| + ``(u, r, s, t) = (1/normalization_factor, 0, 0, 0)``) | |
| + | |
| INPUT: | |
| - ``E1`` - an elliptic curve | |
| - ``E2`` - an elliptic curve | |
| + - ``normalization_factor`` - an element of the base field. Default is 1. | |
| OUTPUT: | |
| @@ -3514,8 +3486,8 @@ | |
| Via: (u,r,s,t) = (1, 76, 41, 3), | |
| Generic morphism: | |
| From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 65*x + 69 over Finite Field of size 83 | |
| - To: Abelian group of points on Elliptic Curve defined by y^2 + x*y + 77*y = x^3 + 49*x + 28 over Finite Field of size 83 | |
| - Via: (u,r,s,t) = (1, 7, 42, 80)) | |
| + To: Abelian group of points on Elliptic Curve defined by y^2 + x*y + y = x^3 + 4*x + 16 over Finite Field of size 83 | |
| + Via: (u,r,s,t) = (1, 7, 42, 42)) | |
| sage: R.<x> = QQ[] | |
| sage: K.<i> = NumberField(x^2 + 1) | |
| @@ -3532,44 +3504,58 @@ | |
| From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1 | |
| To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1 | |
| Via: (u,r,s,t) = (1, 0, 0, 0)) | |
| + | |
| + sage: K.<z> = GF(8, 'z') | |
| + sage: E = EllipticCurve([1, 0, z, z + 1, z^2]) | |
| + sage: E1, E2, i1, i2 = compute_intermediate_curves(E, E) | |
| + sage: E == E1 and E == E2 | |
| + True | |
| + sage: i1.is_identity() and i2.is_identity() | |
| + True | |
| + | |
| + sage: K = GF(27, 'z') | |
| + sage: E = EllipticCurve(K, [1, 1, 0, 1, 1]) | |
| + sage: compute_intermediate_curves(E, E, -1) | |
| + (Elliptic Curve defined by y^2 = x^3 + 2*x^2 + x + 1 over Finite Field in z of size 3^3, | |
| + Elliptic Curve defined by y^2 = x^3 + 2*x^2 + x + 1 over Finite Field in z of size 3^3, | |
| + Generic morphism: | |
| + From: Abelian group of points on Elliptic Curve defined by y^2 + x*y = x^3 + x^2 + x + 1 over Finite Field in z of size 3^3 | |
| + To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 2*x^2 + x + 1 over Finite Field in z of size 3^3 | |
| + Via: (u,r,s,t) = (1, 0, 1, 0), | |
| + Generic morphism: | |
| + From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 2*x^2 + x + 1 over Finite Field in z of size 3^3 | |
| + To: Abelian group of points on Elliptic Curve defined by y^2 + x*y = x^3 + x^2 + x + 1 over Finite Field in z of size 3^3 | |
| + Via: (u,r,s,t) = (2, 0, 1, 0)) | |
| """ | |
| - if (E1.base_ring().characteristic() in [2,3]): | |
| - raise NotImplemented | |
| - | |
| - # compute the r,s,t values that clear the denominator of E1 | |
| - a1 = E1.a1() | |
| - a2 = E1.a2() | |
| - a3 = E1.a3() | |
| - | |
| - s1 = -a1/2 | |
| - r1 = (s1**2 + s1*a1 - a2)/3 | |
| - t1 = (-r1*a1 - a3)/2 | |
| - | |
| - # compute the isomorphism from E1 to intermediate_domain | |
| - pre_isom = WeierstrassIsomorphism(E1, (1, r1, s1, t1)) | |
| - | |
| + K = E1.base_ring() | |
| + | |
| + if K.characteristic() == 2: | |
| + return (E1, E2, WeierstrassIsomorphism(E1, (1, 0, 0, 0), E1), | |
| + WeierstrassIsomorphism(E1, (1, 0, 0, 0), E2)) | |
| + | |
| + # In characteristic 3, a model of the form | |
| + # y^2 = x^3 + a2 x^2 + a4 x + a6 | |
| + # is enough | |
| + complete_cube = K.characteristic() != 3 | |
| + | |
| + # Domain curve to simplified Weierstrass model | |
| + si = E1.isomorphism_to(E1.short_weierstrass_model(complete_cube)) | |
| + pre_isom = WeierstrassIsomorphism(E1, (1, si.r, si.s, si.t)) | |
| intermediate_domain = pre_isom.codomain().codomain() | |
| - # compute the r,s,t values that clear the denominator of E2 | |
| - a1pr = E2.a1() | |
| - a2pr = E2.a2() | |
| - a3pr = E2.a3() | |
| - | |
| - s2 = -a1pr/2 | |
| - r2 = (s2**2 + s2*a1pr - a2pr)/3 | |
| - t2 = (-r2*a1pr - a3pr)/2 | |
| - | |
| - post_isom_inv = WeierstrassIsomorphism(E2, (1, r2, s2, t2)) | |
| - intermediate_codomain = post_isom_inv.codomain().codomain() | |
| - | |
| - post_isom = WeierstrassIsomorphism(intermediate_codomain, (1, -r2, -s2, -t2)) | |
| + # Codomain curve to simplified Weierstrass model plus | |
| + # scaling by the inverse of the normalization factor | |
| + si = E2.isomorphism_to(E2.short_weierstrass_model(complete_cube)) | |
| + post_isom = ~WeierstrassIsomorphism(E2, (~normalization_factor, | |
| + si.r, si.s, si.t)) | |
| + intermediate_codomain = post_isom.domain().codomain() | |
| return (intermediate_domain, intermediate_codomain, pre_isom, post_isom) | |
| -def compute_sequence_of_maps(E1, E2, ell, algorithm=None): | |
| +def compute_sequence_of_maps(E1, E2, ell, algorithm=None, normalization_factor=1): | |
| r""" | |
| Given domain ``E1`` and codomain ``E2`` such that there is a | |
| degree ``ell`` separable normalized isogeny from ``E1`` to ``E2``, | |
| @@ -3638,15 +3624,14 @@ | |
| Via: (u,r,s,t) = (1, 8, 48, 44), | |
| Generic morphism: | |
| From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 41*x + 66 over Finite Field of size 97 | |
| - To: Abelian group of points on Elliptic Curve defined by y^2 + x*y + 9*y = x^3 + 83*x + 6 over Finite Field of size 97 | |
| - Via: (u,r,s,t) = (1, 89, 49, 53), | |
| - Elliptic Curve defined by y^2 = x^3 + 52*x + 31 over Finite Field of size 97, | |
| - Elliptic Curve defined by y^2 = x^3 + 41*x + 66 over Finite Field of size 97, | |
| - x^5 + 67*x^4 + 13*x^3 + 35*x^2 + 77*x + 69) | |
| + To: Abelian group of points on Elliptic Curve defined by y^2 + x*y + y = x^3 + 87*x + 26 over Finite Field of size 97 | |
| + Via: (u,r,s,t) = (1, 89, 49, 49), | |
| + Elliptic Curve defined by y^2 = x^3 + 52*x + 31 over Finite Field of size 97, | |
| + Elliptic Curve defined by y^2 = x^3 + 41*x + 66 over Finite Field of size 97, x^5 + 67*x^4 + 13*x^3 + 35*x^2 + 77*x + 69) | |
| """ | |
| - (E1pr, E2pr, pre_isom, post_isom) = compute_intermediate_curves(E1, E2) | |
| + (E1pr, E2pr, pre_isom, post_isom) = compute_intermediate_curves(E1, E2, normalization_factor) | |
| if algorithm is None or algorithm in ell_isogeny_char_zero.algorithm_names: | |
| try: | |
| @@ -3660,6 +3645,124 @@ | |
| return (pre_isom, post_isom, E1pr, E2pr, ker_poly) | |
| +def _compute_normalization_factor(E1, E2, degree, f=None): | |
| + r""" | |
| + Private routine called by ``compute_normalization_factor``. | |
| + | |
| + INPUT: | |
| + | |
| + - ``E1`` - Elliptic curve. | |
| + - ``E2`` - Elliptic curve. | |
| + - ``degree`` - a prime, the degree of the isogeny from E1 to E2. | |
| + - ``f`` - (optional) a common root of Phi(X, j1) and Phi(X, j2), where | |
| + Phi is Atkin's modular polynomial of degree ``degree``. | |
| + | |
| + OUTPUT: | |
| + | |
| + field element -- the normalization factor. | |
| + | |
| + """ | |
| + | |
| + K = E1.base_field() | |
| + p = K.characteristic() | |
| + j1 = E1.j_invariant() | |
| + j2 = E2.j_invariant() | |
| + | |
| + if p != 0 and degree % p == 0: | |
| + return 0 | |
| + elif p == 2 or p == 3: | |
| + # Up to isomorphism there is only one supersingular curve and | |
| + # any of its endomorphisms has normalization factor + or - 1 | |
| + if j1 == 0 and j2 == 0: | |
| + w = WeierstrassIsomorphism(E1, None, E2) | |
| + return w.u | |
| + | |
| + # In the ordinary case, the characteristic 2 and 3 cases behave | |
| + # differently. | |
| + elif j1 != 0 and j2 != 0: | |
| + # In characteristic 2, models of the form | |
| + # y^2 + xy = x^3 + a x^2 + b | |
| + # are always normalized. | |
| + if p == 2: | |
| + return E1.a1() / E2.a1() | |
| + | |
| + # In characteristic 3, models | |
| + # y^2 = x^3 + a1 x^2 + b1, | |
| + # y^2 = x^3 + a2 x^2 + b2 | |
| + # are normalized if and only if a1 = a2. | |
| + else: | |
| + return ((E1.a1()**2 + E2.a2()) / (E1.a1()**2 + E2.a2())).sqrt() | |
| + else: | |
| + raise ValueError, "Curves are not isogenous." | |
| + | |
| + # In characteristic not 2 or 3, we go to the short Weierstrass model | |
| + # and apply Elkies' formulas | |
| + else: | |
| + E1sh = E1.short_weierstrass_model() | |
| + | |
| + P = PolynomialRing(K, "F,J"); | |
| + F, J = P.gens() | |
| + DB = AtkinModularPolynomialDatabase() | |
| + Phi = P(DB[degree]) | |
| + | |
| + # Since we use Atkin's modular polynomials, we need to know the common | |
| + # root f of Phi(X, j1) and Phi(X, j2) | |
| + if not f: | |
| + fs = Phi(F, j1).gcd(Phi(F, j2)).univariate_polynomial().roots(multiplicities=False) | |
| + if not fs: | |
| + raise ValueError, "Curves are not " + degree + "-isogenous." | |
| + else: | |
| + f = fs[0] | |
| + | |
| + # Elkies' formulae | |
| + DF = f * Phi.derivative(F)(f, j1) | |
| + DJ = j1 * Phi.derivative(J)(f, j1) | |
| + DFst = f * Phi.derivative(F)(f, j2) | |
| + DJst = degree * j2 * Phi.derivative(J)(f, j2) | |
| + _, _, _, a4, a6 = E1sh.a_invariants() | |
| + | |
| + jj = j2 / (j2 - 1728) | |
| + | |
| + A4 = -K(27)/K(4) * degree**4 * (DFst**2 * DJ**2 * a6**2) / (DJst**2 * DF**2 * a4**2) * jj | |
| + A6 = -K(27)/K(4) * degree**6 * (DFst**3 * DJ**3 * a6**3) / (DJst**3 * DF**3 * a4**3) * jj | |
| + | |
| + E2sh = EllipticCurve([A4, A6]) | |
| + | |
| + return WeierstrassIsomorphism(E1, None, E1sh).u * WeierstrassIsomorphism(E2sh, None, E2).u | |
| + | |
| +def compute_normalization_factor(E1, E2, degree): | |
| + r""" | |
| + Compute the normalization factor of the isogeny of prime degree ``degree`` | |
| + from ``E1`` to ``E2``. | |
| + | |
| + INPUT: | |
| + | |
| + - ``E1`` - Elliptic curve. | |
| + - ``E2`` - Elliptic curve. | |
| + - ``degree`` - a prime, the degree of the isogeny from E1 to E2. | |
| + | |
| + OUTPUT: | |
| + | |
| + field element -- the normalization factor. | |
| + | |
| + ..note: | |
| + The normalization factor is only defined up to the automorphisms of | |
| + ``E1`` and ``E2``. | |
| + | |
| + EXAMPLES:: | |
| + | |
| + sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_normalization_factor | |
| + sage: E = EllipticCurve(GF(97), [1,0,1,1,0]) | |
| + sage: R.<x> = GF(97)[]; f = x^5 + 27*x^4 + 61*x^3 + 58*x^2 + 28*x + 21 | |
| + sage: phi = EllipticCurveIsogeny(E, f) | |
| + sage: compute_normalization_factor(E, phi.codomain(), 11)^2 | |
| + 1 | |
| + | |
| + """ | |
| + return _compute_normalization_factor(E1, E2, degree) | |
| + | |
| + | |
| + | |
| ########################################################################## | |
| # The following section is all about computing l-isogenies, where l is | |
| # a prime. The genus 0 cases `l` = 2, 3, 5, 7 and 13 are | |
| diff -r 308b228f1089 -r c1ea68aa11f5 sage/schemes/elliptic_curves/ell_field.py | |
| --- a/sage/schemes/elliptic_curves/ell_field.py Thu Apr 28 17:00:51 2011 +0200 | |
| +++ b/sage/schemes/elliptic_curves/ell_field.py Wed Jul 06 17:29:34 2011 -0400 | |
| @@ -697,7 +697,8 @@ | |
| else: | |
| return Eout | |
| - def isogeny(self, kernel, codomain=None, degree=None, model=None, check=True): | |
| + def isogeny(self, kernel, codomain=None, degree=None, model=None, | |
| + normalized=True, check=True): | |
| r""" | |
| Returns an elliptic curve isogeny from self. | |
| @@ -747,6 +748,18 @@ | |
| rationals, then the codomain is set to be the unique | |
| global minimum model. | |
| + - ``normalized`` - a boolean or an element of the base field (default:``True``). | |
| + This parameter is only considered when the codomain parameter | |
| + is not ``None``. If an element `u` of the base field is | |
| + given, then the isogeny `\phi` between ``domain`` and | |
| + ``codomain`` is assumed to be normalized by a factor `u`, | |
| + i.e. the pullback `\phi^\ast` is such that | |
| + `\phi^\ast \omega_\text{codomain} = u \omega_\text{codomain}`. | |
| + The default ``True`` is equivalent to 1. ``False`` or 0 | |
| + means that the normalization factor is unknown and must | |
| + be computed by evaluating the derivatives of the modular | |
| + polynomial of level ``degree`` (this may be time consuming). | |
| + | |
| - ``check`` (default: True) checks if the input is valid to define an | |
| isogeny | |
| @@ -786,7 +799,8 @@ | |
| ValueError: The polynomial does not define a finite subgroup of the elliptic curve. | |
| """ | |
| - return EllipticCurveIsogeny(self, kernel, codomain, degree, model, check=check) | |
| + return EllipticCurveIsogeny(self, kernel, codomain, degree, model, | |
| + normalized, check) | |
| def isogeny_codomain(self, kernel, degree=None): |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment