📂정수론

이산로그 문제가 쉽게 풀리는 조건

정리 ¹

그룹 $G = F_{p}$ 의 원소 $g$ 가 오더 $N$ 이라고 하자. 그러면 이산로그 문제 $g^{x} = h$ 는 다음의 조건 하에서 비교적 쉽게 풀리게 된다.

• (i): $p$ 가 스무스 소수다.
• (ii): $p \equiv 3 \pmod{4}$ 고 $a$ 가 모듈로 $p$ 에 대한 이차잉여다.

증명

(i)

$p$ 가 스무스한 소수면 폴리그-헬맨 알고리즘을 사용할 수 있으므로 이산로그 문제는 비교적 쉽게 풀린다.

■

(ii)

$$ x^{2} \equiv a \pmod{p} $$ $a$ 가 모듈로 $p$ 에 대한 이차잉여라는 것은 위 합동방정식을 만족시키는 해가 존재한다는 것이다. 만약 소수 $p$ 를 $4$ 로 나눈 나머지가 $3$ 이라면 $$ b \equiv a^{(p+1)/4} \pmod{p} $$ 는 어떤 $a \equiv g^{2k} \pmod{p}$ 에 대해 $$ \begin{align*} b^{2} \equiv & a^{{ p+1 } \over { 2 }} & \pmod{p} \\ \equiv & \left( g^{2k} \right)^{{ p+1 } \over { 2 }} & \pmod{p} \\ \equiv & g^{(p+1)k} & \pmod{p} \\ \equiv & g^{2k + (p-1)k} & \pmod{p} \\ \equiv & a \cdot \left( g^{p-1} \right)^{k} & \pmod{p} \\ \equiv & a & \pmod{p} \end{align*} $$ 이므로 주어진 합동방정식의 솔루션이 된다. 공식에 따라 $a$ 의 제곱근을 아주 빠르게 구할 수 있게 되었으므로 이산로그 문제는 비교적 쉽게 풀리게 된다.

■

같이보기

• 이산로그 문제

이산로그 문제의 어려움을 이용한 보안 알고리즘

• 디피-헬만 키 교환 알고리즘
• 엘가말 공개 키 암호체계

이산로그 문제에 대한 공격 알고리즘

• 샹크스 알고리즘
• 폴리그-헬맨 알고리즘
• 이산로그 문제가 쉽게 풀리는 조건