%2021. 12. 5. 23:18에 작성된 글입니다%
4357번: 이산 로그
소수 P(2 ≤ P < 231), 정수 B(2 ≤ B < P), 정수 N(1 ≤ N < P)가 주어졌을 때, 밑을 B, 나머지를 P로 하는 N의 이산 로그를 구하는 프로그램을 작성하시오. 즉, 다음과 같은 조건을 만족하는 정수 L을 찾으
www.acmicpc.net
\(B^L\equiv N\mod P\)
를 만족시키는 \(L\)을 찾자.
Babystep Giantstep으로도 알려진 Shanks’ Algorithm을 사용하면 된다.
\(L=ax+b\)
\(B^{ax+b}\equiv N\mod P\)
\(B^{ax}\equiv B^{-b}N\mod P\)
페르마의 소정리에 따라
\(B^{-1}\equiv B^{P-2}\mod P\)
이므로 역원은 쉽게 구할 수 있고, \(B^{-b}\)와 \(b\)를 \(0\) ~ \((a-1)\)까지 해시에 박은 뒤 \(B^{ax}\)에서 \(x\)를 하나씩 증가시키며 해당 값이 해시에 이미 존재하는지 찾으면 된다.
만약 찾았다면 \(L=ax+b\).
\(a\)는 무난하게 \(\sqrt P\)로 두면 된다.