Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-29T06:14:58.594Z Has data issue: false hasContentIssue false
  • English
  • Français

Tracking $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}p$-adic precision

Published online by Cambridge University Press:  01 August 2014

Xavier Caruso ,
David Roe  and
Tristan Vaccon
Xavier Caruso
Affiliation:
Institut de recheche en mathématiques de Rennes (IRMAR), Université Rennes 1, Campus de Beaulieu, 35042 Rennes Cedex, France email [email protected]
David Roe
Affiliation:
Department of Mathematics, University of Calgary, 2500 University Dr NW, Calgary, AB T2N 1N4, Canada email [email protected]
Tristan Vaccon
Affiliation:
Institut de recheche en mathématiques de Rennes (IRMAR), Université Rennes 1, Campus de Beaulieu, 35042 Rennes Cedex, France email [email protected]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We present a new method to propagate $p$-adic precision in computations, which also applies to other ultrametric fields. We illustrate it with some examples and give a toy application to the stable computation of the SOMOS 4 sequence.

Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 17 , Special Issue A: Algorithmic Number Theory Symposium XI , 2014 , pp. 274 - 294
Copyright
© The Author(s) 2014 

References

Batut, C., Belabas, K., Benardi, D., Cohen, H. and Olivier, M., User’s guide to PARI-GP (1985–2013), http://pari.math.u-bordeaux.fr.Google Scholar
Berthomieu, J., van der Hoeven, J. and Lecerf, G., ‘Relaxed algorithms for p-adic numbers’, J. Théor. Nombres Bordeaux 23 (2011) no. 3, 541–577.CrossRefGoogle Scholar
Bosma, W., Cannon, J. and Payoust, C., ‘The Magma algebra system. I. The user language’, J. Symbolic Comput. 24 (1997) no. 3–4, 235–265.CrossRefGoogle Scholar
Bostan, A., González-Vega, L., Perdry, H. and Schost, É., ‘‘From Newton sums to coefficients: complexity issues in characteristic p’’, MEGA’05: Eighth International Symposium on Effective Methods in Algebraic Geometry (2005), available at: http://specfun.inria.fr/bostan/publications/BoClSa05.pdf.Google Scholar
Caruso, X., ‘Random matrices over a DVR and LU factorization’, 2012, arXiv:1212.0308.Google Scholar
Fomin, S. and Zelevinsky, A., ‘The Laurent phenomenon’, Adv. Appl. Math. 28 (2002) no. 2, 119–144.CrossRefGoogle Scholar
Gaudry, P., Houtmann, T., Weng, A., Ritzenthaler, C. and Kohel, D., ‘The 2-adic CM method for genus 2 curves with application to cryptography’, Asiacrypt 2006, Lecture Notes in Computer Science 4284 (Springer, 2006) 114–129.CrossRefGoogle Scholar
Karatsuba, A. and Ofman, Y., ‘Multiplication of many-digital numbers by automatic computers’, Proc. USSR Acad. Sci. (1962) no. 145, 293–294.Google Scholar
Kedlaya, K. S., ‘Counting points on hyperelliptic curves using Monsky–Washnitzer cohomology’, J. Ramanujan Math. Soc. 16 (2001) 323–338.Google Scholar
Lauder, A., ‘Deformation theory and the computation of zeta functions’, Proc. Lond. Math. Soc. (3) 88 (2004) no. 3, 565–602; MR 2044050 (2005g:11166).CrossRefGoogle Scholar
Lercier, R. and Sirvent, T., ‘On Elkies subgroups of ℓ-torsion points in elliptic curves defined over a finite field’, J. Théor. Nombres Bordeaux 20 (2008) 783–797.CrossRefGoogle Scholar
Pollack, R. and Stevens, G., ‘Overconvergent modular symbols and p-adic L-functions’, Ann. Sci. Éc. Norm. Supér. (4) 44 (2011) no. 1, 1–42.Google Scholar
Rabin, M. O., ‘Computable algebra, general theory and theory of computable fields’, Trans. Amer. Math. Soc. 95 (1960) 341–360.Google Scholar
Rockafellar, R. T., Variational analysis, Grundlehren der Mathematischen Wissenschaften 317 (Springer, 1997).Google Scholar
Schneider, P., p-adic Lie groups, Grundlehren der Mathematischen Wissenschaften 344 (Springer, Berlin, 2011).CrossRefGoogle Scholar
Somos, M., ‘Problem 1470’, Crux Mathematicorum 15 (1989) 208.Google Scholar
Stein, W. et al. , Sage mathematics software, The Sage Development Team, 2005–2013,http://www.sagemath.org.Google Scholar
van der Hoeven, J., ‘Relax, but don’t be too lazy’, J. Symbolic Comput. 34 (2002) no. 6, 479–542.CrossRefGoogle Scholar
van der Hoeven, J., ‘New algorithms for relaxed multiplication’, J. Symbolic Comput. 42 (2007) no. 8, 792–802.CrossRefGoogle Scholar