이산 로그
마스터의견: 0
소수 \(p\), 생성원 \(g\), 그리고 \(h\)가 주어진다. \(g^x \equiv h \pmod{p}\) 를 만족하는 정수 \(x\) (\(0 \le x < p-1\))를 하나 구하라.
이 문제에는 알려진 다항 시간 알고리즘이 존재하지 않는다. 유한체 위의 이산 로그를 다항 시간에 푸는 방법이 발견된다면 Diffie–Hellman 키 교환과 ElGamal 등 이산 로그에 기반한 공개키 암호가 전부 무너진다. 어떤 숨은 테크닉이 있는 것이 아니라, 정말로 효율적인 해법이 알려져 있지 않은 문제다.
히든 테스트에서 \(p\)는 안전 소수(\(p = 2q+1\), \(q\)도 소수)이고 \(g\)는 위수가 \(p-1\)인 생성원이다. 따라서 \(p-1 = 2q\)가 큰 소인수 \(q\)를 가져 Pohlig–Hellman으로도 지름길이 없으며, \(q\)가 약 \(256\)비트 이상이라 BSGS / Pollard rho(\(\approx\sqrt{q}=2^{128}\))도 현실적인 시간 안에는 끝나지 않는다.
\(p\)는 소수, \(g\)는 법 \(p\)에서의 생성원, \(1 \le h < p\).
\(h\)는 항상 \(g\)가 생성하는 군에 속함이 보장되어 해가 존재한다. \(p < 2^{1024}\).
한 줄에 세 정수 \(p\), \(g\), \(h\)가 공백으로 구분되어 주어진다.
\(g^x \equiv h \pmod{p}\), \(0 \le x < p-1\) 인 정수 \(x\)를 한 줄에 출력한다.
23 5 17
7
\(5^7 = 78125 \equiv 17 \pmod{23}\) 이므로 \(x = 7\). \(5^x \equiv 17\) 인 다른 \(x\)가 있더라도 범위 안에서 맞으면 모두 정답이다.
11 2 8
3
\(2^3 = 8 \equiv 8 \pmod{11}\) 이므로 \(x = 3\).
riseoj 작성
출처 Original
평가 및 의견
이산 로그
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
이산 로그