[3-9] Square Roots Mod n

x^2 ≡ 71 (mod 77)가 solution(해)을 가지고 있다고 가정하자. 

그 전에 먼저 일반적으로 x^2 ≡ b (mod n)의 모든 해를 찾는 문제를 고려하자. 여기서 n = pq, 두 소수의 곱으로 이루어져 있다.

n의 인수분해를 알고 있다면 해를 찾는 것은 매우 쉽게 풀린다. 반대로 모든 솔루션(해)을 알고 있다면 n을 인수분해하는 것이 쉽다. 

 

square root mod a prime p의 case로 진행할 것이고 p가 mod 4에 대해서 3일 때 가장 easy하고 1일 때가 더 어렵다. 이유는 (cohen을 참조하자)

 

Proposition(명제)

p ≡ 3 (mod 4)인 소수이고 y를 정수, x ≡ y^(p+1)/4 (mod p)라고 하자.

1. y가 mod p에 대해 제곱근을 가지면, y의 mod p에 대한 제곱근은 ±x이다.

2. y가 mod p에 대해 제곱근을 안가지면, -y가 mod p에 대해 제곱근을 가지고 -y의 mod p에 대한 제곱근은 ±x이다.

 

Proof(증명)

y ≡ 0 (mod p)라고 가정하면 모든 명령문이 trivial하기 때문에 y !≡ 0 (mod p)라고 가정한다. 페르마의 정리에 의하면 y^p-1 ≡ 1 (mod p)이기 때문에 

으로 표현이 가능하다. 이 식은 (x^2+y)(x^2-y) ≡ 0 (mod p)으로 표현할 수 있는데 그럼 x^2 ≡ ±y (mod p)이다. 그렇기 때문에 y와 -y중 적어도 하나는 mod p에 대해 제곱이다. 둘 다 제곱근이라고 했을 때, y = a^2, -y = b^2으로 두면 -1 = (a/b)^2은 -1이 mod p의 제곱이라는 의미이다. 그러나 p ≡ 3 (mod 4)에서 불가능하기 때문에 y와 -y중 하나만 mod p에 대해서 제곱근을 가지게 된다.

+일반적으로 0과 관련된 답을 trivial하다고 한다. / 대상에 대하여 대단히 간단한 구조를 표현하는 자명한의 의미임

 

Example(예제)

composite modulus의 제곱근을 고려하자. -> x^2 ≡ 71 (mod 77)

이 식은 x^2 ≡ 71 ≡ 1 (mod 7) and x^2 ≡ 71 ≡ 5 (mod 11)을 의미한다. 그러므로 x ≡ ±1 (mod 7) and  x ≡ ±4 (mod 11)이다. 중국인의 나머지 정리 이론에 따르면 합동 mod 7과 합동 mod 5이 합동 mod 77로 재결합될 수 있음을 알려준다. 이 예제의 경우에는 x ≡ 15 (mod 77)이고 4가지 방법으로 재결합이 가능하다. x ≡ ±15 ,  ±29 (mod 77).

 

즉 n = pq, 두 소수의 곱일 때, 우리는 4개의 해를 알 수 있다. (x ≡ ±a, ±b of x^2 ≡ y (mod n)).

이를 통해서 a ≡ b (mod p) and a ≡ -b (mod q)임을 알 수 있고, 그러므로 p|(a-b)이지만 q|(a-b)가 아니다. 이는 gcd(a-b, n) = p라는 것이고 우리는 n의 nontrivial factor를 찾을 수 있다.

->해를 알면 n의 인수분해가 가능함을 보이고 있음

 

결론

위에서 사용한 모든 연산은 n의 인수분해를 제외하고는 빠르다. 특히 중국인의 나머지 정리 계산을 빠르게 수행할 수 있고 gcd의 계산 또한 마찬가지로 빠르다. mod p와 mod q의 제곱근을 계산하는데 필요한 modular exponentiations는 successive squaring(연속제곱법)을 사용해서 빠르게 계산할 수 있다. 

 

---

n = pq가 3 (mod 4)와 합동이고 두 소수의 곱일 때, y는 n에 대해서 서로소이며 mod n에 대해서 제곱근을 가진다고 가정한다. 4개의 해를 찾는 것은 계산상 n을 인수분해하는 것과 같다. 

다시 말하면 해를 찾을 수 있다면 n을 쉽게 인수분해할 수 있고, 반대로 n을 인수분해할 수 있다면 해를 쉽게 찾을 수 있다.