Computing canonical heights with little (or no) factorization

Silverman, Joseph

doi:10.1090/S0025-5718-97-00812-0

Computing canonical heights with little (or no) factorization
HTML articles powered by AMS MathViewer

by Joseph H. Silverman PDF

Math. Comp. 66 (1997), 787-805 Request permission

Abstract:

Let $E/ \mathbb {Q}$ be an elliptic curve with discriminant $\Delta$, and let $P\in E( \mathbb {Q})$. The standard method for computing the canonical height $\hat h(P)$ is as a sum of local heights $\hat h (P)= \hat \lambda _{\infty }(P)+\sum _{p} \hat \lambda _{p}(P)$. There are well-known series for computing the archimedean height $\hat \lambda _{\infty }(P)$, and the non-archimedean heights $\hat \lambda _{p}(P)$ are easily computed as soon as all prime factors of $\Delta$ have been determined. However, for curves with large coefficients it may be difficult or impossible to factor $\Delta$. In this note we give a method for computing the non-archimedean contribution to $\hat h (P)$ which is quite practical and requires little or no factorization. We also give some numerical examples illustrating the algorithm.

References

C. Batut, D. Bernardi, H. Cohen, M. Olivier, PARI-GP, Version 1.3.7.
D. Bernardi, Décomprime, Version 1.0, un program de décomposition des nombres en facteurs premiers utilisant les courbes elliptiques.
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
J. E. Cremona, Algorithms for modular elliptic curves, Cambridge University Press, Cambridge, 1992. MR 1201151
S. Fermiger, Un exemple de courbe elliptique definie sur $\mathbb {Q}$ de rang ${}\ge 19$, C.R. Acad. Sci. Paris 315 (1992), 719–722.
H. G. Folz and H. G. Zimmer, What is the rank of the Demjanenko matrix?, J. Symbolic Comput. 4 (1987), no. 1, 53–67. MR 908412, DOI 10.1016/S0747-7171(87)80053-6
Fumio Hazama, Demjanenko matrix, class number, and Hodge group, J. Number Theory 34 (1990), no. 2, 174–177. MR 1042490, DOI 10.1016/0022-314X(90)90147-J
Alain Kraus, Quelques remarques à propos des invariants $c_4,\;c_6$ et $\Delta$ d’une courbe elliptique, Acta Arith. 54 (1989), no. 1, 75–80 (French). MR 1024419, DOI 10.4064/aa-54-1-75-80
Michael Laska, An algorithm for finding a minimal Weierstrass equation for an elliptic curve, Math. Comp. 38 (1982), no. 157, 257–260. MR 637305, DOI 10.1090/S0025-5718-1982-0637305-2
H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649–673. MR 916721, DOI 10.2307/1971363
Jean-François Mestre, Construction d’une courbe elliptique de rang $\geq 12$, C. R. Acad. Sci. Paris Sér. I Math. 295 (1982), no. 12, 643–644 (French, with English summary). MR 688896
Jean-François Mestre, Un exemple de courbe elliptique sur $\textbf {Q}$ de rang $\geq 15$, C. R. Acad. Sci. Paris Sér. I Math. 314 (1992), no. 6, 453–455 (French, with English summary). MR 1154385
Koh-ichi Nagao, An example of elliptic curve over $\textbf {Q}$ with rank $\ge 20$, Proc. Japan Acad. Ser. A Math. Sci. 69 (1993), no. 8, 291–293. MR 1249440
Koh-ichi Nagao and Tomonori Kouya, An example of elliptic curve over $\mathbf Q$ with rank $\geq 21$, Proc. Japan Acad. Ser. A Math. Sci. 70 (1994), no. 4, 104–105. MR 1276883
Hans Riesel, Prime numbers and computer methods for factorization, Progress in Mathematics, vol. 57, Birkhäuser Boston, Inc., Boston, MA, 1985. MR 897531, DOI 10.1007/978-1-4757-1089-2
Jonathan W. Sands and Wolfgang Schwarz, A Demjanenko matrix for abelian fields of prime power conductor, J. Number Theory 52 (1995), no. 1, 85–97. MR 1331767, DOI 10.1006/jnth.1995.1057
Wolfgang Schwarz, Demjanenko matrix and $2$-divisibility of class numbers, Arch. Math. (Basel) 60 (1993), no. 2, 154–156. MR 1199672, DOI 10.1007/BF01199101
Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. MR 817210, DOI 10.1007/978-1-4757-1920-8
Joseph H. Silverman, Advanced topics in the arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 151, Springer-Verlag, New York, 1994. MR 1312368, DOI 10.1007/978-1-4612-0851-8
Joseph H. Silverman, Computing heights on elliptic curves, Math. Comp. 51 (1988), no. 183, 339–358. MR 942161, DOI 10.1090/S0025-5718-1988-0942161-4
Heinz M. Tschöpe and Horst G. Zimmer, Computation of the Néron-Tate height on elliptic curves, Math. Comp. 48 (1987), no. 177, 351–370. MR 866121, DOI 10.1090/S0025-5718-1987-0866121-6
J. Tate, Algorithm for determining the type of a singular fiber in an elliptic pencil, Modular functions of one variable, IV (Proc. Internat. Summer School, Univ. Antwerp, Antwerp, 1972) Lecture Notes in Math., Vol. 476, Springer, Berlin, 1975, pp. 33–52. MR 0393039
Horst G. Zimmer, A limit formula for the canonical height of an elliptic curve and its application to height computations, Number theory (Banff, AB, 1988) de Gruyter, Berlin, 1990, pp. 641–659. MR 1106690