[암호학] 10. 영지식 증명(1. 2차잉여, 르장드르 기호)

[암호학] 10. 영지식 증명(1. 2차잉여, 르장드르 기호)

양의 정수 $m$과 $\text{gcd}(a,\,n)=1$인 정수 $a$에 대하여 이차합동식 $$x^{2}\equiv a\,(\text{mod}\,n)$$ 의 해가 존재할 때, 즉 적당한 정수 $c$가 존재해서 $c^{2}\equiv a\,(\text{mod}\,m)$일 때 $a$를 법 $m$에 대한 2차잉여(quadratic residue)라고 하고, 그렇지 않으면 2차 비잉여(quadratic nonresidue)라고 한다.

법 $13$에 대한 기약잉여계 $\mathbb{Z}_{13}^{*}$에 대하여 $$\begin{align*}1^{2}\equiv&12^{2}\equiv1\\2^{2}\equiv&11^{2}\equiv4\\3^{2}\equiv&10^{2}\equiv9\\4^{2}\equiv&9^{2}\equiv16\equiv3\\5^{2}\equiv&8^{2}\equiv25\equiv12\\6^{2}\equiv&7^{2}\equiv36\equiv10\end{align*}$$ 이므로 $13$의 2차잉여는 1, 3, 4, 9, 10, 12이고, 나머지인 2, 5, 6, 7, 8, 11은 2차 비잉여이다.  

오일러 판정법(Euler's criterion)

홀수 소수 $p$와 $\text{gcd}(a,\,p)=1$인 정수 $a$에 대하여 다음이 성립한다.

(1) $a^{\frac{p-1}{2}}\equiv1\,(\text{mod}\,p)$일 필요충분조건은 $a$가 $p$의 2차잉여이고, 이때 합동식 $x^{2}\equiv a\,(\text{mod}\,p)$는 두 개의 해를 갖는다.  

(2) $a^{\frac{p-1}{2}}\equiv-1\,(\text{mod}\,p)$일 필요충분조건은 $a$가 $p$의 2차 비잉여이고, 이때 합동식 $x^{2}\equiv a\,(\text{mod}\,p)$는 해를 갖지 않는다. 

또한 법 $p$에 대하여 2차잉여와 2차 비잉여는 각각 $\displaystyle\frac{p-1}{2}$개씩 존재하고, 실제로 법 $p$에 대해 $$1^{2},\,2^{2},\,\cdots,\,\left(\frac{p-1}{2}\right)^{2}$$ 는 2차잉여이다. 

홀수 소수 $a$에 대하여 $a$를 법 $p$에 대한 원시근이라고 하면 $$D=\{1,\,a^{2},\,a^{4},\,...,\,a^{p-3}\},\,a^{p-1}=1$$ 는 법 $p$에 대한 2차잉여 전체의 집합이다. 

홀수 소수 $p$와 $\text{gcd}(a,\,p)=1$인 정수 $a$에 대하여 르장드르 기호(Legendre symbol) $(a/p)$(또는 $\displaystyle\left(\frac{a}{p}\right)$로 나타낸다)의 값을 다음과 같이 정의한다. $$(a/p)=\begin{cases}1&\,(a\,\text{is a quadratic residue of}\,p\,\Leftrightarrow\,x^{2}\equiv a\,(\text{mod}\,p))\\-1&\,(a\,\text{is a quadratic nonresidue of}\,p\,\Leftrightarrow\,x^{2}\not\equiv a\,(\text{mod}\,p))\end{cases}$$ $p|a$인 경우, 즉 $a\equiv0\,(\text{mod}\,p)$인 경우는 $(a/p)=0$으로 나타낸다.  

홀수 소수 $p$와 $\text{gcd}(a,\,p)=\text{gcd}(b,\,p)=1$인 정수 $a,\,b$에 대하여 다음이 성립한다. 

(1) $(1/p)=1$이고 $a\equiv b\,(\text{mod}\,p)$이면, $(a/p)=(b/p)$이다.  

(2) $(a/p)\equiv a^{\frac{p-1}{2}}\,(\text{mod}\,p)$

(3) $(ab/p)=(a/p)(b/p)$이고 $(a^{2}/p)=1$이다.  

(4) $(-1/p)=(-1)^{\frac{p-1}{2}}$

(5) $p\equiv1\,(\text{mod}\,4)\,\Leftrightarrow\,(-1/p)=1$이고 $p\equiv3\,(\text{mod}\,4)\,\Leftrightarrow\,(-1/p)=-1$이다. 

정리 1. 서로 다른 두 홀수 소수 $p,\,q$에 대해 다음이 성립한다. 

(1) $(2/p)=(-1)^{\frac{p^{2}-1}{8}}$ 

(2) $(q/p)(p/q)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$, $(q/p)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}(p/q)$

