지난번 글에서는 이산 로그 문제에 대해 다뤘으니 이번에는 소인수분해 문제를 해결하는 알고리즘에 대해 알아보자. 코드는 이전과 마찬가지로 아래와 같은 수정이 들어간 파이썬 문법을 따랐다.
양 끝을 명시적으로 나타내기 위해 range(st, ed+1) 대신 [st...ed]와 같은 표기를 사용했다. 파이썬에서 거듭제곱을 나타내는 a**b 대신 일반적으로 사용되는 a^b 표기를 사용했다. 지난 이산 로그 문제와는 달리 모두가 알 것이라 믿고 소인수분해 문제에 대한 자세한 설명은 생략한다. 또한 알고리즘 설계를 간단히 하기 위해 소인수분해 문제의 요구조건을 주어진 자연수 n에 대해, 1과 자기 자신(=n)을 제외한 약수를 발견하는 것으로 정했다.
암호학, 특히 공개키 기반 암호시스템은 주로 1)소인수분해 문제 혹은 2)이산 로그 문제를 기반으로 설계되는 경우가 많다. 그중 이산 로그 문제와 이를 해결하는 알고리즘에 대해 알아보자. 예시로 든 코드는 기본적으로 파이썬 문법을 따라 작성했으며 가독성을 위해 다음과 같은 부분을 수정했다.
파이썬에서 range(n)은 0부터 시작해 n이 아닌 n-1까지를 포함한다. 양 끝을 명시적으로 나타내기 위해 [st...ed]와 같은 표기를 사용했다. 파이썬에서 거듭제곱을 나타내는 a**b 대신 일반적으로 사용되는 a^b 표기를 사용했다. mod p에서의 역원을 a^(-1)로 표기했다. 실제 구현에서는 다음과 같이 구할 수 있다. 페르마 소정리에 의해 $a^{p-1} \equiv 1 \pmod p$이므로 $a\cdot a^{p-2} \equiv 1$에서 $a^{-1} \equiv a^{p-2}$ $p$가 소수가 아닌 경우, 확장 유클리드 알고리즘을 사용한다 이산 로그 문제 이산 로그 문제는 이산 대수 문제라고도 하며, 순환군 $\langle g \rangle$와 군의 원시근(primitive root) $g$, 그리고 $y \in \langle g \rangle$ 가 주어졌을 때, $y=g^k$를 만족하는 최소의 자연수 $k$를 찾는 문제이다. 암호학에서는 큰 소수 $p$에 대해 $p$로 나눈 나머지들의 모임인 $\mathbb{Z}_p^\ast$를 사용하는 경우가 많다.
얼마 전 코드포스에서 흥미로운 문제를 접했다. 대회 당시에는 풀지 못했는데, 에디토리얼을 읽어보던 중 뫼비우스 함수(Möbius function)에 대한 언급이 있어 이에 대해 좀더 자세히 알아보았다.
Möbius function의 정의 뫼비우스 함수(Möbius function)는 자연수 n에 대해 다음과 같이 정의된다. (\(p\)는 소수)
