Topics in computational algebraic number theory
Karim Belabas1
1 Mathématiques–Bâtiment 425 Université Paris–Sud F–91405 Orsay Cedex
Journal de théorie des nombres de Bordeaux, Tome 16 (2004) no. 1, pp. 19-63.

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.

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 .

DOI : 10.5802/jtnb.433
Classification : 11Y40
Mots-clés : class field theory, algorithmic number theory

Karim Belabas 1

1 Mathématiques–Bâtiment 425 Université Paris–Sud F–91405 Orsay Cedex 
@article{JTNB_2004__16_1_19_0,
     author = {Karim Belabas},
     title = {Topics in computational algebraic number theory},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {19--63},
     publisher = {Universit\'e Bordeaux 1},
     volume = {16},
     number = {1},
     year = {2004},
     doi = {10.5802/jtnb.433},
     mrnumber = {2145572},
     zbl = {1078.11071},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.433/}
}
TY  - JOUR
AU  - Karim Belabas
TI  - Topics in computational algebraic number theory
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2004
SP  - 19
EP  - 63
VL  - 16
IS  - 1
PB  - Université Bordeaux 1
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.433/
DO  - 10.5802/jtnb.433
LA  - en
ID  - JTNB_2004__16_1_19_0
ER  - 
%0 Journal Article
%A Karim Belabas
%T Topics in computational algebraic number theory
%J Journal de théorie des nombres de Bordeaux
%D 2004
%P 19-63
%V 16
%N 1
%I Université Bordeaux 1
%U https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.433/
%R 10.5802/jtnb.433
%G en
%F JTNB_2004__16_1_19_0
Karim Belabas. Topics in computational algebraic number theory. Journal de théorie des nombres de Bordeaux, Tome 16 (2004) no. 1, pp. 19-63. doi : 10.5802/jtnb.433. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.433/

