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:
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