Geodesic
A rigorous subexponential algorithm for computation of class groups
Journal of the American Mathematical Society, Tome 02 (1989) no. 4, pp. 837-850

Voir la notice de l'article provenant de la source American Mathematical Society

Let $C( - d)$ denote the Gauss Class Group of quadratic forms of a negative discriminant $- d$ (or equivalently, the class group of the imaginary quadratic field $Q(\sqrt { - d} )$). We give a rigorous proof that there exists a Las Vegas algorithm that will compute the structure of $C( - d)$ with an expected running time of $L{(d)^{\sqrt 2 + o(1)}}$ bit operations, where $L(d) = {\text {exp}}(\sqrt {\log d\;\log \log d} )$. Thus, of course, also includes the computation of the class number $h( - d)$, the cardinality of $C( - d)$. 
@article{10_1090_S0894_0347_1989_1002631_0,
     author = {Hafner, James L. and McCurley, Kevin S.},
     title = {A rigorous subexponential algorithm for computation of class groups},
     journal = {Journal of the American Mathematical Society},
     pages = {837--850},
     publisher = {mathdoc},
     volume = {02},
     number = {4},
     year = {1989},
     doi = {10.1090/S0894-0347-1989-1002631-0},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1989-1002631-0/}
}
TY  - JOUR
AU  - Hafner, James L.
AU  - McCurley, Kevin S.
TI  - A rigorous subexponential algorithm for computation of class groups
JO  - Journal of the American Mathematical Society
PY  - 1989
SP  - 837
EP  - 850
VL  - 02
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1989-1002631-0/
DO  - 10.1090/S0894-0347-1989-1002631-0
ID  - 10_1090_S0894_0347_1989_1002631_0
ER  - 
%0 Journal Article
%A Hafner, James L.
%A McCurley, Kevin S.
%T A rigorous subexponential algorithm for computation of class groups
%J Journal of the American Mathematical Society
%D 1989
%P 837-850
%V 02
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1989-1002631-0/
%R 10.1090/S0894-0347-1989-1002631-0
%F 10_1090_S0894_0347_1989_1002631_0
Hafner, James L.; McCurley, Kevin S. A rigorous subexponential algorithm for computation of class groups. Journal of the American Mathematical Society, Tome 02 (1989) no. 4, pp. 837-850. doi: 10.1090/S0894-0347-1989-1002631-0

[1] Coppersmith, Don, Winograd, Shmuel Matrix multiplication via arithmetic progressions J. Symbolic Comput. 1990 251 280

[2] Domich, P. D., Kannan, R., Trotter, L. E., Jr. Hermite normal form computation using modulo determinant arithmetic Math. Oper. Res. 1987 50 59

[3] Goldfeld, Dorian Gauss’s class number problem for imaginary quadratic fields Bull. Amer. Math. Soc. (N.S.) 1985 23 37

[4] Hu, T. C., Young, R. D. Integer programming and network flows 1969

[5] Hua, Loo Keng Introduction to number theory 1982

[6] Kannan, Ravindran, Bachem, Achim Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix SIAM J. Comput. 1979 499 507

[7] Knuth, Donald E. The art of computer programming. Vol. 2 1981

[8] Lenstra, H. W., Jr. On the calculation of regulators and class numbers of quadratic fields 1982 123 150

[9] Mccurley, Kevin S. Cryptographic key distribution and computation in class groups 1989 459 479

[10] Narkiewicz, Wå‚Adyså‚Aw Classical problems in number theory 1986 363

[11] Pomerance, Carl Fast, rigorous factorization and discrete logarithm algorithms 1987 119 143

[12] Schã¶Nhage, A., Strassen, V. Schnelle Multiplikation grosser Zahlen Computing (Arch. Elektron. Rechnen) 1971 281 292

[13] Zantema, H. Class numbers and units 1982 213 234

[14] Schrijver, Alexander Theory of linear and integer programming 1986

[15] Seysen, Martin A probabilistic factorization algorithm with quadratic forms of negative discriminant Math. Comp. 1987 757 780

[16] Shanks, Daniel Class number, a theory of factorization, and genera 1971 415 440

[17] Shanks, Daniel Five number-theoretic algorithms 1973 51 70

[18] Wiedemann, Douglas H. Solving sparse linear equations over finite fields IEEE Trans. Inform. Theory 1986 54 62

Cité par Sources :