|
A natural lattice basis problem with applications
Author(s):
John
D.
Hobby.
Journal:
Math. Comp.
67
(1998),
1149-1161.
MSC (1991):
Primary 11H55;
Secondary 52C07, 68U15
Retrieve article in:
PDF
This article is available free of charge
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:
- 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
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
Email:
hobby@bell-labs.com
DOI:
10.1090/S0025-5718-98-00936-3
PII:
S 0025-5718(98)00936-3
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
Copyright of article:
Copyright
1998,
Lucent Technologies Inc.
|
Comments: webmaster@ams.org