A natural lattice basis problem with applications
HTML articles powered by AMS MathViewer
- by John D. Hobby PDF
- Math. Comp. 67 (1998), 1149-1161
Abstract:
Integer lattices have numerous important applications, but some of them may have been overlooked because of the common assumption that a lattice basis is part of the problem instance. This paper gives an application that requires finding a basis for a lattice defined in terms of linear constraints. We show how to find such a basis efficiently.References
- L. Babai, On Lovász’ lattice reduction and the nearest lattice point problem, Combinatorica 6 (1986), no. 1, 1–13. MR 856638, DOI 10.1007/BF02579403
- Charles Bigelow and Kris Holmes, The design of a Unicode font, Elec. Publish. 6 (1993), no. 3, 289–305.
- J. A. Buchmann and H. W. Lenstra Jr., Approximating rings of integers in number fields, J. Théor. Nombres Bordeaux 6 (1994), no. 2, 221–260 (English, with English and French summaries). MR 1360644, DOI 10.5802/jtnb.113
- Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
- Alan M. Frieze, Johan Håstad, Ravi Kannan, Jeffrey C. Lagarias, and Adi Shamir, Reconstructing truncated integer variables satisfying linear congruences, SIAM J. Comput. 17 (1988), no. 2, 262–280. Special issue on cryptography. MR 935340, DOI 10.1137/0217016
- E. R. Gansner, An infinite precision integer package for c++, AT&T Bell Laboratories technical memorandum, 1987.
- Eric Grosse and John D. Hobby, Improved rounding for spline coefficients and knots, Math. Comp. 63 (1994), no. 207, 175–194. MR 1240659, DOI 10.1090/S0025-5718-1994-1240659-8
- J. Håstad, B. Just, J. C. Lagarias, and C.-P. Schnorr, Polynomial time algorithms for finding integer relations among real numbers, SIAM J. Comput. 18 (1989), no. 5, 859–881. MR 1015261, DOI 10.1137/0218059
- Johan Håstad, Solving simultaneous modular equations of low degree, SIAM J. Comput. 17 (1988), no. 2, 336–341. Special issue on cryptography. MR 935343, DOI 10.1137/0217019
- John D. Hobby, Generating automatically tuned bitmaps from outlines, J. ACM 40 (1993), no. 1, 48–94.
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
- A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, DOI 10.1007/BF01457454
- H. W. Lenstra Jr., Integer programming with a fixed number of variables, Math. Oper. Res. 8 (1983), no. 4, 538–548. MR 727410, DOI 10.1287/moor.8.4.538
- Andrew M. Odlyzko, Cryptanalytic attacks on the multiplicative knapsack cryptosystem and on Shamir’s fast signature scheme, IEEE Trans. Inform. Theory 30 (1984), no. 4, 594–601. MR 755786, DOI 10.1109/TIT.1984.1056942
- M. Pohst, A modification of the LLL reduction algorithm, J. Symbolic Comput. 4 (1987), no. 1, 123–127. MR 908420, DOI 10.1016/S0747-7171(87)80061-5
- J. M. Pollard, A Monte Carlo method for factorization, Nordisk Tidskr. Informationsbehandling (BIT) 15 (1975), no. 3, 331–334. MR 392798, DOI 10.1007/bf01933667
- Adi Shamir, A polynomial-time algorithm for breaking the basic Merkle-Hellman cryptosystem, IEEE Trans. Inform. Theory 30 (1984), no. 5, 699–704. MR 781265, DOI 10.1109/TIT.1984.1056964
- K\B{o}kichi Sugihara, On finite-precision representations of geometric objects, J. Comput. System Sci. 39 (1989), no. 2, 236–247. Computational geometry. MR 1024129, DOI 10.1016/0022-0000(89)90046-9
Additional Information
- John D. Hobby
- Affiliation: Bell Laboratories, Lucent Technologies, 700 Mountain Ave., Murray Hill, New Jersey 07974
- Email: hobby@bell-labs.com
- Received by editor(s): January 13, 1995
- Received by editor(s) in revised form: May 1, 1996, and January 10, 1997
- © Copyright 1998 Lucent Technologies Inc.
- Journal: Math. Comp. 67 (1998), 1149-1161
- MSC (1991): Primary 11H55; Secondary 52C07, 68U15
- DOI: https://doi.org/10.1090/S0025-5718-98-00936-3
- MathSciNet review: 1458222