86
Views
2
CrossRef citations to date
0
Altmetric
Original Articles

How can we solve a linear Diophantine equation by the basis reduction algorithm

Pages 1227-1234 | Published online: 19 Aug 2006
 

Abstract

The main difficulty in solving the systems of linear Diophantine equations is the very rapid growth of the intermediate results. Hence, it is important to design algorithms that restraint the growth of intermediate results. The use of the basis reduction algorithm for solving a linear Diophantine equation is examined in this paper. The motivation behind choosing the basis reduction is twofold. First the basis reduction allows us to work only with integers, which avoids the round-off problems. Second, the basis reduction finds short and nearly orthogonal vectors belonging to the lattice described by the basis. Then, we expect the general solution obtained by this basis will also be short. It is important to note that the basis reduction does not change the lattice, it only derives an alternative way of spanning it. Once we have obtained the vectors given by the reduced basis, we use them to find the general solution of the linear Diophantine equation.

Log in via your institution

Log in to Taylor & Francis Online

PDF download + Online access

  • 48 hours access to article PDF & online version
  • Article PDF can be downloaded
  • Article PDF can be printed
USD 61.00 Add to cart

Issue Purchase

  • 30 days online access to complete issue
  • Article PDFs can be downloaded
  • Article PDFs can be printed
USD 1,129.00 Add to cart

* Local tax will be added as applicable

Related Research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.