These programs are meant to work with the
Number Theory Library of Victor Shoup.
See
http://www.shoup.net/

March 2003, edited in November 2003, March 2005.
We have added the following variants to the integer arithmetic LLL of NTL.

long Ximage(ZZ& det, mat_ZZ& B, mat_ZZ& U, long verbose)
This first does Victor's fast procedure "image", then straightens U a bit.
So it is like image, but with some time spent on a slightly better
transformation matrix U.

long HNF_image(mat_ZZ& B, mat_ZZ& U, long verbose)
long HNF_image(mat_ZZ& B, long verbose)
Computes a Hermite Normal Form.
HNF_image combines the best of "image" with the Havas-Majewski-Matthews
HNF algorithm to get a fast algorithm with good control on the size of U.
In other words, 
	HNF_image(mat_ZZ& B, mat_ZZ& U, long verbose) 
is basically the Chou Collins algorithm, which Chou and Collins showed to be 
well-behaved. 
And 
	HNF_image(mat_ZZ& B, long verbose) 
is our obvious extension to the case where one does not insist on independent 
generators. (Recall that Chou and Collins make the generators independent by 
grafting an identity matrix onto the input matrix.)
Why do so many people write that the straightforward algorithm explodes?
It strongly depends on the precise organisation.
HNF_image is pretty straightforward. 
Note that my complexity analysis also applies to the dependent case. Anyway, 
the dependent case is also an obvious corollary of the case treated by Chou
and Collins. Also note that the analysis of Chou Collins has much in common
with the analysis of the LLL algorithm.

long HNF_LLL(mat_ZZ& B, mat_ZZ& U, long a, long b, long verbose)
This first does HNF_image, then uses LLL to make the transformation U small.
Thus the end result is of the same nature, up to reversals of numberings,
as the end result of the Havas-Majewski-Matthews HNF algorithm.
We did not implement the Havas-Majewski-Matthews HNF algorithm, as we
believe HNF_LLL is an improvement.
(Just try putting me to shame by running tests.)

long XLLL(ZZ& det, mat_ZZ& B, mat_ZZ& U, long verbose)
long XLLL(ZZ& det, mat_ZZ& B, long verbose)
This is an alternative for LLL, relevant when there are enough dependencies
(and there is enough rank) to cause trouble for LLL.
XLLL starts with HNF_image, then lets LLL take over.
This may cause a drastic speadup, a better U, and in any case a
much better estimate for the size of U throughout the algorithm.

long XXLLL(ZZ& det, mat_ZZ& B, mat_ZZ& U, long a, long b, long verbose)
This first does XLLL and then applies LLL to make U small. So it takes
longer than XLLL.

How to read the tests.

We always used the same test set, as given in the file myin.
If you have more relevant test cases, just adapt the test programs and try them.

In HNFold_imageTest.out one must beware that two rather different situations
alternate: Those where the determinant is 1, so that the old algorithm knows
the answer is the identity matrix, and those where the determinant is large.
Looking at the latter cases one sees there is really no need for modular
arithmetic. There is no intermediate expression swell to speak of.