토넬리-섕크스 알고리즘

토넬리-섕크스 알고리즘(Tonelli–Shanks algorithm)은 모듈러산술에서 홀수 소수를 법으로 하는 이차합동식 [math]\displaystyle{ x^2 \equiv a \pmod p }[/math]의 해, 즉 모듈러 제곱근을 구하는 방법이다.

주어진 소수 [math]\displaystyle{ p }[/math]에 대해 [math]\displaystyle{ p-1 }[/math]이 8의 배수일 때 이 알고리즘을 이용하면 모듈러 제곱근을 손쉽게 구할 수 있다.

아이디어

먼저 홀수 소수는 [math]\displaystyle{ p=2^mq+1 }[/math]의 꼴로 나타낼 수 있다. 여기서 [math]\displaystyle{ q }[/math]는 홀수이고, 2의 지수 [math]\displaystyle{ m }[/math]은 유일하게 정해진다.

[math]\displaystyle{ 1 \leq b \leq p }[/math]인 어떤 자연수가 법 [math]\displaystyle{ p }[/math]에 대한 이차비잉여이면 [math]\displaystyle{ b^{p-1} \equiv 1, b^{\frac{p-1}{2}} \equiv -1 \pmod p }[/math]이다. [math]\displaystyle{ c=b^q \mod p }[/math]이라 하면 [math]\displaystyle{ c^{2^m} \equiv 1, c^{2^{m-1}} \equiv -1 \pmod p }[/math]이므로 [math]\displaystyle{ \operatorname{ord}_p c=2^m }[/math]이다. 한편 [math]\displaystyle{ 1 \leq a \leq p }[/math]인 임의의 자연수에 대해 [math]\displaystyle{ (a^q)^{2^m} \equiv 1 \pmod p }[/math]이므로 [math]\displaystyle{ \operatorname{ord}_p a^q \mid 2^m }[/math]이며, [math]\displaystyle{ a^q \equiv c^r \pmod p, 0 \leq r \lt 2^m }[/math]인 [math]\displaystyle{ r }[/math]이 반드시 하나 존재한다.

만약 운이 좋은 경우로 [math]\displaystyle{ r=0, a^q \equiv 1 \pmod p }[/math]이라면 [math]\displaystyle{ x^2 \equiv a \pmod p }[/math]의 해는 [math]\displaystyle{ x \equiv \pm a^{\frac{q+1}{2}} \pmod p }[/math]으로 바로 나온다. 물론 실제로는 상당한 확률로 [math]\displaystyle{ r \neq 0 }[/math]인데, [math]\displaystyle{ a^q \mod p }[/math]에서 출발하는 [math]\displaystyle{ t }[/math]를 변형하여 이 값이 1에 도달하도록 알고리즘을 세울 것이다.

먼저 위에서 구한 [math]\displaystyle{ c=b^q \mod p }[/math]으로부터 [math]\displaystyle{ O=\{x: x \equiv c^r \pmod p, 0 \leq r\lt 2^m \} \subset \mathbb{Z}/n\mathbb{Z} }[/math]를 정의한다. 즉 [math]\displaystyle{ O=\{1, c, c^2, \cdots c^{2^m-1} \} }[/math]와 같이 써지고, 이제 이 집합을 법 [math]\displaystyle{ p }[/math]에 대한 위수 별로 쪼갠다.

