Topics in computational algebraic number theory

Belabas, Karim

Journal de théorie des nombres de Bordeaux, Tome 16 (2004) no. 1, pp. 19-63.

Nous décrivons des algorithmes efficaces pour les opérations usuelles de la théorie algorithmique des corps de nombres, en vue d’applications à la théorie du corps de classes. En particulier, nous traitons l’arithmétique élémentaire, l’approximation et l’obtention d’uniformisantes, le problème du logarithme discret, et le calcul de corps de classes via un élément primitif. Tout ces algorithmes ont été implantés dans le système Pari/Gp .

We describe practical algorithms from computational algebraic number theory, with applications to class field theory. These include basic arithmetic, approximation and uniformizers, discrete logarithms and computation of class fields. All algorithms have been implemented in the Pari/Gp system.

Classification : 11Y40
Mots clés : class field theory, algorithmic number theory

[1] B. Allombert, An efficient algorithm for the computation of Galois automorphisms. Math. Comp. To appear. | MR | Zbl

[2] E. Bach, J. Driscoll, & J. Shallit, Factor refinement. J. Algorithms 15 (1993), no. 2, 199–222. | MR | Zbl

[3] K. Belabas, A relative van Hoeij algorithm over number fields. J. Symbolic Comput. To appear. | MR | Zbl

[4] K. Belabas & H. Gangl, Generators and relations for $K_2{𝒪}_F$. K-Theory. To appear. | Zbl

[5] D. J. Bernstein, Factoring into coprimes in essentially linear time. J. Algorithms. To appear. | MR | Zbl

[6] J. Buchmann & H. W. Lenstra, Jr., Approximating rings of integers in number fields. J. Théor. Nombres Bordeaux 6 (1994), no. 2,  221–260. | Numdam | MR | Zbl

[7] J. Buchmann, A subexponential algorithm for the determination of class groups and regulators of algebraic number fields. Séminaire de Théorie des Nombres, Paris 1988–1989, Progr. Math., vol. 91, Birkhäuser, 1990, 27–41. | MR | Zbl

[8] J. Buchmann & F. Eisenbrand, On factor refinement in number fields. Math. Comp. 68 (1999), no. 225, 345–350. | MR | Zbl

[9] H. Cohen, A course in computational algebraic number theory, third ed., Springer-Verlag, 1996. | MR | Zbl

[10] H. Cohen, Advanced topics in computational number theory, Springer-Verlag, 2000. | MR | Zbl

[11] H. Cohen & F. Diaz y Diaz, A polynomial reduction algorithm. Sém. Théor. Nombres Bordeaux (2) 3 (1991), no. 2, 351–360. | Numdam | MR | Zbl

[12] H. Cohen, F. Diaz y Diaz, & M. Olivier, Subexponential algorithms for class group and unit computations. J. Symbolic Comput. 24 (1997), no. 3-4, 433–441, Computational algebra and number theory (London, 1993). | MR | Zbl

[13] H. Cohen & X.-F. Roblot, Computing the Hilbert class field of real quadratic fields Math. Comp. 69 (2000), no. 231, 1229–1244. | MR | Zbl

[14] M. Daberkow, C. Fieker, J. Klüners, M. Pohst, K. Roegner, M. Schörnig, & K. Wildanger, KANT V4, J. Symbolic Comput. 24 (1997), no. 3-4, 267–283, Computational algebra and number theory (London, 1993). | MR | Zbl

[15] L. Ducos, Optimizations of the subresultant algorithm. J. Pure Appl. Algebra 145 (2000), no. 2, 149–163. | MR | Zbl

[16] M. Elkenbracht-Huizing, An implementation of the number field sieve Experiment. Math. 5 (1996), no. 3, 231–253. | MR | Zbl

[17] C. Fieker, Computing class fields via the Artin map. Math. Comp. 70 (2001), no. 235, 1293–1303. | MR | Zbl

[18] C. Fieker & C. Friedrichs, On reconstruction of algebraic numbers. Algorithmic number theory (Leiden, 2000), LNCS, vol. 1838, Springer, 2000, 285–296. | MR | Zbl

[19] U. Fincke & M. Pohst, Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math. Comp. 44 (1985), no. 170,  463–471. | MR | Zbl

[20] D. Ford, S. Pauli, & X.-F. Roblot, A fast algorithm for polynomial factorization over ${\mathbb{Q}}_p$. J. Théor. Nombres Bordeaux 14 (2002), no. 1, 151–169. | Numdam | MR | Zbl

[21] X. Gourdon, Algorithmique du théorème fondamental de l’algèbre. Rapport de recherche 1852, INRIA, 1993.

[22] J. L. Hafner & K. S. McCurley, A rigorous subexponential algorithm for computation of class groups. J. Amer. Math. Soc. 2 (1989), no. 4, 837–850. | MR | Zbl

[23] J. Klüners, On computing subfields. A detailed description of the algorithm. J. Théor. Nombres Bordeaux 10 (1998), no. 2, 243–271. | Numdam | MR | Zbl

[24] D. E. Knuth, The art of computer programming. Vol. 2, second ed., Addison-Wesley Publishing Co., Reading, Mass., 1981, Seminumerical algorithms, Addison-Wesley Series in Computer Science and Information Processing. | MR | Zbl

[25] H. Koy & C.-P. Schnorr, Segment LLL-Reduction with Floating Point Orthogonalization. CaLC, LNCS, vol. 2146, Springer, 2001, 81–96. | MR | Zbl

[26] A. K. Lenstra, H. W. Lenstra, Jr., & L. Lovász, Factoring polynomials with rational coefficients. Math. Ann. 261 (1982), no. 4,  515–534. | MR | Zbl

[27] P. L. Montgomery, Square roots of products of algebraic numbers. Mathematics of Computation 1943–1993: a half-century of computational mathematics (Vancouver, BC, 1993). Proc. Sympos. Appl. Math., vol. 48, Amer. Math. Soc., 1994,  567–571. | MR | Zbl

[28] P. Nguyen, A Montgomery-like square root for the number field sieve. Algorithmic number theory (Portland, OR, 1998), Lecture Notes in Comput. Sci., vol. 1423, Springer, 1998, 151–168. | MR | Zbl

[29] PARI/GP, version 2.1.5, Bordeaux, 2003, http://pari.math.u-bordeaux.fr/.

[30] F. Rouillier & P. Zimmermann, Efficient isolation of a polynomial real roots. Journal of Computational and Applied Mathematics. To appear. | Zbl

[31] C.-P. Schnorr & M. Euchner, Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Programming 66 (1994), no. 2, Ser. A, 181–199. | MR | Zbl

[32] J. von zur Gathen & J. Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. | MR | Zbl