##### Department of Mathematics,

University of California San Diego

****************************

### Math 209: Number Theory Seminar

## Keegan Ryan

#### UC San Diego

## Fast Practical Lattice Reduction through Iterated Compression

##### Abstract:

We introduce a new lattice basis reduction algorithm with approximation guarantees analogous to the LLL algorithm and practical performance that far exceeds the current state of the art. We achieve these results by iteratively applying precision management techniques within a recursive algorithm structure and show the stability of this approach. We analyze the asymptotic behavior of our algorithm, and show that the heuristic running time is $O(n^{\omega}(C+n)^{1+\varepsi

[pre-talk at 1:20PM]

### April 20, 2023

### 2:00 PM

APM 6402 and Zoom; see https://www.math.ucsd.edu/~nts

****************************