### 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:
a_{11}x_{1}+⋯+a_{1n}x_{n}=b_{1}

.

.

.

a_{m1}x_{1}+⋯+a_{mn}x_{n}=b_{m}

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.

*Last modified 3rd November 2011*

Return to main page