  Lattice reduction algorithms have numerous applications in number theory,
algebra, as well as in cryptanalysis. The most famous algorithm for lattice
reduction is the LLL algorithm. In polynomial time it computes a reduced basis
with provable output quality. One early improvement of the LLL algorithm was
LLL with deep insertions (DeepLLL). The output of this version of LLL has
higher quality in practice but the running time seems to explode. Weaker
variants of DeepLLL, where the insertions are restricted to blocks, behave
nicely in practice concerning the running time. However no proof of polynomial
running time is known. In this paper PotLLL, a new variant of DeepLLL with
provably polynomial running time, is presented. We compare the practical
behavior of the new algorithm to classical LLL, BKZ as well as blockwise
variants of DeepLLL regarding both the output quality and running time.