(3) $(2/p)=1\,\Leftrightarrow\,p\equiv1\,(\text{mod}\,8)\,\text{or}\,p\equiv-1\,(\text{mod}\,8)$이고 

   $(2/p)=-1\,\Leftrightarrow\,p\equiv3\,(\text{mod}\,8)\,\text{or}\,p\equiv-3\,(\text{mod}\,8)$이다.

(4) $(q/p)=(p/q)$일 필요충분조건은 $p\equiv1\,(\text{mod}\,4)\,\text{or}\,q\equiv1\,(\text{mod}\,4)$이고

   $(q/p)=-(p/q)$일 필요충분조건은 $p\equiv q\equiv3\,(\text{mod}\,4)$이다. 

서로 다른 홀수 소수 $p,\,q$에 대하여 $m=pq$라 하고 $a$를 $\text{gcd}(a,\,m)=1$라 하자. 

2차합동식 $x^{2}\equiv a$가 해를 가질 필요충분조건은 다음의 두 합동식 $$x^{2}\equiv a\,(\text{mod}\,p),\,x^{2}\equiv a\,(\text{mod}\,q)$$ 가 모두 해를 갖는 것이다. 즉 $$(a/p)=(a/q)=1$$ 이다. 

그리고 2차합동식 $x^{2}\equiv a\,(\text{mod}\,m)$이 해를 가질 때, 이 이차합동식은 다음과 같은 4개의 해를 갖고 $$\begin{align*}x\equiv&x_{1}\,(\text{mod}\,m),&&x\equiv x_{2}\,(\text{mod}\,m)\\x\equiv&-x_{1}\equiv m-x_{1}\,(\text{mod}\,m),&&x\equiv-x_{2}\equiv m-x_{2}\,(\text{mod}\,m)\end{align*}$$ 이들 해애 대하여 다음이 성립한다.

(1) $\text{gcd}(x_{1}+x_{2},\,m)$과 $\text{gcd}(x_{1}-x_{2},\,m)$중 하나는 $p$이고 또 다른 하나는 $q$이다. 

(2) $p\equiv q\equiv 3\,(\text{mod}\,4)$이면, 이들 해 중에는 $(x_{0}/p)=(x_{0}/q)=1$인 해 $x\equiv x_{0}\,(\text{mod}\,m)$, 즉 법 $m$에 대해 이차잉여인 해가 존재하고 이러한 해는 유일하다. 

증명: 중국인의 나머지 정리에 의해 이차합동식 $x^{2}\equiv a\,(\text{mod}\,m)$은 다음의 연립합동식과 동치이므로 $$\begin{cases}x^{2}\equiv a\,(\text{mod}\,p)\\x^{2}\equiv a\,(\text{mod}\,q)\end{cases}$$ 이차합동식 $x^{2}\equiv a\,(\text{mod}\,m)$은 다음의 두 이차합동식들이 해를 가질 때에만 해를 갖는다. $$x^{2}\equiv a\,(\text{mod}\,p),\,x^{2}\equiv a\,(\text{mod}\,q)$$ 이제 이차합동식 $x^{2}\equiv a\,(\text{mod}\,p)$가 해를 갖는다고 하자. 이때 이차합동식 $x^{2}\equiv a\,(\text{mod}\,p)$, $x^{2}\equiv a\,(\text{mod}\,q)$는 각각의 두 해 $$x\equiv\pm b\,(\text{mod}\,p),\,x\equiv\pm c\,(\text{mod}\,q)$$ 를 가지며 이때 이차합동식 $x^{2}\equiv a\,(\text{mod}\,m)$의 해는 다음의 네 연립합동식의 해와 같다. $$\begin{align*}&\begin{cases}x\equiv b\,(\text{mod}\,p)\\x\equiv c\,(\text{mod}\,q)\end{cases}&&\begin{cases}x\equiv-b\,(\text{mod}\,p)\\x\equiv c\,(\text{mod}\,q)\end{cases}\\&\begin{cases}x\equiv b\,(\text{mod}\,p)\\x\equiv-c\,(\text{mod}\,q)\end{cases}&&\begin{cases}x\equiv-b\,(\text{mod}\,p)\\x\equiv-c\,(\text{mod}\,q)\end{cases}\end{align*}$$ 위의 각 연립일차합동식에 중국인ㅇ의 나머지 정리를 적용하기 위해 $qN_{1}+pN_{2}=1$인 정수 $N_{1},\,N_{2}$를 구하고 $$x_{1}=qN_{1}b+pN_{2}c,\,x_{2}=qN_{1}(-b)+pN_{2}c$$ 라 하면 위 연립일차합동식의 해는 각각 다음과 같다. $$\begin{align*}&x\equiv x_{1}\,(\text{mod}\,m),&&x\equiv x_{2}\,(\text{mod}\,m)\\&x\equiv-x_{2}\,(\text{mod}\,m)&&x\equiv-x_{1}\,(\text{mod}\,m)\end{align*}$$ 이들은 이차합동식 $x^{2}\equiv a\,(\text{mod}\,m)$의 해이고 또한 $$\begin{align*}&x_{1}+x_{2}=2pN_{2},c&&x_{1}-x_{2}=2qN_{1}b\\&\text{gcd}(c,\,q)=\text{gcd}(N_{2},\,q)=1,&&\text{gcd}(b,\,p)=\text{gcd}(N_{1},\,p)=1\end{align*}$$ 이므로 $\text{gcd}(x_{1}+x_{2},\,m)=p$, $\text{gcd}(x_{1}-x_{2},\,m)=q$이다. 여기서 연립일차방정식의 순서를 정하는 방법에 따라 $\text{gcd}(x_{1}+x_{2},\,m)$, $\text{gcd}(x_{1}-x_{2},\,m)$은 $p$ 또는 $q$이다. 

