A natural lattice basis problem with applications

Hobby, John

doi:10.1090/S0025-5718-98-00936-3

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