Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.22196 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910706823069696 |
|---|---|
| author | Kalbach, Alex Chinburg, Ted |
| author_facet | Kalbach, Alex Chinburg, Ted |
| contents | This is an expository paper intended to introduce the polynomial time lattice basis reduction algorithm first described by Arjen Lenstra, Hendrik Lenstra, and László Lovász in 1982. We begin by introducing the shortest vector problem, which motivates the underlying components of the LLL algorithm. Then, we introduce the details of the algorithm itself, followed by proofs of the correctness and runtime of the algorithm in complete detail, assuming only a basic linear algebra background and an understanding of big O notation. Finally, we apply the LLL algorithm to the shortest vector problem and explore other applications of the algorithm in various mathematical settings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_22196 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | LLL Algorithm for Lattice Basis Reduction Kalbach, Alex Chinburg, Ted Number Theory This is an expository paper intended to introduce the polynomial time lattice basis reduction algorithm first described by Arjen Lenstra, Hendrik Lenstra, and László Lovász in 1982. We begin by introducing the shortest vector problem, which motivates the underlying components of the LLL algorithm. Then, we introduce the details of the algorithm itself, followed by proofs of the correctness and runtime of the algorithm in complete detail, assuming only a basic linear algebra background and an understanding of big O notation. Finally, we apply the LLL algorithm to the shortest vector problem and explore other applications of the algorithm in various mathematical settings. |
| title | LLL Algorithm for Lattice Basis Reduction |
| topic | Number Theory |
| url | https://arxiv.org/abs/2410.22196 |