[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 K2𝒪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 ℚ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

  • Andrea Lesavourey; Thomas Plantard; Willy Susilo Improved computation of polynomial roots over number fields when using complex embeddings, Journal of Computational Algebra, Volume 12 (2024), p. 19 (Id/No 100026) | DOI:10.1016/j.jaca.2024.100026 | Zbl:7975287
  • M. J. Uray Algebraic number fields and the LLL algorithm, Journal of Symbolic Computation, Volume 121 (2024), p. 21 (Id/No 102261) | DOI:10.1016/j.jsc.2023.102261 | Zbl:1539.11154
  • Karim Belabas L’algorithmique de la théorie algébrique des nombres, Journées mathématiques X-UPS (2024), p. 89 | DOI:10.5802/xups.2005-02
  • Karim Belabas; Denis Simon Power detection over number fields, Mathematics of Computation, Volume 93 (2024) no. 348, pp. 1953-1961 | DOI:10.1090/mcom/3913 | Zbl:1553.11119
  • Przemysław Koprowski; Beata Rothkegel The anisotropic part of a quadratic form over a number field, Journal of Symbolic Computation, Volume 115 (2023), pp. 39-52 | DOI:10.1016/j.jsc.2022.07.003 | Zbl:1511.11039
  • Daniel J. Bernstein Fast norm computation in smooth-degree abelian number fields, Research in Number Theory, Volume 9 (2023) no. 4, p. 57 (Id/No 82) | DOI:10.1007/s40993-022-00402-0 | Zbl:1532.11170
  • Werner Bley; Tommy Hofmann; Henri Johnston Computation of lattice isomorphisms and the integral matrix similarity problem, Forum of Mathematics, Sigma, Volume 10 (2022), p. 36 (Id/No e87) | DOI:10.1017/fms.2022.74 | Zbl:1507.11101
  • Alice Pellet-Mary; Damien Stehlé On the hardness of the NTRU problem, Advances in cryptology – ASIACRYPT 2021. 27th international conference on the theory and application of cryptology and information security, Singapore, December 6–10, 2021. Proceedings. Part I, Cham: Springer, 2021, pp. 3-35 | DOI:10.1007/978-3-030-92062-3_1 | Zbl:1514.94125
  • Andrea Lesavourey; Thomas Plantard; Willy Susilo Short principal ideal problem in multicubic fields, Journal of Mathematical Cryptology, Volume 14 (2020), pp. 359-392 | DOI:10.1515/jmc-2019-0028 | Zbl:1462.94044
  • Dan Boneh; Darren Glass; Daniel Krashen; Kristin Lauter; Shahed Sharif; Alice Silverberg; Mehdi Tibouchi; Mark Zhandry Multiparty non-interactive key exchange and more from isogenies on elliptic curves, Journal of Mathematical Cryptology, Volume 14 (2020), pp. 5-14 | DOI:10.1515/jmc-2015-0047 | Zbl:1445.14043
  • Jens Bauch; Daniel J. Bernstein; Henry de Valence; Tanja Lange; Christine van Vredendaal Short generators without quantum computers: the case of multiquadratics, Advances in cryptology – EUROCRYPT 2017. 36th annual international conference on the theory and applications of cryptographic techniques, Paris, France, April 30 – May 4, 2017. Proceedings. Part I, Cham: Springer, 2017, pp. 27-59 | DOI:10.1007/978-3-319-56620-7_2 | Zbl:1410.11136
  • Jean-François Biasse; Claus Fieker; Tommy Hofmann On the computation of the HNF of a module over the ring of integers of a number field, Journal of Symbolic Computation, Volume 80 (2017), pp. 581-615 | DOI:10.1016/j.jsc.2016.07.027 | Zbl:1403.11084
  • Claus Fieker; William Hart; Tommy Hofmann; Fredrik Johansson Nemo/Hecke. Computer algebra and number theory packages for the Julia programming language, Proceedings of the 42nd international symposium on symbolic and algebraic computation, ISSAC 2017, Kaiserslautern, Germany, July 25–28, 2017, New York, NY: Association for Computing Machinery (ACM), 2017, pp. 157-164 | DOI:10.1145/3087604.3087611 | Zbl:1457.68325
  • Abdelmalek Azizi; Mohamed Talbi; Mohammed Talbi; Aïssa Derhem; Daniel C. Mayer The group Gal(k3(2)|k) for k = ℚ(−3,d) of type (3,3), International Journal of Number Theory, Volume 12 (2016) no. 07, p. 1951 | DOI:10.1142/s1793042116501207
  • Alexandre Gélin; Antoine Joux Reducing number field defining polynomials: an application to class group computations, LMS Journal of Computation and Mathematics, Volume 19A (2016), pp. 315-331 | DOI:10.1112/s1461157016000255 | Zbl:1391.11163
  • Karim Belabas; Jean-François Jaulent The logarithmic class group package in PARI/GP, Publications mathématiques de Besançon. Algèbre et théorie des nombres (2016), p. 5 | DOI:10.5802/pmb.o-1
  • Xavier-François Roblot Computing p-adic L-functions of totally real number fields, Mathematics of Computation, Volume 84 (2015) no. 292, pp. 831-874 | DOI:10.1090/s0025-5718-2014-02889-5 | Zbl:1333.11106
  • Nicholas Coxon List decoding of number field codes, Designs, Codes and Cryptography, Volume 72 (2014) no. 3, pp. 687-711 | DOI:10.1007/s10623-013-9803-x | Zbl:1321.94137
  • Daniel C. Mayer Quadratic p-ring spaces for counting dihedral fields, International Journal of Number Theory, Volume 10 (2014) no. 8, pp. 2205-2242 | DOI:10.1142/s1793042114500754 | Zbl:1323.11090
  • Daniel C. Mayer Principalization algorithm via class group structure, Journal de Théorie des Nombres de Bordeaux, Volume 26 (2014) no. 2, pp. 415-464 | DOI:10.5802/jtnb.874 | Zbl:1361.11073
  • Uri Shapira; Zhiren Wang Remarks on Euclidean minima, Journal of Number Theory, Volume 137 (2014), pp. 93-121 | DOI:10.1016/j.jnt.2013.09.014 | Zbl:1285.11135
  • Claus Fieker; Tommy Hofmann Computing in quotients of rings of integers, LMS Journal of Computation and Mathematics, Volume 17A (2014), pp. 349-365 | DOI:10.1112/s1461157014000291 | Zbl:1369.11104
  • Daniel C. Mayer The second p-class group of a number field, International Journal of Number Theory, Volume 8 (2012) no. 2, pp. 471-505 | DOI:10.1142/s179304211250025x | Zbl:1261.11070
  • Claus Fieker; Damien Stehlé Short bases of lattices over number fields, Algorithmic number theory. 9th international symposium, ANTS-IX, Nancy, France, July 19–23, 2010. Proceedings, Berlin: Springer, 2010, pp. 157-173 | DOI:10.1007/978-3-642-14518-6_15 | Zbl:1260.11084
  • Denis Simon Selected applications of LLL in number theory, The LLL algorithm. Survey and applications, Dordrecht: Springer, 2010, pp. 265-282 | DOI:10.1007/978-3-642-02295-1_7 | Zbl:1241.11001
  • Claus Fieker; Michael E. Pohst Dependency of units in number fields, Mathematics of Computation, Volume 75 (2006) no. 255, pp. 1507-1518 | DOI:10.1090/s0025-5718-06-01899-0 | Zbl:1097.11061

Cité par 26 documents. Sources : Crossref, zbMATH