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 3-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 3-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 3-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.
Acknowledgements
The author thank the Research Council of Sharif University of Technology for its support.