[4357] 이산 로그

%2021. 12. 5. 23:18에 작성된 글입니다%

4357번: 이산 로그

 

 

$B^L\equiv N\mathrm{mod}P$​
를 만족시키는 $L$을 찾자.

Babystep Giantstep으로도 알려진 Shanks’ Algorithm을 사용하면 된다.

$L=ax+b$​
$B^{ax+b}\equiv N\mathrm{mod}P$​
$B^{ax}\equiv B^{-b}N\mathrm{mod}P$​
페르마의 소정리에 따라

$B^{-1}\equiv B^{P-2}\mathrm{mod}P$​
이므로 역원은 쉽게 구할 수 있고, $B^{-b}$와 $b$를 $0$ ~ $(a-1)$까지 해시에 박은 뒤 $B^{ax}$에서 $x$를 하나씩 증가시키며 해당 값이 해시에 이미 존재하는지 찾으면 된다.

만약 찾았다면 $L=ax+b$.

$a$는 무난하게 $\sqrt{P}$로 두면 된다.