仕事でLLLは使っていないです。 LLL(Lenstra–Lenstra–Lovász lattice basis reduction algorithm、Lenstra–Lenstra–Lovász格子基底簡約アルゴリズム)は、CTFのCryptoジャンルで、RSAや楕円曲線の次くらいの中難易度の問題に出てくる。昨年末に開催されたSECCON CTF 2021では、Cryptoの6問中3問がLLLを使う問題だった。SECCON CTF 2021の作問に関わり、テスターとしてLLLを使う問題を解いたりレビューのやりとりを眺めていたりして、だいぶLLLが理解できたので、それらの問題の解説と合わせてまとめておく。 LLL Lenstra–Lenstra–Lovász lattice basis reduction algorithm - Wikipedia ベクトルの集合 $\mathbf{B