[암호학] 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