Tonelli-Shanks Algorithm

Aim: Solve \(x^2 \equiv n \pmod p \) in \( \mathcal{O}( \log^2 p ) \).

Tonelli-Shanks Algorithm은 \(\mathbb{Z}/p\mathbb{Z}\)에서 이차방정식을 빠르게 풀어내는 알고리즘이다.

Step 1. \(n\)이 \(\text{mod   } p\)에서 quadratic residue인지 확인한다. \( n^{\frac{p-1}{2}} \equiv 1 \pmod p\)인지 여부를 확인하면 된다.

Step 2. \(p-1 = Q \cdot 2^S\)인 홀수 \(Q\)와 음이 아닌 정수 \(S\)를 구한다. 

Step 3. \(\text{mod   } p\)에서 quadratic non-residue인 자연수 \(z\)를 하나 찾는다. 

Step 4. \(M=S\), \(c=z^Q\), \(t=n^Q\), \(R = n^{\frac{Q+1}{2}} \)라 하자. 전부 \(\text{mod   }p\)로 본다.

Step 5. 이제 다음을 반복한다.

• \(t=0\)이면 \(0\)을 출력한다. \(t=1\)이면 \(R\)을 출력한다. 
• 이제 \(0<i<M\)이면서 \(t^{2^i} \equiv 1 \pmod{p}\)를 만족하는 최소의 자연수 \(i\)를 찾는다.
• \(b=c^{2^{M-i-1}}\)이라 두고, \(M \leftarrow i\), \(c \leftarrow b^2\), \(t \leftarrow tb^2\), \(R \leftarrow Rb\)로 값을 바꿔준다.

알고리즘을 통해 출력된 값이 \(r\)이라면, \(r\)와 \(-r\)이 \(x^2 \equiv n \pmod p\)의 두 근이 된다.

이 알고리즘을 활용하여, \(ax^2+bx+c \equiv n \pmod p\)도 쉽게 풀 수 있다.  

Claim 1: 이 알고리즘으로 출력된 값이 \(r\)이라면, \(r^2 \equiv n \pmod p\)가 성립한다. 

Proof of Claim 1: 우선 \(c^{2^{M-1}} = -1\), \(t^{2^{M-1}} = 1\), \(R^2 = tn\)이 항상 성립함을 보이자. 

초기에 \(c^{2^{M-1}} = z^{Q \cdot 2^{S-1}} = z^{\frac{p-1}{2}} = -1\)이다. (\(z\)는 quadratic non-residue니까)

초기에 \(t^{2^{M-1}} = n^{Q \cdot 2^{S-1}} = n^{\frac{p-1}{2}} = 1\)이다. (\(n\)은 quadratic residue니까)

초기에 \(R^2 = n^{Q+1} = n \cdot n^Q = nt\)가 성립한다. 초기에서는 세 식이 모두 성립함을 확인했다.

Step 5에서 \(M, c, t, R\)이 \(M', c', t', R'\)으로 바뀐다고 하자. 

\(c'^{2^{M'-1}} = b^{2^i} = c^{2^{M-1}} = -1\)이므로, 바뀐 뒤에도 첫번째 식이 성립한다. 

\(t'^{2^{M'-1}} = t^{2^{i-1}} \cdot b^{2^i} = -1 \cdot -1 = 1\)이므로, 바뀐 뒤에도 두번째 식이 성립한다. (why?)

\(R'^2 = R^2b^2 = tnb^2 = t'n\)이므로, 바뀐 뒤에도 마지막 식이 성립한다.  

\(t^{2^{M-1}} = 1\)이므로, Step 5에서 항상 조건을 만족하는 \(i\)를 찾을 수 있다.

또한, Step 5를 반복하면서 항상 \(M\)의 값이 감소하게 된다. \(M'=i<M\)이기 때문이다. 

그러다가 \(M=1\)이 되면 그 순간 \(t=1\)임이 보장되며, \(R^2 = tn = n\)이므로 \(R\)은 합동방정식의 해가 된다. 

Claim 2: 이 알고리즘은 \(\mathcal{O}(\log^2 p) \)번의 사칙연산을 필요로 한다. 

Proof of Claim 2: Step 1, 2, 4는 로그 시간에 할 수 있음이 자명하다. 

Step 3는 그냥 \(z\)를 랜덤하게 잡아보면서 quadratic non-residue가 나오면 terminate하는 방식으로 \(z\)를 찾아도 된다. 

\(z\)가 quadratic non-residue일 확률이 \(\frac{1}{2}\) 정도이므로, 평균 2번 정도의 시행을 필요로 한다. 

Step 5의 loop는 최대 \(S = \mathcal{O}(\log p)\)번 돌아가고, 각 loop에서 소모하는 연산 횟수는 \(\mathcal{O}(M)\)번, 즉 \(\mathcal{O}(\log p)\)번이다.

그러므로 Step 5에서는 최대 \(\mathcal{O}(\log^2 p)\)번의 사칙연산을 활용한다. 

시간복잡도를 \(\mathcal{O}(S^2)\)로도 쓸 수 있으며, \(S\)가 작은 경우도 많다는 점도 주목하자.

이제 Hensel's Lemma를 걸어주면, \(x^2 \equiv n \pmod{p^k}\)도 빠르게 풀어줄 수 있다. 

활용문제: Project Euler 216, 437