thisisuser's study

이산 로그 문제(Discrete Logarithm Problem, DLP)어떠한 원시근 $g$와 $y$에 대해, $y \equiv g^k \pmod{p}$를 만족하는 최소의 자연수 $k$를 찾는 문제이다.아직까지 해결하기 어려운 문제로 남아 암호학 등에 주로 사용된다. 대충 간략하게 브루트포스 알고리즘으로 구성하면, 다음과 같다.def discreteLog(y, g, mod): cur = 1 cnt = 0 while True: cur = (cur * g) % mod cnt += 1 if cur == y: return cntprint(discreteLog(3, 2, 11)) 당연하지만 mod가 더럽게 커지면, 사실상 못 쓰는 코드다. Shanks' Algorithmsqrt d..

위수(계수, Order)$ n > 1, gcd(a, n) = 1 $ 일 때, $a^k \equiv 1 \pmod{n}$을 만족하는 가장 작은 양의 정수 $k$를법 $n$에 대한 a의 위수라고 한다. 오일러 정리 쓰면 $a ^ {\phi (n)} \equiv 1 \pmod{n}$이지만 종종 작은 게 더 있어서 이렇게 정의한다고 한다. 아래는 위수의 성질을 정리한 것이다. 증명은 생략.1. $a \equiv b \pmod{n}$이면 법 $n$에 대한 $a, b$의 위수는 같다.2. $a, n$이 서로소가 아니면 법 $n$에 대한 $a$의 위수는 존재하지 않는다.3. 법 $n$에 대한 $a$의 위수가 $k$이면 $a^h \equiv 1 \pmod{n}$인 모든 h에 대해 $k | h$4. 법 $n$에 대한 $..