• 정의: [math]\displaystyle{ A_k=\{x: x \in O, \operatorname{ord}_n x=2^k \}, 0 \leq k \leq m }[/math]
• [math]\displaystyle{ A_m=\{c, c^3, c^5, \cdots c^{2^m-1} \} }[/math]
• [math]\displaystyle{ A_{m-1}=\{c^2, c^6, c^{10}, \cdots c^{2^m-2} \} }[/math]
• [math]\displaystyle{ A_{m-2}=\{c^4, c^{12}, c^{20}, \cdots c^{2^m-4} \} }[/math]
• 이렇게 나아가서 [math]\displaystyle{ A_2=\{c^{2^{m-2}}, c^{3\cdot 2^{m-2}} \}, A_1=\{c^{2^{m-1}} \}, A_0=\{1\} }[/math]까지 도달한다.
• [math]\displaystyle{ O=A_0 \cup A_1 \cup A_2 \cdots \cup A_m, A_k \cap A_{k'} =\emptyset \text { for } k \neq k' }[/math]

가령 [math]\displaystyle{ t \in O }[/math]인 원소에 대해 [math]\displaystyle{ t \in A_k }[/math]이면 [math]\displaystyle{ t^2 \in A_{k-1}, t^4 \in A_{k-2}, \cdots t^{2^k} \in A_0 }[/math]임을 알 수 있다. 또, [math]\displaystyle{ t \equiv c^r \pmod p }[/math]에 대해 [math]\displaystyle{ 2^{m-k} \mid r, 2^{m-k+1} \nmid r }[/math]이다. 그렇다면 만약 [math]\displaystyle{ r'=r+2^{m-k}, t'=c^{r'}=tc^{2^{m-k}} \mod p }[/math]을 새로 정의하면 [math]\displaystyle{ 2^{m-k+1} \mid r' }[/math]이므로 [math]\displaystyle{ \operatorname{ord}_n t'=2^{k'} \mid 2^{k-1}, t' \in A_{k'}, k'\lt k }[/math]라 할 수 있고, 이것이 알고리즘의 단서가 된다.

• 먼저 [math]\displaystyle{ t=a^q \mod p }[/math]에서 출발하여 이 값이 [math]\displaystyle{ A_k }[/math] 중 어느 집합의 원소인지 알아본다. 즉 [math]\displaystyle{ t^{2^k} \equiv 1 \pmod p }[/math]인 최소 [math]\displaystyle{ k }[/math]를 찾으면 된다.
• 그 다음 [math]\displaystyle{ t'=tc^{2^{m-k}} }[/math]을 셈하고 이 새로운 값이 어느 집합의 원소인지를 다시 찾는다. 이러한 변형을 반복하면 [math]\displaystyle{ A_0 }[/math]의 원소인 1에 수렴한다.

알고리즘

구체화된 알고리즘은 아래와 같이 진행한다.

• [math]\displaystyle{ p-1=2^m q }[/math]를 만족하는 홀수 [math]\displaystyle{ q }[/math]와 2의 지수 [math]\displaystyle{ m }[/math]을 구한다.
• [math]\displaystyle{ 1\lt b\lt p, \left(\frac{b}{n}\right)=-1 }[/math]인 자연수를 아무거나 잡고 [math]\displaystyle{ c=b^q \mod p }[/math]를 셈한다.
• 변수 네 개를 지정한다: [math]\displaystyle{ M \leftarrow m, y \leftarrow c, t \leftarrow a^q \mod p, x \leftarrow a^{\frac{q+1}{2}} }[/math]
• (※) [math]\displaystyle{ t=1 }[/math]이면 알고리즘은 여기서 끝나고, [math]\displaystyle{ \pm x }[/math]를 반환한다.
• [math]\displaystyle{ t \neq 1 }[/math]이면 제곱을 반복해서 [math]\displaystyle{ t^{2^k} \equiv 1 \pmod p }[/math]인 최소 [math]\displaystyle{ k }[/math]를 찾는다.
• 보조 변수 [math]\displaystyle{ s \leftarrow y^{2^{M-k-1}} \mod p }[/math]를 셈하고 앞서 세운 변수의 값들을 갱신한다.
  • [math]\displaystyle{ M \leftarrow k, y \leftarrow s^2, t \leftarrow s^2t, x \leftarrow sx }[/math] 다음 (※) 지점으로 돌아간다.

참고 사항

만약 [math]\displaystyle{ p-1 }[/math]이 8의 배수가 아니면 두 경우로 나누어서 풀이과정을 단순화할 수 있다.

• [math]\displaystyle{ p \equiv 3 \pmod 4 \Rightarrow x \equiv \pm a^{\frac{n+1}{4}} \pmod p }[/math]
• [math]\displaystyle{ p \equiv 5 \pmod 8 \Rightarrow x \equiv \pm aj(2aj^2-1) \pmod p, j \equiv (2a)^{\frac{n-5}{8}} \pmod p }[/math]

적용 예

[math]\displaystyle{ x^2 \equiv 89 \pmod{97} }[/math]은 아래와 같이 푼다.

첫 단계로 [math]\displaystyle{ 97=2^m q+1, q=3, m=5 }[/math]를 찾는다. 그 다음 법 97에 대한 이차비잉여를 하나 찾는다. 97을 5로 나눈 나머지가 2라는 점에서 5는 이차비잉여임을 알 수 있다. 즉 [math]\displaystyle{ \left(\frac{5}{97}\right)=-1 }[/math]

해가 나올때까지 알고리즘은 아래와 같이 진행된다.

p=97, a=89, q=3, m=5, b=5
c=b**q %n ##c=28
M=m, y=c, t=a**q %n, x=a**((q+1)/2) %n ##M=5, y=28, t=70, x=64
t!=1: t**2 %p==50, t**4 %p==75, t**8 %p==96, t**16 %n ==1 -> k=4
r=M-k-1 ##r=0
s=y**(2**r) %p ##s=28
M=k, y=s**2 %p, t=(s**2)*t %p, x=s*x %p ##M=4, y=8, t=75, x=46
t!=1: t**2 %p==96, t**4 %n==1 -> k=2
r=M-k-1 ##r=1
s=y**(2**r) %p ##s=64
M=k, y=s**2 %n, t=(s**2)*t %p, x=s*x %p ##M=2, y=22, t=1, x=34
t==1: return x

이렇게 해서 [math]\displaystyle{ x \equiv \pm 34 \pmod{97} }[/math]을 얻는다.

이 과정은 아래와 같이 전개된다:

• 페르마의 소정리에 의해 [math]\displaystyle{ b^{96} \equiv c^{32} \equiv 1 \pmod{97} }[/math]이다.
• [math]\displaystyle{ a=89 \equiv b^{22}, t_1=70 \equiv a^3 \equiv c^{22}, x_1=64 \equiv b^{44} \pmod{97} }[/math]에서 출발한다. 이때 [math]\displaystyle{ t_1 }[/math]에 대응하는 [math]\displaystyle{ c }[/math]의 지수가 4의 배수가 아닌 2의 배수이므로, [math]\displaystyle{ t_1 \in A_4, k_1=4 }[/math]이다.
• [math]\displaystyle{ t_2=t_1c^2 \mod{97} }[/math]는 우변의 [math]\displaystyle{ c }[/math]의 지수가 4의 배수가 되도록 맞추는 식이다. 이를 위해 [math]\displaystyle{ y_1=c, s_1=y_1^{2^0}=c=b^3 }[/math]을 대입하고 [math]\displaystyle{ t_2=t_1s_1^2 \mod{97}, x_2=s_1x_1 \mod{97} }[/math]를 셈한다.
• [math]\displaystyle{ t_2=75 \equiv c^{24}, x_2=46 \equiv b^{47} \pmod{97} }[/math]이다. 이번에는 [math]\displaystyle{ c }[/math]의 지수가 8의 배수이므로 [math]\displaystyle{ t_2 \in A_2, k_2=2 }[/math]가 나왔다.
• 그렇다면 이번에는 [math]\displaystyle{ t_3=t_2c^8 \mod{97} }[/math]을 계산해서 지수를 16의 배수로 맞춘다. 이를 위해 [math]\displaystyle{ y_2=s_1^2=c^2, s_2=y_2^{2^1}=c^4=b^{12} }[/math]을 대입하고 [math]\displaystyle{ t_3=t_2s_2^2 \mod{97}, x_3=s_2x_2 \mod{97} }[/math]를 셈한다.
• [math]\displaystyle{ t_3=1 \equiv c^{32}, x_3=34 \equiv b^{59} \pmod{97} }[/math]이다. 이 시점에서 1과 합동인 [math]\displaystyle{ c^{32} }[/math]에 도달하였기에 알고리즘이 끝난다. 아울러 마지막에 나온 [math]\displaystyle{ x_3 \equiv b^{59} }[/math]가 구하는 해이며, 검산을 하면 [math]\displaystyle{ x_3^2 \equiv b^{118} \equiv b^{22} \equiv a \pmod{97} }[/math]로 원래 식과 일치함을 알 수 있다.