서론
이 글은 이전에 작성한 Tonelli-Shanks 구현 포스팅에 Tonelli-Shanks에 대한 이론적 내용을 덧붙여 작성한 글입니다. 배우며 작성한 글이므로 틀린 내용이 있을 수 있으니, 발견하시면 댓글로 알려주시길 바랍니다.
본 글은 https://rkm0959.tistory.com/20를 토대로 학습하며 작성한 글입니다.
암호학을 공부하다 보면 $\mathbb{Z}/p\mathbb{Z}$에서 이차방정식을 풀어야 할 필요가 있다. CTF에서 RSA 문제를 풀 때 $m^2\mod p$를 구했다거나, Diffie-Hellman 프로토콜 문제를 풀며 $g^2 \mod p$로부터 $g$를 찾아야 한다거나… 여러 상황에서 이차방정식을 해결할 수 있다면 편리할 것이다.
우선 $\mathbb{Z}/p\mathbb{Z}$가 아니라 $\mathbb{R}$에서 이차방정식을 풀 때를 생각해보자. 근의 공식이 너무 익숙하지만, 그 이전에는 한 변을 완전제곱식으로 변형하고 양변에 제곱근을 취하여 해를 구하였다.
따라서 $\mathbb{Z}/p\mathbb{Z}$에서도 $x^2 \equiv n \text{ (mod } p\text{)}$를 풀 수 있다면, 임의의 이차방정식에 대해 근을 구할 수 있음을 알 수 있다. 이러한 해결책으로는 Tonelli-Shanks 알고리즘을 사용하는 시간복잡도 $O(\log^2p)$의 솔루션이 존재한다.
우선 다음과 같은 Lemma를 확인해두자.
Lemma 1
$\mod p$에서 quadratic residue는 정확히 $p-1\over2$개 존재한다.
Proof
우선, $1\le k \le {p-1\over2}$일 때 $k^2\equiv(p-k)^2\text{ (mod } p\text{)}$이다.
$1\le a<b\le{p-1\over2}$이라고 하자. $a^2-b^2\equiv(a+b)(a-b)\text{ (mod } p\text{)}$인데, $2\le a+b \le p-1$이고 $a$와 $b$가 다른 수이므로 $a^2-b^2\mod p$는 0이 아니다. 따라서 $1,2,\cdots,{p-1\over2}$는 모두 제곱한 값이 서로 다르며, quadratic residue는 정확히 $p-1\over2$개 있음을 알 수 있다.
또한, Lemma 1에 의해 자명하게 quadratic non-residue 역시 $p-1\over2$개이다.
Lemma 2
$n$이 $\mod p$에서 quadratic residue $\Leftrightarrow$ $n^{p-1\over2}\equiv1\text{ (mod } p\text{)}$
Proof
quadratic residue라면 $x^2\equiv n\text{ (mod } p\text{)}$인 $x$가 존재하고, $n^{p-1\over2}\equiv x^{p-1}\equiv1\text{ (mod } p\text{)}$이다. $x^{p-1}\equiv1\text{ (mod } p\text{)}$는 페르마 소정리에 의해 성립한다.
$n^{p-1\over2}\equiv1\text{ (mod } p\text{)}$는 ${p-1\over2}$차 방정식이므로 최대 ${p-1\over2}$개의 근을 갖는다. 그러므로 quadratic non-residue는 이 방정식의 근이 될 수 없다.
참고로 $n$이 quadratic non-residue일 때 $n^{p-1\over2}\equiv-1\text{ (mod } p\text{)}$이다. $1\equiv n^{p-1}\equiv (n^{p-1\over2})^2 \text{ (mod } p\text{)}$이므로 $n^{p-1\over2}\equiv\pm1\text{ (mod } p\text{)}$인데, $n^{p-1\over2}\equiv1\text{ (mod } p\text{)}$은 아니므로 $n^{p-1\over2}\equiv-1\text{ (mod } p\text{)}$이다.
Lemma 3
$\sqrt{p}$ 이하의 자연수 중 quadratic non-residue가 적어도 하나 존재한다.
Proof
$\sqrt{p}$ 이하의 자연수가 모두 quadratic residue라고 가정하자. 이때 quadratic residue의 집합을 $Q$라고 하면, $a,b\in Q$일 때 $ab\in Q$이다. 따라서 $x\in\mathbb{Z}/p\mathbb{Z}$인 임의의 $x$에 대해 $x\in Q$를 보장할 수 있다. 하지만 Lemma 2에 의해 quadratic residue는 $p-1\over2$개뿐이므로 모순이 발생한다.
즉, 귀류법에 의해 Lemma 3이 성립한다.
Tonelli-Shanks 알고리즘
Tonelli-Shanks 알고리즘은 다음과 같이 진행된다.
-
$n$이 $\text{mod } p$에서 quadratic residue인지 확인한다. (Lemma 2 활용)
-
$p-1=Q\cdot2^S$인 홀수 $Q$와 음 아닌 정수 $S$를 구한다.
-
$\text{mod } p$에서 quadratic non-residue인 정수 $z$를 하나 찾는다. Lemma 2에 의해 조사해야 하는 수의 개수의 기댓값이 2임을 알 수 있다.
최악의 경우에도 Lemma 3에 의해 $O(\sqrt{p}\log{p})$에 찾을 수 있으나, 보통은 거의 상수 시간복잡도로 찾을 수 있다.
-
다음과 같이 정의하자.
- $M\equiv S\text{ (mod } p\text{)}$
- $c\equiv z^Q \text{ (mod } p\text{)}$
- $t\equiv n^Q\text{ (mod } p\text{)}$
- $R\equiv n^{Q+1\over2}\text{ (mod } p\text{)}$
-
다음 과정을 반복한다.
- $t=0$이면 $0$을 출력한다.
- $t=1$이면 $R$을 출력한다.
- $0<i<M$과 $t^{2^i}\equiv1\text{ (mod } p\text{)}$를 만족하는 최소의 자연수 $i$를 찾는다.
- $b$를 $b\equiv c^{2^{M-i-1}}\text{ (mod } p\text{)}$로 정의한다.
- $M\leftarrow i$, $c\leftarrow b^2$, $t\leftarrow tb^2$, $R\leftarrow Rb\text{ (mod } p\text{)}$
-
출력된 값이 $r$이라면 $\pm r$이 $x^2\equiv n\text{ (mod } p\text{)}$의 두 근이다.
알고리즘의 타당성 증명
초기의 정의를 다시 한 번 봐보자.
- $M=S$
- $c\equiv z^Q \text{ (mod } p\text{)}$
- $t\equiv n^Q\text{ (mod } p\text{)}$
- $R\equiv n^{Q+1\over2}\text{ (mod } p\text{)}$
이때 초기값에 관해 다음과 같은 사실을 알 수 있다. $\cdots$ (A)
- $z$가 quadratic non-residue이므로 $c^{2^{M-1}}\equiv z^{Q\cdot2^{S-1}}\equiv z^{p-1\over2}\equiv-1\text{ (mod } p\text{)}$이다.
- $n$은 quadratic residue이므로 $t^{2^{M-1}}=n^{Q\cdot2^{S-1}}\equiv n^{p-1\over2}\equiv1\text{ (mod } p\text{)}$이다.
- $R^2\equiv n^{Q+1}\equiv nt\text{ (mod } p\text{)}$이다.
(5.)에서 $M,c,t,R$에 각각 $M^\prime,c^\prime,t^\prime,R^\prime$이 대입된다고 하자.
각각의 값이 어떻게 정의되는지 다시 한 번 확인하자.
- $b\equiv c^{2^{M-i-1}}\text{ (mod } p\text{)}$
- $M^\prime$는 $0<M^\prime<M$과 $t^{2^{M^\prime}}\equiv1\text{ (mod } p\text{)}$를 만족하는 최소의 자연수
- $c^\prime \equiv b^2 \text{ (mod } p\text{)}$
- $t^\prime\equiv tb^2 \text{ (mod } p\text{)}$
- $R^\prime\equiv Rb\text{ (mod } p\text{)}$
$b$의 정의에 따라 다음과 같은 명제가 성립한다.
-
${c^\prime}^{2^{M^\prime-1}}\equiv b^{2^i}\equiv c^{2^{M-1}}\equiv-1\text{ (mod } p\text{)}$
-
${t^\prime}^{2^{M^\prime-1}}\equiv t^{2^{M^\prime-1}}b^{2^{M^\prime}}\equiv(-1)\cdot(-1)\equiv1\text{ (mod } p\text{)}$
-
${R^\prime}^{2}\equiv R^2b^2\equiv ntb^2\equiv nt^\prime\text{ (mod } p\text{)}$
따라서 (A)에서 성립한 식은 (5.)를 몇 번 반복하더라도 여전히 성립함을 알 수 있다.
이 때 $t^{2^{M-1}}\equiv1\text{ (mod } p\text{)}$이므로 $0<M^\prime<M$인 $M^\prime$은 항상 존재하며, $M$의 값이 항상 감소하게 됨을 알 수 있다. 그렇게 계속 반복하며 $M=1$이 되는 순간 $1\equiv t^{2^{M-1}}\equiv t^1\text{ (mod } p\text{)}$이므로 $t\equiv1\text{ (mod } p\text{)}$임이 보장되며, $R^2\equiv nt\equiv n\text{ (mod } p\text{)}$이므로 $R$은 $x^2\equiv n\text{ (mod } p\text{)}$의 해가 된다.
알고리즘의 시간복잡도 증명
(1.), (2.), (4.)는 자명하게 $O(\log p)$에 동작함을 알 수 있다.
(3.) 역시 보통 상수 시간복잡도로 찾을 수 있다.
(5.)에서 $i$를 찾는 과정은 $O(M)$인데, $M$은 최악의 경우 $O(\log p)$이다. 따라서 $O(log p)$ 이내에 찾을 수 있다. (5.)의 이외의 과정도 $O(\log p)$에 계산할 수 있다.
(5.)는 최대 $O(\log p)$번 반복되므로 총 $O(\log^2 p)$에 동작한다.
따라서 전체 시간복잡도는 $O(\log p+1+\log^2 p)=O(\log^2 p)$가 됨을 알 수 있다.
Python 구현
def tonelli_shanks(n,p):
def isQR(x,p):# check whether x is quadratic residue
return pow(x,(p-1)//2,p)==1
# (1.)
if not isQR(n,p):
return -1
# (2.)
Q,S=p-1,0
while Q%2==0:
S+=1
Q//=2
# (3.)
z=None
for x in range(2,p):
if not isQR(x,p):
z=x
break
# (4.)
M,c,t,R=S,pow(z,Q,p),pow(n,Q,p),pow(n,(Q+1)//2,p)
# (5.)
while True:
if t==0:
return 0
elif t==1:
return R
k=t*t%p
ii=None
for i in range(1,M):
if k==1:
ii=i
break
k*=k
k%=p
b=pow(c,2**(M-i-1),p)%p
M=ii%p
c=b*b%p
t=t*c%p
R=R*b%p
# test
if __name__=='__main__':
n,p=map(int,input().split())
print("STARTED")
print(tonelli_shanks(n,p))