📂정수론

합동방정식의 거듭제곱근

알고리즘 ¹

자연수 $b,k,m$ 가 $\gcd (b , m) = \gcd ( k , \phi (m) ) = 1$ 을 만족하면 합동방정식 $x^{k} \equiv b \pmod{ m }$ 의 해 $x$ 는 다음과 같이 계산할 수 있다.

---

Step 1.

$\phi (m)$ 을 계산한다.

---

Step 2.

$ku - \phi (m) v =1$ 을 만족하는 $u, v$ 을 찾고 양변에 $u$ 승을 취해 $x^{ku} \equiv b^{u} \pmod{m}$ 를 얻는다.

---

Step 3.

$b^{u} \pmod{ m }$ 을 연속제곱법으로 계산한다.

설명

$\phi$ 는 토션트 함수로, 곱셈적 성질을 가져 $m$ 의 소인수분해가 핵심이다.

알려져있듯 소인수분해엔 딱히 왕도가 없어서 무척 어려운데, 무지막지하게 큰 소수 $p,q$ 가 존재해서 $m=pq$ 이라고 한다면 $x := \phi (m)$ 을 구하는 것부터가 힘들다. 언뜻 이것은 단점으로 보이지만, 오히려 이를 이용하면 $x$ 를 암호처럼 사용할 수 있게 된다. $k$ 와 $m$ 이 공개되어 있어도 $m$ 의 소인수분해를 모르면 $x$ 를 계산 하는 것이 몹시 어렵다. 따라서 $x$ 를 알 자격이 있는 사람만 $m$ 의 소인수분해를 안다면 훌륭한 암호 체계가 된다. 이러한 암호 체계를 RSA 암호라고 한다.

이 알고리즘은 아주 큰 소수를 찾는 일이 실용적 가치를 가진다는 것을 말해준다.

증명

$ku - \phi (m) v =1$ 을 만족하는 정수해 $u,v$ 의 존재성은 보장되어있고, $ku = \phi (m) v + 1$ 이므로 $$x^{ku} \equiv x^{ \phi (m) v + 1 } \pmod{m}$$

오일러의 토션트 정리: $\gcd(x,m) = 1 \implies x^{ \phi (m) } \equiv 1 \pmod{m}$

$x^{ \phi (m) v + 1 } \equiv x^{ 1 } = b^{u} \pmod{m}$ 이므로, $b^{u}$ 만 계산하면 된다. 여기서 조건인 $\gcd (x, m) = 1$ 을 만족하진 않았지만, 이렇게 구해진 $x$ 는 주어진 합동방정식의 해로써 전혀 문제가 없다.

$$x^{k} = \left( b^{u} \right)^{k} = b^{uk} = b^{ 1+ \phi (m ) v} = b \cdot b^{ \phi (m ) v}$$ 인데, $\gcd (b , m) = 1$ 을 가정했으므로 다음이 성립한다. $$x^{k} \equiv b \pmod{ m }$$

■