Center for diffusion of mathematic journals

 
 
 
 

Les cours du CIRM

Table of contents for this issue | Previous article
Xavier Caruso
Computations with $p$-adic numbers
Les cours du CIRM, 5 no. 1: Journées Nationales de Calcul Formel (2017), Exp. No. 2, 75 p., doi: 10.5802/ccirm.25
Article PDF

Résumé - Abstract

This document contains the notes of a lecture I gave at the “Journées Nationales du Calcul Formel” (JNCF) on January 2017. The aim of the lecture was to discuss low-level algorithmics for $p$-adic numbers. It is divided into two main parts: first, we present various implementations of $p$-adic numbers and compare them and second, we introduce a general framework for studying precision issues and apply it in several concrete situations.

Bibliography

[1] Jounaïdi Abdeljaoued and Henri Lombardi. Méthodes matricielles, introduction à la complexité algébrique. Springer Verlag, Berlin, Heidelberg (2004)  MR 2046056
[2] Yvette Amice. Les nombres p-adiques. PUF (1975)
[3] Micheal Bartholomew-Biggs, Steven Brown, Bruce Christianson and Laurence Dixon. Automatic differentiation of algorithms. Journal of Comp. and App. Math. 124 (2000), 171–190
[4] Christian Batut, Karim Belabas, Dominique Benardi, Henri Cohen and Michel Olivier. User’s guide to PARI-GP. (1985–2013).
[5] Laurent Berger. La correspondance de Langlands locale $p$-adique pour $\text{\rm GL}_2(\mathbb{Q}_p)$. Astérisque 339 (2011), 157–180
[6] Pierre Berthelot and Arthur Ogus. Notes on Crystalline Cohomology. Princeton University Press (1978)
[7] Jérémy Berthomieu, Joris van der Hoeven, and Grégoire Lecerf. Relaxed algorithms for $p$-adic numbers. J. Number Theor. Bordeaux 23 (2011), 541–577
[8] Jérémy Berthomieu and Romain Lebreton. Relaxed $p$-adic Hensel lifting for algebraic systems. In ISSAC’12 (2012), 59–66
[9] Bhargav Bhatt. What is... a Perfectoid Space? Notices of the Amer. Math. Soc. 61 (2014), 1082–1084
[10] Richard Bird. A simple division-free algorithm for computing determinants. Information Processing Letters 111 (2011), 1072–1074
[11] Wieb Bosma, John Cannon, and Catherine Payoust. The Magma algebra system. I. The user language. J. Symbolic Comput. 24 (1997), 235–265
[12] Alin Bostan, Frédéric Chyzak, Grégoire Lecerf, Bruno Salvy and Éric Schost. Differential equations for algebraic functions. In ISSAC’07 (2007), 25–32
[13] Alin Bostan, Laureano González-Vega, Hervé Perdry and Éric Schost. From Newton sums to coefficients: complexity issues in characteristic $p$. In MEGA’05 (2005)
[14] Olivier Brinon and Brian Conrad. CMI Summer School notes on p-adic Hodge theory. Available at http://math.stanford.edu/~conrad/papers/notes.pdf (2009)
[15] Joe Buhler and Kiran Kedlaya. Condensation of determinants and the Robbins phenomenon. Microsoft Research Summer Number Theory Day, Redmond (2012), available at http://kskedlaya.org/slides/microsoft2012.pdf
[16] Xavier Caruso. Random matrices over a DVR and LU factorization. J. Symbolic Comput. 71 (2015), 98–123
[17] Xavier Caruso. Numerical stability of Euclidean algorithm over ultrametric fields. to appear at J. Number Theor. Bordeaux  MR 3682477
[18] Xavier Caruso, David Roe and Tristan Vaccon. Tracking $p$-adic precision. LMS J. Comp. and Math. 17 (2014), 274–294
[19] Xavier Caruso, David Roe and Tristan Vaccon. $p$-adic stability in linear algebra. In ISSAC’15 (2015)
[20] Xavier Caruso, David Roe and Tristan Vaccon. Characteristic polynomials of $p$-adic matrices. In preparation
[21] Man-Duen Choi. Tricks or treats with the Hilbert matrix., Amer. Math. Monthly (1983), 301–312
[22] John Coates. On $p$-adic $L$-functions. Astérisque 177 (1989), 33–59
[23] Henri Cohen, A course in computational algebraic number theory, Springer Verlag, Berlin (1993)  MR 1228206
[24] Pierre Colmez. Integration sur les variétés $p$-adiques. Astérisque 248 (1998)  MR 1645429
[25] Pierre Colmez, Fonctions d’une variable $p$-adique, Astérisque 330 (2010), 13–59
[26] Marc Daumas, Jean-Michel Muller et al. Qualité des Calculs sur Ordinateur. Masson, Paris (1997)
[27] Roberto Dvornicich and Carlo Traverso. Newton symmetric functions and the arithmetic of algebraically closed fields. In AAECC-5, LNCS 356, Springer, Berlin (1989), 216–224
[28] David Eisenbud. Commutative Algebra: with a view toward algebraic geometry. Springer Science & Business Media 150 (1995)
[29] Sergey Fomin and Andrei Zelevinsky. The Laurent phenomenon. Advances in Applied Math. 28 (2002), 119–144
[30] Martin Fürer. Faster integer multiplication. SIAM J. Comput. 39 (2009), 979–1005
[31] Alexander Grothendieck et al. Séminaire de géométrie algébrique du Bois-Marie. (1971–1977)
[32] Pierrick Gaudry, Thomas Houtmann, Annegret Weng, Christophe Ritzenthaler and David Kohel. The $2$-adic CM method for genus $2$ curves with application to cryptography. In Asiacrypt 2006, LNCS 4284, 114–129
[33] Joachim von zur Gathen and Jürgen Gerhard. Modern Computer Algebra. Cambridge University Press, Cambridge (2003)
[34] Fernando Gouvêa. Arithmetic of $p$-adic modular forms. Lecture Notes in Math. 1304, Springer-Verlag, Berlin, New-York (1988)  MR 1027593
[35] Fernando Gouvêa. $p$-adic Numbers: An Introduction. Springer (1997)  MR 1488696
[36] Über eine neue Begründung der Theorie der algebraischen Zahlen. Jahresbericht der Deutschen Mathematiker-Vereinigung 6 (1897), 83–88
[37] James Hafner and Kevin McCurley. Asymptotically fast triangularization of matrices over rings. SIAM Journal of Comp. 20 (1991), 1068–1083
[38] David Harari. Zéro-cycles et points rationnels sur les fibrations en variétés rationnellement connexes (d’après Harpaz et Wittenberg). Séminaire Bourbaki, Exp. 1096, Astérisque 380 (2016), 231–262
[39] Yonatan Harpaz and Olivier Wittenberg. On the fibration method for zero-cycles and rational points. Ann. of Math. 183 (2016), 229–295.
[40] David Harvey, Joris van der Hoeven and Grégoire Lecerf. Even faster integer multiplication. J. Complexity 36 (2015), 1–30
[41] Francis Hilbebrand. Introduction to Numerical Analysis. McGraw-Hill, New York (1956)
[42] Joris van der Hoeven. Lazy multiplication of formal power series. In ISSAC’97 (1997), 17–20
[43] Joris van der Hoeven. Relax, but don’t be too lazy. J. Symbolic Comput. 34 (2002), 479–542
[44] Joris van der Hoeven. New algorithms for relaxed multiplication. J. Symbolic Comput. 42 (2007), 792–802
[45] Joris van der Hoeven, Grégoire Lecerf and Bernard Mourrain The Mathemagix Language, 2002–2012
[46] Alston Householder, The Theory of Matrices in Numerical Analysis. (1975)  MR 378371
[47] IEEE Computer Society. IEEE Standard for Floating-Point Arithmetic, IEEE Standard 754-2008. IEEE Computer Society, New York (2008)
[48] Erich Kaltofen and Gilles Villard. On the complexity of computing determinants. Comp. Complexity 13 (2005), 91–130
[49] Kiran Kedlaya. Counting points on hyperelliptic curves using Monsky–Washnitzer cohomology. J. Ramanujan Math. Soc. 16 (2001), 323–338
[50] Kiran Kedlaya. $p$-adic Differential Equations. Cambridge University Press (2010)  MR 2663480
[51] Kiran Kedlaya and David Roe. Two specifications for $p$-adic floating-point arithmetic: a Sage enhancement proposal. Personal communication
[52] Neal Koblitz. $p$-adic Numbers, $p$-adic Analysis, and Zeta-Functions. Graduate Texts in Math. 58, Berlin, New York, Springer-Verlag (1984)
[53] Pierre Lairez and Tristan Vaccon, On $p$-adic differential equations with separation of variables. In ISSAC’16 (2016)
[54] Alan Lauder. Deformation theory and the computation of zeta functions. Proc. London Math. Soc. 88 (2004), 565–602
[55] Romain Lebreton. Relaxed Hensel lifting of triangular sets. In MEGA´13 (2013)
[56] Arjen Lenstra, Hendrik Lenstra and László Lovász. Factoring polynomials with rational coefficients. Math. Ann. 261 (1982), 515–534
[57] Reynald Lercier and Thomas Sirvent. On Elkies subgroups of $\ell $-torsion points in elliptic curves defined over a finite field. J. Number Theor. Bordeaux 20 (2008), 783–797
[58] Bernard Le Stum. Rigid cohomology. Cambridge University Press (2007)
[59] Carla Limongelli and Roberto Pirastu. Exact solution of linear systems over rational numbers by parallel $p$-adic arithmetic. In Parallel Processing: CONPAR 94-VAPP VI (1994), 313–323
[60] Kurt Mahler. An interpolation series for continuous functions of a $p$-adic variable. J. reine und angew. Mathematik 199 (1958), 23–34
[61] Yuri Manin. Le groupe de Brauer-Grothendieck en géométrie diophantienne. In Actes du Congrés International des Mathématiciens (Nice, 1970), Tome 1, Gauthier-Villars, Paris (1971), 401–411
[62] Jean-Michel Muller. Arithmétique des ordinateurs. Masson, Paris (1989)
[63] Jean-Michel Muller et al. Handbook of floating-point arithmetic. Birkhauser, Boston (2009)
[64] Richard Neidinger, Introduction to Automatic Differentiation and MATLAB Object-Oriented Programming. SIAM Review 52 (2010), 545–563
[65] Jurgen Neurkich. Algebraic Number Theory. Springer, Berlin, New York (1999)
[66] Jurgen Neurkich, Class Field Theory. The Bonn lectures. Edited by Alexander Schmidt. Springer, Berlin, London (2013)
[67] Alain Robert. A course in $p$-adic analysis. Springer Science & Business Media 198 (2000)
[68] R. Tyrell Rockafellar. Variational Analysis. Grundlehren der Mathematischen Wissenschaften 317, Springer-Verlag (1997)
[69] Pierre Samuel. Algebraic theory of numbers. Paris, Hermann (1972)  MR 265266
[70] Peter Schneider. $p$-Adic Lie groups. Grundlehren der mathematischen Wissenschaften 344. Springer, Berlin (2011)
[71] Peter Scholze. Perfectoid spaces: A survey. Current Developments in Mathematics (2012)
[72] Peter Scholze. Perfectoid spaces and their Applications. Proceedings of the ICM 2014 (2014)  MR 3728623
[73] Arnold Schönhage, The fundamental theorem of algebra in terms of computational complexity. Technical report, Univ. Tübingen (1982)
[74] Jean-Pierre Serre. Corps locaux. Hermann Paris (1962)
[75] Jean-Pierre Serre. Cours d’arithmétique. PUF (1970)
[76] Michael Somos. Problem 1470. Crux Mathematicorum 15 (1989), 208–208.
[77] William Stein et al. Sage Mathematics Software, The Sage Development Team, 2005–2017.
[78] Richard Taylor and Andrew Wiles. Ring theoretic properties of certain Hecke algebras. Ann. of Math. 141 (1995), 553–572
[79] Tristan Vaccon. Précision $p$-adique. PhD Thesis (2015). Available at https://tel.archives-ouvertes.fr/tel-01205269
[80] André Weil. Numbers of solutions of equations in finite fields. Bull. Amer. Math. Soc. 55 (1949), 497–508
[81] Andrew Wiles. Modular elliptic curves and Fermat’s Last Theorem. Ann. of Math. 141 (1995), 443–551
[82] Franz Winkler. Polynomial Algorithms in Computer Algebra. Springer Wien New Work (1996)
Copyright Cellule MathDoc 2019 | Credit | Site Map