A note on solving linear Diophantine systems by using L³-reduction algorithm

Abstract

The main difficulty in solving linear Diophantine systems is the very rapid growth of intermediate results which makes many algorithms, for solving linear Diophantine systems, impractical even for large computers. One way for controlling this growth is to use the L ³-reduction algorithm, introduced by Lenstra et al. [A.K. Lenstra, H.W. Lenstra, and L. Lovăsz, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), pp. 515–534.]. Esmaeili [H. Esmaeili, How can we solve a linear Diophantine equation by the basis reduction algorithm, Int. J. Comput. Math. 82 (2005), pp. 1227–1234.] proposed a method for obtaining the general integer solution of a linear Diophantine equation by using L ³-reduction algorithm. Here we propose a procedure for generalizing Esmaeili's method, to a method for obtaining the general integer solution of systems of linear Diophantine equations by using L ³-reduction algorithm. Then we consider the complexity issues and show that the generalized algorithm controls the growth of the intermediate results and the number of required arithmetic operations well. Finally, some illustrative numerical examples are given to show the efficiency of the proposed algorithm.

Keywords:

• systems of linear Diophantine equations
• linear Diophantine equations
• lattice basis reduction algorithms
• L ³-reduction algorithm
• euclidean algorithm

AMS Subject Classifications :

• 11D45
• 68WXX
• 34K17
• 68W40

Acknowledgements

The author thank the Research Council of Sharif University of Technology for its support.