이어서 CCE2023에 출제되었던 the miracle문제로 연습을 해보자.
다른 부분들은 이 글의 목적에 있어서 지엽적이므로 LLL과 관련 있는 부분만 작성하겠다.
문제 상황의 식은 다음과 같다.
여기서 와 는 128bit이므로 896bit인 과 512bit인 에 비해 매우 작다. 따라서 에 대하여 LLL알고리즘을 사용할 수 있다.
위와 같이 행렬을 구성하고 LLL을 사용한다면, 결과를 이라 했을 때, 의 값이 에 곱해진 수일 것이며, 의 경우, 이 1인 를 찾으면 된다. (은 1번 곱해졌기 때문)
실제로 결과를 보자.
첫 번째 행이 찾고자 하는 행임을 알 수 있다. 잘 활용만 한다면 정말 사기적인 기술인 것 같다..
많은 도움이 되었습니다, 감사합니다.