다음으로 $p\equiv q\equiv3\,(\text{mod}\,4)$라 하자. 이때 르장드르 기호의 성질에 의해 $(-1/p)=(-1/q)=1$이고 $qN_{1}+pN_{2}=1$이므로 $$qN_{1}\equiv1\,(\text{mod}\,p),\,pN_{2}\equiv1\,(\text{mod}\,q)$$ 이고 따라서 $x_{1},\,x_{2}$의 값에 의해 $$\begin{align*}&x_{1}\equiv b\,(\text{mod}\,p)&&x_{2}\equiv-b\,(\text{mod}\,p)\\&x_{1}\equiv c\,(\text{mod}\,q)&&x_{2}\equiv c\,(\text{mod}\,q)\end{align*}$$ 이므로 다음이 성립한다. $$\begin{align*}&(x_{1}/p)=(-x_{2}/p)=(b/p),&&(-x_{1}/p)=(x_{2}/p)=-(b/p)\\&(x_{1}/q)=(x_{2}/q)=(c/q)&&(-x_{1}/q)=(-x_{2}/q)=-(c/q)\end{align*}$$ 그러므로 네 순서쌍 $$((x_{1}/p),\,(x_{1}/q)),\,((-x_{1}/p),\,(-x_{1}/q)),\,((x_{2}/p),\,(x_{2}/q)),\,((-x_{2}/p),\,(-x_{2}/q))$$ 은 각각 $$((b/p),\,(c/q)),\,(-(b/p),\,-(c/q)),\,(-(b/p),\,(c/q)),\,((b/p),\,-(c/q))$$ 와 같으므로, 위의 각 순서쌍은 $$(1,\,1),\,(1,\,-1),\,(-1,\,1),\,(-1,\,-1)$$ 중 단 하나와 일치한다. 그러므로 위의 네 순서쌍 중 순서쌍 $(1,\,1)$과 같은 것이 단 하나 존재하고, 이 사실은 이차합동식 $x^{2}\equiv a\,(\text{mod}\,m)$의 해 중 $$(x_{0}/p)=(x_{0}/q)=1$$ 인 해 $x\equiv x_{0}\,(\text{mod}\,m)$가 단 하나 존재함을 뜻하고 이때 $x_{0}$는 법 $m$에 대하여 2차잉여이다.    

정리 2. 홀수 소수 $p$에 대하여 $p\equiv3\,(\text{mod}\,4)$일 때 $\text{mod}(a,\,p)=1$인 정수 $a$에 대하여 $(a/p)=1$이면, 즉 이차합동식 $x^{2}\equiv a\,(\text{mod}\,p)$의 해가 존재하면 이 이차합동식의 두 해는 다음과 같다. $$x\equiv\pm a^{\frac{p+1}{4}}\,(\text{mod}\,p)$$ 증명: 가정에 의해 $\displaystyle\frac{p+1}{4}$는 정수이고 $1=(a/p)\equiv a^{\frac{p-1}{2}}\,(\text{mod}\,p)$이므로 $$\left(\pm a^{\frac{p+1}{4}}\right)^{2}\equiv a^{\frac{p+1}{2}}\equiv a^{\frac{p-1}{2}}a\equiv a\,(\text{mod}\,p)$$ 이고 따라서 정리가 성립한다. 

참고자료:

암호학과 부호이론, 박승안, 경문사

Elementary Number Theory 7th edition, Burton, McGraw-Hill