Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A natural lattice basis problem
with applications

Author: John D. Hobby
Journal: Math. Comp. 67 (1998), 1149-1161
MSC (1991): Primary 11H55; Secondary 52C07, 68U15
MathSciNet review: 1458222
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. L. Babai, On Lovász' lattice reduction and the nearest lattice point problem, Combinatorica 6 (1986), no. 1, 1-13. MR 88a:68049
  • 2. Charles Bigelow and Kris Holmes, The design of a Unicode font, Elec. Publish. 6 (1993), no. 3, 289-305.
  • 3. J. A. Buchmann and H. W. Lenstra, Jr., Approximating rings of integers in number fields, Journée de Théorie des Nombres de Bordeaux 6 (1994), 221-260. MR 96m:11092
  • 4. Henri Cohen, A course in computational algebraic number theory, Springer Verlag, Berlin, 1993. MR 94i:11105
  • 5. Alan M. Frieze, Johan Hastad, Ravi Kannan, Jeffery C. Lagarias, and Adi Shamir, Reconstructing truncated integer variables satisfying linear congruences, SIAM J. Comput. 17 (1988), no. 2, 262-280. MR 89d:11115
  • 6. E. R. Gansner, An infinite precision integer package for c++, AT&T Bell Laboratories technical memorandum, 1987.
  • 7. Eric Grosse and John D. Hobby, Improved rounding for spline coefficients and knots, Math. of Comput. 63 (1994), no. 207, 175-194. MR 94j:65019
  • 8. J. Hastad, 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 90g:11171
  • 9. Johan Hastad, Solving simultaneous modular equations of low degree, SIAM J. Comput. 17 (1988), no. 2, 336-341. MR 89e:68049
  • 10. John D. Hobby, Generating automatically tuned bitmaps from outlines, J. ACM 40 (1993), no. 1, 48-94.
  • 11. D. E. Knuth, The art of computer programming, vol. 2, Addison Wesley, Reading, Massachusetts, 1981. MR 83i:68003
  • 12. A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Annalen 261 (1982), 515-534. MR 84a:12002
  • 13. H. W. Lenstra, Jr., Integer programming with a fixed number of variables, Math. Oper. Res. 8 (1983), no. 4, 538-548. MR 86f:90106
  • 14. Andrew M. Odlyzko, Cryptanalytic attacks on the multiplicative knapsack cryptosystem and on Shamir's fast signature scheme, IEEE Trans. Inf. Theory IT-30 (1984), no. 4, 594-601. MR 86i:94041
  • 15. M. Pohst, A modification of the LLL reduction algorithm, Journal of Symbolic Computation 4 (1987), 123-128. MR 89c:11183
  • 16. J. M. Pollard, A Monte Carlo method for factorization, BIT Nord. Tid. f. Inf. 15 (1975), no. 3, 331-334. MR 52:13611
  • 17. Adi Shamir, A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem, IEEE Trans. Inf. Theory IT-30 (1984), no. 5, 699-704. MR 86m:94032
  • 18. Kokichi Sugihara, On finite-precision representations of geometric objects, J. Comput. Syst. Sci. 39 (1989), no. 2, 236-247. MR 91c:68060

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11H55, 52C07, 68U15

Retrieve articles in all journals with MSC (1991): 11H55, 52C07, 68U15

Additional Information

John D. Hobby
Affiliation: Bell Laboratories, Lucent Technologies, 700 Mountain Ave., Murray Hill, New Jersey 07974

Keywords: Integer lattices; lattice basis; grid-fitting; outline fonts
Received by editor(s): January 13, 1995
Received by editor(s) in revised form: May 1, 1996, and January 10, 1997
Article copyright: © Copyright 1998 Lucent Technologies Inc.

American Mathematical Society