×

Lattice basis reduction for indefinite forms and an application. (English) Zbl 0848.68041

Summary: We present an analogue of the lattice basis reduction algorithm of A. K. Lenstra, H. W. Lenstra and L. Lovász for the case of an indefinite non-degenerate symmetric bilinear form. The algorithm produces a reduced basis with similar size properties as in the Euclidean case. As an application, we present an algorithm, which finds zero divisors in rings isomorphic to \(M_2 (\mathbb{Z})\) in polynomial time.

MSC:

68W10 Parallel algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cassels, J. W.S., Rational Quadratic Forms, (L.M.S. Monographs (1978), Academic Press: Academic Press New York) · Zbl 0496.10008
[2] Fincke, U.; Pohst, M., Improved methods for calculating vectors of short length in a lattice, including a complexity analysis, Math. Comp., 44, 463-471 (1985) · Zbl 0556.10022
[3] Frumkin, M. A., Polynomial time algorithms in the theory of linear diophantine equations, (Proc. FCT ’76. Proc. FCT ’76, Lecture Notes in Computer Science, vol. 56 (1976), Springer: Springer Berlin), 386-392 · Zbl 0367.10012
[4] Friedl, K.; Rónyai, L., Polynomial time solution of some problems in computational algebra, (Proc. 17th ACM STOC (1985)), 153-162
[5] Ivanyos, G.; Rónyai, L., Finding maximal orders in semisimple algebras over, Q, Comput. Complexity, 3, 245-261 (1993) · Zbl 0792.16020
[6] Lenstra, A. K.; Lenstra, H. W.; Lovász, L., Factoring polynomials with rational coefficients, Math. Ann., 261, 538-548 (1982) · Zbl 0477.68043
[7] Lovász, L., An algorithmic theory of numbers, graphs and convexity, Rheinische Friedrich-Wilhelms-Universität Bonn Report (1985)
[8] Pierce, R. S., Associative Algebras (1982), Springer: Springer Berlin · Zbl 0497.16001
[9] Pohst, M., A modification of the LLL reduction algorithm, J. Symbol. Comput., 4, 123-127 (1987) · Zbl 0629.10001
[10] Reiner, I., Maximal Orders (1975), Academic Press: Academic Press New York · Zbl 0305.16001
[11] Rónyai, L., Zero divisors in quaternion algebras, J. Algorithms, 9, 494-506 (1988) · Zbl 0662.12015
[12] Rónyai, L., Algorithmic properties of maximal orders in simple algebras over Q, Comput. Complexity, 2, 225-243 (1992) · Zbl 0787.16002
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.