La réduction des réseaux. Autour de l'algorithme de Lenstra, Lenstra, Lovász

 Access to full text

 Full (PDF)

1. 1. L. BABAI, On Lovász's Lattice Reduction and the Nearest Lattice Point Problem, Combinatorica, vol. 5, 1985. Zbl0593.68030
2. 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). Zbl0654.10006MR935340
3. 3. A. DUPRÉ, Journal de Mathématiques, vol.11, 1846, p. 41-64. 
4. 4. C. F. GAUSS, Recherches Arithmétiques, Paris, 1807, réimprimé par Blanchard, Paris, 1953. Zbl0051.03003JFM42.0236.19
5. 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 Zbl0606.68033
6. 6. B. HELFRICH, Algorithms to Construct Minkowski and Hermite Reduced Bases, Theoretical Computer Science, vol. 41, 1985, p. 125-139. Zbl0601.68034MR847673
7. 7. J. W. S. CASSELS, Rational Quadratic Forms, Academic Press, 1978. Zbl0395.10029MR522835
8. 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. Zbl0596.12001MR826569
9. 9. R. KANNAN, Improved Algorithms for Integer programming and Related Lattice Problem, J.A.C.M., 1983, p. 193-206. 
10. 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. Zbl0654.12001MR917831
11. 11. J. C. LAGARIAS, Computational Complexity of Simultaneous Diophantine Approximation Problem, 23rd I.E.E.E. Symp. F.O.C.S., 1982. MR780377
12. 12. J. C. LAGARIAS et A. ODLYZKO, Solving Low-Density Subset Sum Problems, 24th I.E.E.E. Symp. F.O.C.S., 1983. Zbl0632.94007
13. 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. Zbl0723.11029
14. 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. Zbl0586.12002
15. 15. A. K. LENSTRA, H. W. LENSTRA et L. LOVASZ, Factoring Polynomial with Rational Coefficients, Math. Annalen, vol. 261, 1982, p. 513-534. Zbl0488.12001MR682664
16. 16. H. W. LENSTRA, Integer Programming with a Fixed Number of Variables, Mathematics of Operations Research, vol 8, n° 4, nov. 1983. Zbl0524.90067MR727410
17. 17. L. LOVASZ, An Algorithmic Theory of Numbers, Graphs and Convexity, Technical Report, Universitat Bonn. Zbl0606.68039
18. 18. A. SHAMIR, A Polynomial Time Algorithmfor Breahing theMerkle-Hellman Cryptosystem, 23rd I.E.E.E. Symp. F.O.C.S., 1982. 
19. 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. Zbl0569.68030MR784270
20. 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). Zbl0595.68038MR864698
21. 21. C. P. SCHNORR, A Hierarchy of Polynomial Tume Lattice Basis Reduction Algorithms, Theoretical Computer Science, vol. 53, 1987, p. 201-224. Zbl0642.10030MR918090
22. 22. J. STERN, Lectures Notes, University of Singapore, 1986. 
23. 23. J. STERN, Secret Linear Congruential Generatorsare not Cryptographically Secure, 28th I.E.E.E. Symp. F. O. C. S., 1987. 
24. 24. B. VALLÉE, Provably fast integor factoring algorithm with quasi-uniform small quadratic residues, ACM. STOC 89, p. 98-106. 
25. 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). Zbl0602.10022
26. 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). Zbl0692.10005MR1008518
27. 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 

1. Ali Akhavi, Jean-François Marckert, Alain Rouault, On the reduction of a random basis