×

Relaxed algorithms for \(p\)-adic numbers. (English. French summary) Zbl 1247.11152

The main theme of this paper is to replace the standard zealous algorithms for \(p\)–adic numbers by new lazy algorithms. The standard algorithms compute with truncated \(p\)–adic expansions at a precision specified by the user, combined with Newton-Hensel lifting techniques; they have an efficient asymptotic cost. The principle of lazy algorithms appeared for formal power series. It has advantages to solve implicit equations and does not need any choice from the user, but the first versions had a more expensive asymptotic cost than zealous algorithms. Here the Authors apply progress due to van der Hoeven to the case of \(p\)–adic numbers. They study in detail the elementary arithmetical operations and the computation of \(k\)–th roots. They have implemented their algorithms in the C++ library algebraix of Mathemagix.

MSC:

11Y40 Algebraic number theory computations
11Y16 Number-theoretic algorithms; complexity
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] D. Bernstein, Removing redundancy in high precision Newton iteration. Available from , 2000.
[2] R. P. Brent and H. T. Kung, Fast algorithms for manipulating formal power series. Journal of the ACM 25 (1978), 581-595. · Zbl 0388.68052
[3] R. P. Brent, The complexity of multiprecision arithmetic. In R. S. Anderssen and R. P. Brent, editors, Complexity of computational problem solving, 126-165. University of Queensland Press, Brisbane, 1976.
[4] D. V. Chudnovsky and G. V. Chudnovsky, Computer algebra in the service of mathematical physics and number theory (Computers in mathematics, Stanford, Ca, 1986). In Lect. Notes in Pure and Applied Math. 125, 109-232. Dekker, New-York, 1990. · Zbl 0712.11078
[5] D. G. Cantor and E. Kaltofen, On fast multiplication of polynomials over arbitrary algebras. Acta Informatica 28 (1991), 693-701. · Zbl 0766.68055
[6] C. Durvye and G. Lecerf, A concise proof of the Kronecker polynomial system solver from scratch. Expositiones Mathematicae 26(2) (2008), 101 - 139. · Zbl 1134.14317
[7] S. De Smedt, \(p\)-adic arithmetic. The Mathematica Journal 9(2) (2004), 349-357.
[8] A. Fröhlich and J. C. Shepherdson, Effective procedures in field theory. Philos. Trans. Roy. Soc. London. Ser. A. 248 (1956), 407-432. · Zbl 0070.03502
[9] M. Fürer, Faster integer multiplication. In Proceedings of the Thirty-Ninth ACM Symposium on Theory of Computing (STOC 2007), 57-66, San Diego, California, 2007. · Zbl 1179.68198
[10] T. Granlund et al, GMP, the GNU multiple precision arithmetic library. Available from , 1991.
[11] J. von zur Gathen, Hensel and Newton methods in valuation rings. Math. Comp., 42(166) (1984), 637-661. · Zbl 0581.13001
[12] J. von zur Gathen and J. Gerhard, Modern computer algebra. Cambridge University Press, Cambridge, second edition, 2003. · Zbl 1055.68168
[13] J. van der Hoeven et al, Mathemagix. Available from , 2002.
[14] W. B. Hart and D. Harvey, FLINT 1.5.1: Fast library for number theory. Available from , 2009.
[15] J. van der Hoeven, Lazy multiplication of formal power series. In W. W. Küchlin, editor, Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation (ISSAC 1997), 17-20, Maui, Hawaii, July 1997. · Zbl 0932.68135
[16] J. van der Hoeven, Fast evaluation of holonomic functions. Theoretical Computer Science, 210 (1999), 199-215. · Zbl 0912.68081
[17] J. van der Hoeven, Fast evaluation of holonomic functions near and in singularities. J. Symbolic Comput. 31 (2001), 717-743. · Zbl 0982.65024
[18] J. van der Hoeven, Relax, but don’t be too lazy. J. Symbolic Comput. 34(6) (2002), 479-542. · Zbl 1011.68189
[19] J. van der Hoeven, Efficient accelero-summation of holonomic functions. J. Symbolic Comput. 42(4) (2007), 389-428. · Zbl 1125.34072
[20] J. van der Hoeven, New algorithms for relaxed multiplication. J. Symbolic Comput., 42(8) (2007), 792-802. · Zbl 1130.68103
[21] J. van der Hoeven, Relaxed resolution of implicit equations. Technical report, HAL, 2009. .
[22] J. van der Hoeven, Newton’s method and FFT trading. J. Symbolic Comput. 45(8) (2010), 857-878. · Zbl 1192.13017
[23] S. Katok, \(p\)-adic analysis compared with real. Student Mathematical Library 37. American Mathematical Society, Providence, RI, 2007. · Zbl 1147.12003
[24] N. Koblitz, \(p\)-adic numbers, \(p\)-adic analysis, and zeta-functions. Graduate Texts in Mathematics 58. Springer-Verlag, New York, second edition, 1984. · Zbl 0364.12015
[25] S. Lang, Algebra. Graduate Texts in Mathematics 211. Springer-Verlag, third edition, 2002. · Zbl 0984.00001
[26] The PARI Group, Bordeaux, PARI/GP, version 2.3.5, 2008. Available from .
[27] W. A. Stein et al, Sage Mathematics Software (Version 4.2.1). The Sage Development Team, 2009. Available from .
[28] A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen. Computing 7 (1971), 281-292. · Zbl 0223.68007
[29] P. S. Wang, Implementation of a \(p\)-adic package for polynomial factorization and other related operations. In EUROSAM 84 (Cambridge, 1984), Lecture Notes in Comput. Sci. 174, 86-99. Springer, Berlin, 1984. · Zbl 0563.12013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.