finding short lattice vectors within mordell's inequality
The celebrated Lenstra-Lenstra-Lovsz lattice basis reduction algorithm (LLL) can naturally be viewed as an algorithmic version of Hermite's inequality on Hermite's constant. We present a polynomial-time blockwise reduction algorithm based on duality which can similarly be viewed as an algorithmic version of Mordell's inequality on Hermite's constant. This achieves a better and more natural approximation factor for the shortest vector problem than Schnorr's algorithm and its transference variant by Gama, Howgrave-Graham, Koy and Nguyen. Furthermore, we show that this approximation factor is essentially tight in the worst case.
lll schnorr's algorithm lattice reduction slide reduction transference reduction.