LLL on the Average
Phong Nguyen and Damien Stehlé
Abstract: Despite their popularity, lattice reduction algorithms remain
mysterious in many ways.
It has been widely reported that they behave much more nicely
than what was expected from the worst-case proved bounds,
both in terms of the running time and the output quality.
In this article, we investigate this puzzling statement by trying to
model the average case of lattice reduction algorithms,
starting with the celebrated Lenstra-Lenstra-Lovász algorithm (LLL).
We discuss what is meant by lattice reduction on the average,
and we present extensive experiments on the average case behavior of LLL,
in order to give a clearer picture of the differences/similarities
between the average and worst cases.
Our work is intended to clarify the practical behavior of LLL and
to raise theoretical questions on its average behavior.
Download: ps.gz,
pdf,
fplll-1.2.
Warning: The conference proceedings version contains a calculation mistake.
Throughout the paper, the 0.18 constant must be replaced by 0.25.
Homepage