Ce texte est une version étendue des notes d’un cours que j’ai donné en janvier 2018 aux « Journées Nationales de Calcul Formel » (JNCF). Ce cours portait sur l’algorithmique sous-jacente à l’implémentation bas niveau des nombres -adiques sur machine. Il est divisé en deux grandes parties : dans un premier temps, nous présentons et comparons divers paradigmes couramment utilisés pour implémenter les nombres -adiques puis, dans un second temps, nous introduisons un cadre général permettant d’étudier la propagation de la précision dans le monde -adique puis nous l’appliquons dans plusieurs situations concrètes.
This document contains the notes of a lecture I gave at the “Journées Nationales du Calcul Formel(French) National Computer Algebra Days” (JNCF) on January 2017. The aim of the lecture was to discuss low-level algorithmics for -adic numbers. It is divided into two main parts: first, we present various implementations of -adic numbers and compare them and second, we introduce a general framework for studying precision issues and apply it in several concrete situations.
@article{CCIRM_2017__5_1_A2_0, author = {Xavier Caruso}, title = {Computations with $p$-adic numbers}, journal = {Les cours du CIRM}, note = {talk:2}, publisher = {CIRM}, volume = {5}, number = {1}, year = {2017}, doi = {10.5802/ccirm.25}, language = {en}, url = {https://ccirm.centre-mersenne.org/articles/10.5802/ccirm.25/} }
Xavier Caruso. Computations with $p$-adic numbers. Les cours du CIRM, Tome 5 (2017) no. 1, Exposé no. 2, 75 p. doi : 10.5802/ccirm.25. https://ccirm.centre-mersenne.org/articles/10.5802/ccirm.25/
[1] Jounaïdi Abdeljaoued and Henri Lombardi. Méthodes matricielles, introduction à la complexité algébrique. Springer Verlag, Berlin, Heidelberg (2004)
[2] Yvette Amice. Les nombres p-adiques. PUF (1975) | Zbl
[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 | MR
[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 -adique pour . 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 -adic numbers. J. Number Theor. Bordeaux 23 (2011), 541–577 | MR
[8] Jérémy Berthomieu and Romain Lebreton. Relaxed -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 | MR
[10] Richard Bird. A simple division-free algorithm for computing determinants. Information Processing Letters 111 (2011), 1072–1074 | MR
[11] Wieb Bosma, John Cannon, and Catherine Payoust. The Magma algebra system. I. The user language. J. Symbolic Comput. 24 (1997), 235–265 | MR
[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 . 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 | MR
[17] Xavier Caruso. Numerical stability of Euclidean algorithm over ultrametric fields. to appear at J. Number Theor. Bordeaux
[18] Xavier Caruso, David Roe and Tristan Vaccon. Tracking -adic precision. LMS J. Comp. and Math. 17 (2014), 274–294
[19] Xavier Caruso, David Roe and Tristan Vaccon. -adic stability in linear algebra. In ISSAC’15 (2015)
[20] Xavier Caruso, David Roe and Tristan Vaccon. Characteristic polynomials of -adic matrices. In preparation | Numdam
[21] Man-Duen Choi. Tricks or treats with the Hilbert matrix., Amer. Math. Monthly (1983), 301–312 | Zbl
[22] John Coates. On -adic -functions. Astérisque 177 (1989), 33–59 | Numdam
[23] Henri Cohen, A course in computational algebraic number theory, Springer Verlag, Berlin (1993)
[24] Pierre Colmez. Integration sur les variétés -adiques. Astérisque 248 (1998)
[25] Pierre Colmez, Fonctions d’une variable -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 | MR
[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 | MR
[30] Martin Fürer. Faster integer multiplication. SIAM J. Comput. 39 (2009), 979–1005 | MR
[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 -adic CM method for genus curves with application to cryptography. In Asiacrypt 2006, LNCS 4284, 114–129 | Numdam
[33] Joachim von zur Gathen and Jürgen Gerhard. Modern Computer Algebra. Cambridge University Press, Cambridge (2003)
[34] Fernando Gouvêa. Arithmetic of -adic modular forms. Lecture Notes in Math. 1304, Springer-Verlag, Berlin, New-York (1988)
[35] Fernando Gouvêa. -adic Numbers: An Introduction. Springer (1997)
[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 | MR
[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. | MR
[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 | MR | Zbl
[44] Joris van der Hoeven. New algorithms for relaxed multiplication. J. Symbolic Comput. 42 (2007), 792–802 | MR
[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)
[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 | MR | Zbl
[50] Kiran Kedlaya. -adic Differential Equations. Cambridge University Press (2010)
[51] Kiran Kedlaya and David Roe. Two specifications for -adic floating-point arithmetic: a Sage enhancement proposal. Personal communication
[52] Neal Koblitz. -adic Numbers, -adic Analysis, and Zeta-Functions. Graduate Texts in Math. 58, Berlin, New York, Springer-Verlag (1984) | Numdam
[53] Pierre Lairez and Tristan Vaccon, On -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 | MR
[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 | MR
[57] Reynald Lercier and Thomas Sirvent. On Elkies subgroups of -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 -adic arithmetic. In Parallel Processing: CONPAR 94-VAPP VI (1994), 313–323
[60] Kurt Mahler. An interpolation series for continuous functions of a -adic variable. J. reine und angew. Mathematik 199 (1958), 23–34 | MR
[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 | MR
[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 -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)
[70] Peter Schneider. -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)
[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 | MR
[79] Tristan Vaccon. Précision -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 | MR
[81] Andrew Wiles. Modular elliptic curves and Fermat’s Last Theorem. Ann. of Math. 141 (1995), 443–551 | MR
[82] Franz Winkler. Polynomial Algorithms in Computer Algebra. Springer Wien New Work (1996)
Cité par Sources :