La réduction des réseaux. Autour de l'algorithme de Lenstra, Lenstra, Lovász
Vallée, Brigitte
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 23 (1989), p. 345-376 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1989-01-01
@article{ITA_1989__23_3_345_0,
     author = {Vall\'ee, Brigitte},
     title = {La r\'eduction des r\'eseaux. Autour de l'algorithme de Lenstra, Lenstra, Lov\'asz},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {23},
     year = {1989},
     pages = {345-376},
     mrnumber = {1020479},
     zbl = {0692.10032},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/ITA_1989__23_3_345_0}
}

Vallée, Brigitte. La réduction des réseaux. Autour de l'algorithme de Lenstra, Lenstra, Lovász. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 23 (1989) pp. 345-376. http://gdmltest.u-ga.fr/item/ITA_1989__23_3_345_0/

1. L. Babai, On Lovász's Lattice Reduction and the Nearest Lattice Point Problem, Combinatorica, vol. 5, 1985. | Zbl 0593.68030

2. A. Frieze, J. Hastad, R. Kannan, J. C. Lagarias et A. Shamir, Reconstructing Truncated Integer Variables Satisfying Linear Congruences,, in S.I.A.M. Journal on Computing (to appear). | MR 935340 | Zbl 0654.10006

3. A. Dupré, Journal de Mathématiques, vol.11, 1846, p. 41-64.

4. C. F. Gauss, Recherches Arithmétiques, Paris, 1807, réimprimé par Blanchard, Paris, 1953. | JFM 42.0236.19 | Zbl 0051.03003

4. J. Hastad, B. Just, J. C. Lagarias et C. P. Schnorr, Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers, Proceedings of S.T.A.C.S., Lecture Notes in Computer Science, 1986 | Zbl 0606.68033

6. B. Helfrich, Algorithms to Construct Minkowski and Hermite Reduced Bases, Theoretical Computer Science, vol. 41, 1985, p. 125-139. | MR 847673 | Zbl 0601.68034

7. J. W. S. Cassels, Rational Quadratic Forms, Academic Press, 1978. | MR 522835 | Zbl 0395.10029

8. E. Kaltofen et H. Rolletschek, Arithmetic in Quadratic Fields with Unique Factorization, Comptes rendus de EUROCAL'85, Lectures notes in Computer Science, 204, Springer-Verlag. | MR 826569 | Zbl 0596.12001

9. R. Kannan, Improved Algorithms for Integer programming and Related Lattice Problem, J.A.C.M., 1983, p. 193-206.

10. R. Kannan, H. W. Lenstra et L. Lovász, Polynomial Factorization and Bits of Algebraic and Some Transcendental Numbers, Mathematics of Computation, vol. 50, n° 181, 1988, p. 235-250. | MR 917831 | Zbl 0654.12001

11. J. C. Lagarias, Computational Complexity of Simultaneous Diophantine Approximation Problem, 23rd I.E.E.E. Symp. F.O.C.S., 1982. | MR 780377

12. J. C. Lagarias et A. Odlyzko, Solving Low-Density Subset Sum Problems, 24th I.E.E.E. Symp. F.O.C.S., 1983.

13. J. C. Lagarias, H. W. Lenstra et C. P. Schnorr, Korkine-Zolotarev Bases and Successive Minima of a Lattice and its Reciprocal Lattice, Technical Report, M.S.R.I. 07718-86, Mathematical Sciences Research Institute, Berkeley.

14. S. Landau et G. L. Miller, Solvability by Radicals is in Polynomial Time, 15th Annual A.C.M. Symposium on Theory of Computing, 1983.

15. A. K. Lenstra, H. W. Lenstra et L. Lovasz, Factoring Polynomial with Rational Coefficients, Math. Annalen, vol. 261, 1982, p. 513-534. | MR 682664 | Zbl 0488.12001

16. H. W. Lenstra, Integer Programming with a Fixed Number of Variables, Mathematics of Operations Research, vol 8, n° 4, nov. 1983. | MR 727410 | Zbl 0524.90067

17. L. Lovasz, An Algorithmic Theory of Numbers, Graphs and Convexity, Technical Report, Universitat Bonn.

18. A. Shamir, A Polynomial Time Algorithmfor Breahing theMerkle-Hellman Cryptosystem, 23rd I.E.E.E. Symp. F.O.C.S., 1982.

19. A. Schonhage, Factorization of Univariate Integer Polynomial by Diophantine Approximation and by an Improved Basis Reduction Algorithm, Proceedings of the 11th I.C.A.L.P., Antwerpen, 1984, Lecture Notes in Computer Science, Vol. 172, Springer, 1984. | MR 784270 | Zbl 0569.68030

20. C. P. Schnorr, A More efficient Algorithm for Lattice Basis Reduction, Proceedings of the 13th I.C.A.L.P., Rennes, 1986, Lecture Notes in Computer Science, vol. 226, Springer, 1986, dans Journal of Algorithms, 1987 (à paraître). | MR 864698 | Zbl 0595.68038

21. C. P. Schnorr, A Hierarchy of Polynomial Tume Lattice Basis Reduction Algorithms, Theoretical Computer Science, vol. 53, 1987, p. 201-224. | MR 918090 | Zbl 0642.10030

22. J. Stern, Lectures Notes, University of Singapore, 1986.

23. J. Stern, Secret Linear Congruential Generatorsare not Cryptographically Secure, 28th I.E.E.E. Symp. F. O. C. S., 1987.

24. B. Vallée, Provably fast integor factoring algorithm with quasi-uniform small quadratic residues, ACM. STOC 89, p. 98-106.

25. B. Vallée, Une approche géométrique de la réduction des réseaux enpetite dimension, Thèse de doctorat de l'Université de Caen (1986), résumé paru dans le Séminaire de Théorie des Nombres de Bordeaux (1986), et dans Proceedings of EUROCAL'87, Lecture notes in Computer Science, Springer (à paraître). | Zbl 0602.10022

26. B. Vallée, M. Girault et Ph. Toffin, HOW to Guess l-th Roots Modulo n by Reducing Lattice Bases, Prépublications de l'Université de Caen, 1988, First International Joint Conference of I.S.S.A.C.-88 and A.A.E.C.C-6, juillet 1988(soumis). | MR 1008518 | Zbl 0692.10005

27. P. Van Emde Boas, Another NP-Complete Partition Problem and the Complexity of Computing Short Vectors in a Lattice, Rep. MI, U.V.A. 81-04, Amsterdam, 1981