zbMATH — the first resource for mathematics

Lattice basis reduction: Improved practical algorithms and solving subset sum problems. (English) Zbl 0829.90099
A practical floating point \(L^3\)-algorithm, \(L^3FP\), is presented that shows good stability according to empirical tests up to dimension 125 with integer entries of bit length up to 300. Moreover, a practical algorithm for block Korkin-Zolotarev reduction is proposed, and a variant of the Lenstra-Lenstra-Lovasz \(L^3\)-algorithm is introduced that uses “deep insertions”. For all the algorithms presented computational performance in solving subset sum problems is reported.
Reviewer: R.Euler (Brest)

90C10 Integer programming
90C27 Combinatorial optimization
11Y16 Number-theoretic algorithms; complexity
Full Text: DOI
[1] E.F. Brickell, ”Solving low density knapsacks,” in:Advances in Cryptology, Proceedings of CRYPTO’83 (Plenum Press, New York, 1984) pp. 25–37.
[2] B. Chor and R. Rivest, ”A knapsack-type public key cryptosystem based on arithmetic in finite fields,”IEEE Transactions on Information Theory IT-34 (1988) 901–909. · Zbl 0664.94011
[3] M.J. Coster, A. Joux, B.A. La Macchia, A.M. Odlyzko, C.P. Schnorr and J. Stern, ”An improved lowdensity subset sum algorithm,”Computational Complexity 2 (1992) 97–186. · Zbl 0768.11049 · doi:10.1007/BF01201999
[4] P. van Emde Boas, Another NP-complete partition problem and the complexity of computing short vectors in a lattice, Rept. 81-04, Dept. of Mathematics, Univ. of Amsterdam, 1981.
[5] M. Euchner, Praktische Algorithmen zur Gitterreduktion und Faktorisierung, Diplomarbeit Uni. Frankfurt (1991).
[6] A.M. Frieze, ”On the Lagarias–Odlyzko algorithm for the subset sum problem,”SIAM Journal on Computing 15 (2) (1986) 536–539. · Zbl 0592.94010 · doi:10.1137/0215038
[7] M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman and Company, New York, 1979). · Zbl 0411.68039
[8] J. Hastad, B. Just, J.C. Lagarias and C.P. Schnorr, ”Polynomial time algorithms for finding integer relations among real numbers,”SIAM Journal on Computing 18 (5) (October 1989) 859–881. · Zbl 0692.10033 · doi:10.1137/0218059
[9] C. Hermite, ”Extraits de lettres de M.Ch. Hermite à M. Jacobi sur différents objects de la théorie des nombres. Deuxième lettre du 6 août 1845,”Journal für die Reine und Angewandte Mathematik 40 (1850) 279–290. · doi:10.1515/crll.1850.40.279
[10] A. Joux and J. Stern, ”Improving the critical density of the Lagarias–Odlyzko attack against subset sum problems,”Proceedings of Fundamentals of Computation Theory, FCT’91, Ed. L. Budach, Springer LNCS 529 (1991) pp. 258–264. · Zbl 0925.90301
[11] R. Kannan, ”Minkowski’s convex body theory and integer programming,”Mathematics of Operations Research 12 (1987) 415–440. · Zbl 0639.90069 · doi:10.1287/moor.12.3.415
[12] A. Korkine and G. Zolotareff, ”Sur les formes quadratiques,”Mathematische Annalen 6 (1873) 366–389. · JFM 05.0109.01 · doi:10.1007/BF01442795
[13] J.C. Lagarias, H.W. Lenstra, Jr. and C.P. Schnorr, ”Korkin–Zolotarev bases and successive minima of a lattice and its reciprocal lattice,”Combinatorica 10 (1990) 333–348. · Zbl 0723.11029 · doi:10.1007/BF02128669
[14] J.C. Lagarias and A.M. Odlyzko, ”Solving low-density subset sum problems,”Journal of the Association for Computing Machinery 32(1) (1985) 229–246. · Zbl 0632.94007
[15] B.A. La Macchia, Basis reduction algorithms and subset sum problems, SM Thesis, Dept. of Elect. Eng. and Comp. Sci., Massachusetts Institute of Technology, Cambridge, MA (1991).
[16] H.W. Lenstra, Jr., ”Integer programming with a fixed number of variables,”Mathematics of Operations Research 8 (1983) 538–548. · Zbl 0524.90067 · doi:10.1287/moor.8.4.538
[17] A.K. Lenstra, H.W. Lenstra and L. Lovász, ”Factoring polynomials with rational coefficients,”Mathematische Annalen 261 (1982) 515–534. · Zbl 0488.12001 · doi:10.1007/BF01457454
[18] L. Lovász,An Algorithmic Theory of Numbers, Graphs and Convexity (SIAM Publications, Philadelphia, 1986).
[19] L. Lovász and H. Scarf, ”The generalized basis reduction algorithm,”Mathematics of Operations Research (1992). · Zbl 0774.90060
[20] A. M. Odlyzko, ”The rise and fall of knapsack cryptosystems. Cryptology and computational number theory,” in: C. Pomerance, ed.,American Mathematical Society, Proceedings of the Symposium on Applied Mathematics 42 (1990) 75–88. · Zbl 0733.94012
[21] A. Paz and C.P. Schnorr, Approximating integer lattices by lattices with cyclic factor groups,Automata, Languages, and Programming: 14th ICALP, Lecture Notes in Computer Science 267 (Springer-Verlag, NY, 1987) 386–393. · Zbl 0642.10031
[22] S. Radziszowski and D. Kreher, ”Solving subset sum problems with theL 3 algorithm,”J. Combin. Math. Combin. Comput. 3 (1988) 49–63. · Zbl 0657.90070
[23] C.P. Schnorr, ”A hierarchy of polynomial time lattice basis reduction algorithms,”Theoretical Computer Science 53 (1987) 201–224. · Zbl 0642.10030 · doi:10.1016/0304-3975(87)90064-8
[24] C.P. Schnorr, ”A more efficient algorithm for lattice basis reduction,”Journal of Algorithms 9 (1988) 47–62. · Zbl 0825.11015 · doi:10.1016/0196-6774(88)90004-1
[25] C.P. Schnorr, ”Factoring integers and computing discrete logarithms via diophantine approximation,”Proceedings EUROCRYPT’91, Brighton, May 1991, Springer LNCS 547 (1991) pp. 281–293. Final paper:DIMACS Series in discrete Mathematics and Theoretical Computer Science 13 (1993) pp. 172–181. · Zbl 0772.11045
[26] C.P. Schnorr and M. Euchner, ”Lattice basis reduction: improved algorithms and solving subset sum problems,”Proceedings of Fundamentals of Computation Theory, FCT’91, Ed. L. Budach, Springer LNCS 529 (1991) pp. 68–85 (preliminary version of this paper). · Zbl 0925.11049
[27] M. Seysen, ”Simultaneous reduction of a lattice basis and its reciprocal basis,”Combinatorica 13 (1993) 363–376. · Zbl 0801.11029 · doi:10.1007/BF01202355
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.