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, Volume 23 (1989) no. 3, pp. 345-376.
@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},
     pages = {345--376},
     publisher = {EDP-Sciences},
     volume = {23},
     number = {3},
     year = {1989},
     mrnumber = {1020479},
     zbl = {0692.10032},
     language = {fr},
     url = {http://archive.numdam.org/item/ITA_1989__23_3_345_0/}
}
TY  - JOUR
AU  - Vallée, Brigitte
TI  - La réduction des réseaux. Autour de l'algorithme de Lenstra, Lenstra, Lovász
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1989
SP  - 345
EP  - 376
VL  - 23
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1989__23_3_345_0/
LA  - fr
ID  - ITA_1989__23_3_345_0
ER  - 
%0 Journal Article
%A Vallée, Brigitte
%T La réduction des réseaux. Autour de l'algorithme de Lenstra, Lenstra, Lovász
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1989
%P 345-376
%V 23
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1989__23_3_345_0/
%G fr
%F 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, Volume 23 (1989) no. 3, pp. 345-376. http://archive.numdam.org/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

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 | Zbl

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 | Zbl

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

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

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

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 | Zbl

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 | Zbl

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

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 | Zbl

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

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 | Zbl

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 | Zbl

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

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

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 | Zbl

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