Despite its popularity, the Lenstra Lenstra Lovász reduction algorithm remains mysterious in many ways. It has been widely reported that it behaves much more nicely than what could be expected from the worst-case proved bounds, both in terms of the running time and the output quality.

In this talk, after a few reminders on the LLL algorithm itself, we investigate this puzzling statement. We discuss what is meant by lattice reduction on the average, and we present extensive experiments on the average case behaviour of LLL, to give a clearer picture of the differences/similarities between the average and worst cases. We will focus on three main points: the running-time, the output quality and the numerical behaviour.