staple
Avec cedram.org

Rechercher dans le site

Table des matières de ce fascicule | Article précédent | Article suivant
Karim Belabas
Topics in computational algebraic number theory
Journal de théorie des nombres de Bordeaux, 16 no. 1 (2004), p. 19-63, doi: 10.5802/jtnb.433
Article PDF | Analyses MR 2145572 | Zbl 1078.11071 | 3 citations dans Cedram
Class. Math.: 11Y40
Mots clés: class field theory, algorithmic number theory

Résumé - Abstract

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 .

Bibliographie

[1] B. Allombert, An efficient algorithm for the computation of Galois automorphisms. Math. Comp. To appear.  MR 2034127 |  Zbl 01998525
[2] E. Bach, J. Driscoll, & J. Shallit, Factor refinement. J. Algorithms 15 (1993), no. 2, 199–222.  MR 1231441 |  Zbl 0784.11058
[3] K. Belabas, A relative van Hoeij algorithm over number fields. J. Symbolic Comput. To appear.  MR 2094619 |  Zbl 1137.11360
[4] K. Belabas & H. Gangl, Generators and relations for $K_2\mathcal{O}_F$. K-Theory. To appear.  Zbl 02129392
[5] D. J. Bernstein, Factoring into coprimes in essentially linear time. J. Algorithms. To appear.  MR 2108417 |  Zbl 02136072
[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. Cedram |  MR 1360644 |  Zbl 0828.11075
[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 1104698 |  Zbl 0727.11059
[8] J. Buchmann & F. Eisenbrand, On factor refinement in number fields. Math. Comp. 68 (1999), no. 225, 345–350.  MR 1613766 |  Zbl 0916.11067
[9] H. Cohen, A course in computational algebraic number theory, third ed., Springer-Verlag, 1996.  MR 1228206 |  Zbl 0786.11071
[10] H. Cohen, Advanced topics in computational number theory, Springer-Verlag, 2000.  MR 1728313 |  Zbl 0977.11056
[11] H. Cohen & F. Diaz y Diaz, A polynomial reduction algorithm. Sém. Théor. Nombres Bordeaux (2) 3 (1991), no. 2, 351–360. Cedram |  MR 1149802 |  Zbl 0758.11053
[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 1484490 |  Zbl 0880.68067
[13] H. Cohen & X.-F. Roblot, Computing the Hilbert class field of real quadratic fields Math. Comp. 69 (2000), no. 231, 1229–1244.  MR 1651747 |  Zbl 1042.11075
[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 1484479 |  Zbl 0886.11070
[15] L. Ducos, Optimizations of the subresultant algorithm. J. Pure Appl. Algebra 145 (2000), no. 2, 149–163.  MR 1733249 |  Zbl 0941.65044
[16] M. Elkenbracht-Huizing, An implementation of the number field sieve Experiment. Math. 5 (1996), no. 3, 231–253. Article |  MR 1426450 |  Zbl 0869.11101
[17] C. Fieker, Computing class fields via the Artin map. Math. Comp. 70 (2001), no. 235, 1293–1303.  MR 1826583 |  Zbl 0982.11074
[18] C. Fieker & C. Friedrichs, On reconstruction of algebraic numbers. Algorithmic number theory (Leiden, 2000), LNCS, vol. 1838, Springer, 2000, 285–296.  MR 1850612 |  Zbl 0990.11084
[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 777278 |  Zbl 0556.10022
[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. Cedram |  MR 1925995 |  Zbl 1032.11053
[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 1002631 |  Zbl 0702.11088
[23] J. Klüners, On computing subfields. A detailed description of the algorithm. J. Théor. Nombres Bordeaux 10 (1998), no. 2, 243–271. Cedram |  MR 1828244 |  Zbl 0935.11047
[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 633878 |  Zbl 0477.65002
[25] H. Koy & C.-P. Schnorr, Segment LLL-Reduction with Floating Point Orthogonalization. CaLC, LNCS, vol. 2146, Springer, 2001, 81–96.  MR 1903889 |  Zbl 1053.94013
[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 682664 |  Zbl 0488.12001
[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 1314892 |  Zbl 0819.11069
[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 1726068 |  Zbl 0983.11075
[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 1040.65041
[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 1297061 |  Zbl 0829.90099
[32] J. von zur Gathen & J. Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999.  MR 1689167 |  Zbl 0936.11069