Lattice Basis Reduction

194 Lattice Basis Reduction

A few years ago, Hanrot and Stehl´e [54] considered a different improvement

to Kannan’s algorithm:

(1) Replace the enumeration procedures of Kannan a nd Helfrich, which

search over all integer points in an n-dimensional paralleliped, by a

call to the Fincke-Pohst algorithm, which searches over all integer

points in an n-dimensional ellipsoid of smaller volume. (The ratio

between the two volumes tends to 0 as n increases.)

(2) Use a more sophisticated analysis to obtain a smaller upper bound

on the numb er of integer points in the n-dimensiona l ellipso id.

This allows Hanrot and Stehl´e to improve the complexity factor n

n/