Lenstra-Lenstra-Lovász (LLL) 알고리즘은 1982년 Arjen Lenstra, Hendrik Lenstra, László Lovász 세 명의 수학자가 개발한 알고리즘으로 격자의 기저를 짧고, 직교에 가깝게 변환해 주는 격자 기저 축소알고리즘이다.
쉽게 말해 LLL은 공간을 설명하는 더 좋고 효율적인 좌표축을 찾아주는 도구라고 할 수 있다.
이 알고리즘은 원래 암호학을 위해 만들어진 것이 아니다. 초기에는 유리수 계수 다항식의 인수분해를 효율적으로 수행하기 위한 중간 단계로 고안되었다. 하지만 이 알고리즘이 가진 강력한 성질 덕분에 이후 정수론, 최적화 문제, 그리고 암호학 전반에 큰 변화를 가져왔다.
격자에서 가장 짧은 벡터를 찾는 문제인 SVP (Shortest Vector Problem)는 풀기 매우 어려운 NP-hard 문제이다. 즉, 차원이 커질수록 완벽한 정답을 찾는 데 걸리는 시간이 기하급수적으로 늘어난다.
하지만 LLL 알고리즘은 타협점을 제시했다. 완벽하게 제일 짧은 벡터는 아니더라도, 충분히 짧은 벡터를 매우 빠르게 찾아다.
이것이 LLL의 핵심 가치이다. LLL은 최초로 다항 시간 안에 작동하는 격자 기저 축소 알고리즘으로서, 수학적으로 완벽한 최단 벡터보다는 조금 길지만, 실용적으로 사용하기엔 충분히 짧은 근사 해를 제공한다.
격자란 유한 개의 기저 벡터들의 정수 선형결합으로 생성되는 이산적인 점들의 집합이다. 보다 엄밀하게 말하면 $\mathbb{R}^m$ 공간에서 선형독립인 기저 벡터 $b_1, b_2, \ldots, b_n$ (단, $n \leq m$)이 주어졌을 때 이들로 생성되는 격자 $L$은 다음과 같이 정의된다:
$$ L = \left\{ \sum_{i=1}^{n} x_i b_i \mid x_i \in \mathbb{Z} \right\} $$
여기서 $x_i$는 정수 계수이며 이는 격자가 연속적인 공간이 아닌 이산적인 점들의 집합임을 의미한다. 기저 벡터들은 행렬 $B = [b_1, \ldots, b_n]$로 표현할 수 있으며, 격자의 차원은 $n$이고 격자가 놓인 공간의 차원은 $m$이다.
2차원 평면에서 두 기저 벡터 $b_1 = (3, 1)$, $b_2 = (1, 2)$로 생성되는 격자를 생각해보자. 이를 행렬로 표현하면:
$$ B = \begin{bmatrix} 3 & 1 \\ 1 & 2 \end{bmatrix} $$