Solving a system of linear diophantine equations using the Hermite normal form of an integer matrix via the Havas-Majewski-Matthews LLL-based algorithm

A is a nonzero m × n matrix of integers, b is m × 1 matrix, X is n × 1. We solve the system of linear diophantine equations AX = b:

a11x1+⋯+a1nxn=b1
.
.
.
am1x1+⋯+amnxn=bm

using the Hermite normal form algorithm. The version used is the LLL-based algorithm of Havas-Majewski-Matthews, as this tends to give small solutions in the case when there is more than one solution X in integers.
We determine if there is a solution in integers and exhibit a solution Y. If there is more than one solution, we find all solutions X with ||X|| ≤ ||Y|| and find the solutions X with minimal length, using a modification of the Fincke-Pohst algorithm. See the note.

We use LLL parameter α = 1.

The augmented matrix can be entered either (i) as a string of m(n+1) integers separated by spaces, or
(ii) cut and pasted from a text file, with entries separated by spaces and each row ended by a newline.
The case of zero coeffient matrix is not dealt with.

    Enter m, the number of equations (≤ 50):
    Enter n, the number of unknowns (≤ 50):
    Enter the m × (n+1) augmented matrix :

Last modified 3rd November 2011
Return to main page