모듈러 제곱근

모듈러 제곱근(Modular square root)은 모듈러산술에서 이차 합동방정식 [math]\displaystyle{ x^2 \equiv a \pmod n }[/math]의 해를 말한다. [math]\displaystyle{ a, n }[/math]은 알고 있는 값이고, 좌변의 [math]\displaystyle{ x }[/math]는 미지수이다.

이차합동식의 해의 존재성

합동식의 법 [math]\displaystyle{ n }[/math]의 특징에 따라 결정된다.

• [math]\displaystyle{ n=2 }[/math]이면 [math]\displaystyle{ a \in \{0, 1\} }[/math]인 경우만 생각하면 되고, 해는 [math]\displaystyle{ x \equiv a \pmod n }[/math]이다.
• [math]\displaystyle{ n }[/math]이 소수이면 이차잉여 여부가 해의 존재 여부를 결정한다. [math]\displaystyle{ n \mid a }[/math]이면 방정식의 해는 [math]\displaystyle{ x \equiv 0 \pmod n }[/math]이다. [math]\displaystyle{ \gcd(a, n)=1 }[/math]인 경우, 르장드르 기호 값을 먼저 계산한다. [math]\displaystyle{ \left(\frac{a}{n}\right)=1 }[/math], 즉 [math]\displaystyle{ a }[/math]가 법 [math]\displaystyle{ n }[/math]에 대한 이차잉여일 때에는 해가 두 개 존재하고, 이차잉여가 아니면 해는 없다.
• [math]\displaystyle{ n }[/math]이 소수의 거듭제곱이면 복잡한 경우의 수가 나오는데, 이는 아래 문단에서 서술.
• [math]\displaystyle{ n }[/math]이 합성수이고, 소수의 거듭제곱이 아니면 [math]\displaystyle{ n=p_1^{r_1}p_2^{r_2} \cdots p_k^{r_k} }[/math]과 같이 소인수분해를 해서 [math]\displaystyle{ x^2 \equiv a \pmod{p_i^{r_i}} (1 \leq i \leq k) }[/math]로 방정식을 [math]\displaystyle{ k }[/math]개로 쪼갠다. 각 방정식을 푼 다음 원래 법 [math]\displaystyle{ n }[/math]에 대한 해를 도출한다.

법이 홀수 소수일 때

이와 관련한 내용은 토넬리-섕크스 알고리즘에서 볼 수 있습니다.

[math]\displaystyle{ n \equiv 3 \pmod 4 }[/math]이면 해는 어렵지 않게 구할 수 있다. [math]\displaystyle{ x^2 \equiv a \pmod n }[/math]에서 [math]\displaystyle{ a }[/math]가 이차잉여라는 사실을 알고 있다면, 오일러의 규준에 의해 [math]\displaystyle{ a^{\frac{n-1}{2}} \equiv 1 \pmod n }[/math]이다. 이를 주어진 방정식에 대입하면 [math]\displaystyle{ x^2 \equiv a^{\frac{n+1}{2}} \pmod n }[/math]이다. 여기서 [math]\displaystyle{ 4 \mid n+1 }[/math]이므로 우변의 지수는 짝수이며, 이에 따라 [math]\displaystyle{ x \equiv \pm a^{\frac{n+1}{4}} \pmod n }[/math]임을 알 수 있다.

[math]\displaystyle{ n \equiv 1 \pmod 4 }[/math], 즉 피타고라스 소수인 경우 셈법은 복잡해진다. [math]\displaystyle{ n \equiv 5 \pmod 8 }[/math]일 때는 아래 방법으로 그나마 간결하게 해를 구할 수 있다.

• [math]\displaystyle{ \left(\frac{a}{n}\right)=1, \left(\frac{2}{n}\right)=-1 }[/math]이므로 [math]\displaystyle{ (2a)^{\frac{n-1}{2}} \equiv -1 \pmod n }[/math]이다.
• [math]\displaystyle{ i \equiv (2a)^{\frac{n-1}{4}} \pmod n }[/math]은 -1의 모듈러 제곱근이다. 즉 [math]\displaystyle{ i^2+1 \equiv 0 \pmod n }[/math]. 그러면 [math]\displaystyle{ (i-1)^2 \equiv -2i \pmod n }[/math]이다.
• [math]\displaystyle{ x^2 \equiv a \equiv -a(2a)^{\frac{n-1}{2}} \equiv a^2 \cdot (-2)(2a)^{\frac{n-3}{2}} \equiv a^2(2a)^{\frac{n-5}{4}}(-2i) \pmod n }[/math]과 같이 변형한다. 이는 우변을 완전제곱식 모양을 만들기 위함이며, [math]\displaystyle{ \frac{n-5}{4} }[/math]가 짝수임에 주목한다. 양 변에 제곱근을 취하면 [math]\displaystyle{ x \equiv \pm a(2a)^{\frac{n-5}{8}}(i-1) \pmod n }[/math]이다.
• [math]\displaystyle{ j \equiv (2a)^{\frac{n-5}{8}} \pmod n }[/math]이라 하면 [math]\displaystyle{ x \equiv \pm aj(2aj^2-1) \pmod n }[/math]과 같이 정리된다.

[math]\displaystyle{ n \equiv 1 \pmod 8 }[/math]이면 위 방법마저 통하지 않고, 토넬리-섕크스 알고리즘을 이용한다. 구체적인 방법과 적용 예는 해당 문서에 소개되어 있다.

적용 예

아래 예시들은 방정식의 우변이 해당 법에 대한 이차잉여라는 사실을 확인하고 계산을 진행한다.

1. [math]\displaystyle{ x^2 \equiv 23 \pmod{83} }[/math]

   83은 4로 나눈 나머지가 3이므로 해를 어렵지 않게 구할 수 있다.

   [math]\displaystyle{ \frac{83+1}{4}=21, x \equiv 23^{21} \equiv \pm 40 \pmod{83} }[/math]

   따라서 [math]\displaystyle{ x \equiv 40 \text{ or } 43 \pmod{83} }[/math]이며, 검산을 하면 주어진 방정식이 성립함을 알 수 있다.

2. [math]\displaystyle{ x^2 \equiv 21 \pmod{109} }[/math]

   109는 8로 나눈 나머지가 5이므로 위 문단의 두 번째 방법을 이용한다.

   [math]\displaystyle{ \frac{109-5}{8}=13, j \equiv (2\cdot 21)^{13} \equiv 50 \pmod{109} }[/math]

   [math]\displaystyle{ x \equiv \pm 21 \cdot 50 \cdot (42 \cdot 50^2-1) \equiv \pm 28 \pmod{109} }[/math]

   결과를 정리하면 [math]\displaystyle{ x \equiv 28 \text{ or } 81 \pmod{109} }[/math]이다.

법이 소수의 거듭제곱일 때

[math]\displaystyle{ x^2 \equiv a \pmod{p^{\lambda}}, \lambda \geq 2 }[/math]인 경우 [math]\displaystyle{ a, p }[/math]가 서로소인지 여부에 따라 달려 있다.

• [math]\displaystyle{ p \mid a }[/math]이면 [math]\displaystyle{ p \mid x }[/math]이어야 하고, 그에 따라 [math]\displaystyle{ p^2 \mid a }[/math] 조건이 따라온다.
  • [math]\displaystyle{ p^2 \nmid a }[/math]인 경우 해는 없다.
  • [math]\displaystyle{ x=py, a=p^2b }[/math]을 대입하면 [math]\displaystyle{ p^2y^2 \equiv p^2b \pmod{p^{\lambda}} }[/math]이고, 간단히 하면 [math]\displaystyle{ y^2 \equiv b \pmod{p^{\lambda-2}} }[/math]이다.

이처럼 [math]\displaystyle{ p \mid a }[/math]인 경우는 합동식의 각 항을 [math]\displaystyle{ p^2 }[/math]씩 나눠서 [math]\displaystyle{ p }[/math]의 차수를 떨어뜨릴 수 있다. 따라서 아래 풀이법은 [math]\displaystyle{ p \nmid a }[/math]라는 전제를 깔고 들어간다.

2의 거듭제곱

[math]\displaystyle{ p=2 }[/math]일 때, 해를 구하기 위한 기본형을 상정한다.

• [math]\displaystyle{ x^2 \equiv 1 \pmod 4 \Rightarrow x \equiv 1 \pmod 2 }[/math]
• [math]\displaystyle{ x^2 \equiv 1 \pmod 8 \Rightarrow x \equiv 1 \pmod 2 }[/math]
• [math]\displaystyle{ x^2 \equiv 1 \pmod 16 \Rightarrow x \equiv \pm 1 \pmod 8 }[/math]
• [math]\displaystyle{ x^2 \equiv 9 \pmod 16 \Rightarrow x \equiv \pm 3 \pmod 8 }[/math]
• [math]\displaystyle{ x^2 \equiv 3 \pmod 4 \text{ or } x^2 \equiv 5 \pmod 8 }[/math]의 해는 없다.

[math]\displaystyle{ \lambda \geq 5 }[/math]일 때에는 문자를 치환한다.

• 먼저 [math]\displaystyle{ x^2 \equiv a \pmod{2^{\lambda}} }[/math]를 [math]\displaystyle{ x^2 \equiv a \pmod{16} }[/math]으로 간소화하고 이에 대해 [math]\displaystyle{ x \equiv \pm c \pmod 8 }[/math]을 도출한다. 이때 위 기본형에서 알 수 있듯이 [math]\displaystyle{ c }[/math]는 1과 3 둘 중 하나다.
• [math]\displaystyle{ x_1=8k+c }[/math]를 원래 방정식에 대입한다. 그러면 [math]\displaystyle{ 64k^2+16ck \equiv a-c^2 \pmod{2^{\lambda}} }[/math]가 된다.
• 이 방정식의 양 변과 법을 공통 약수인 16으로 나눈다. 그러면 [math]\displaystyle{ 4k^2+ck \equiv (a-c^2)/16 \pmod{2^{\lambda-4}} }[/math]이며, 법을 4로 축소하면 [math]\displaystyle{ ck \equiv (a-c^2)/16 \pmod{4} }[/math]이다.즉 [math]\displaystyle{ k }[/math]에 관한 일차합동식이 되어 어렵지 않게 구할 수 있다.
  • [math]\displaystyle{ \lambda=6 }[/math]이면 위 방정식을 풀어서 [math]\displaystyle{ k }[/math]를 구하고 x에 대입한다.
  • [math]\displaystyle{ \lambda=5 }[/math]이면 [math]\displaystyle{ ck \equiv (a-c^2)/16 \pmod{2} }[/math]로부터 [math]\displaystyle{ k }[/math]는 홀수임을 알아낸다.
  • [math]\displaystyle{ \lambda \geq 7 }[/math]이면 문자 치환과 차수 떨어뜨리기를 반복한다. (아래 예시 참고)

이렇게 해서 [math]\displaystyle{ \pm x_1 }[/math]이 준 방정식의 해가 된다. [math]\displaystyle{ x_2=8k-c }[/math]를 시도하면 [math]\displaystyle{ x_2 \equiv -x_1 \pmod{2^{\lambda}} }[/math]가 도출되며, [math]\displaystyle{ x_2 }[/math]에 대해 별도로 문자 치환을 다시 시도할 필요는 없다.

이해를 돕기 위한 예시로 [math]\displaystyle{ x^2 \equiv 932 \pmod{2048} }[/math]을 풀어보자.

• 먼저 합동식의 우변은 4의 배수이므로 [math]\displaystyle{ x=2y }[/math]를 대입해서 법의 차수를 내린다. [math]\displaystyle{ 4y^2 \equiv 932 \pmod{2048} }[/math]을 간단히 하면 [math]\displaystyle{ y^2 \equiv 233 \pmod{512} }[/math]이다.
• 법 16에 대한 식으로 간소화하면 [math]\displaystyle{ y^2 \equiv 9 \pmod{16} }[/math]이며 기본형 조건에 의해 [math]\displaystyle{ y \equiv \pm 3 \pmod 8 }[/math]이다.
• [math]\displaystyle{ y=8k+3 }[/math]을 방정식에 대입하면 [math]\displaystyle{ 64k^2+48k \equiv 224 \pmod{512} }[/math]이고, 공통 약수인 16으로 나누면 [math]\displaystyle{ 4k^2+3k \equiv 14 \pmod{32} }[/math](◇)이다. [math]\displaystyle{ k^2 }[/math]의 계수가 4이므로 방정식의 법을 4로 축소하면 [math]\displaystyle{ 3k \equiv 2, k \equiv 2 \pmod 4 }[/math]임을 알아낸다.
• (◇) 식에다 [math]\displaystyle{ k=4l+2 }[/math]로 문자 치환을 다시 시도한다. [math]\displaystyle{ (4k+3)k=(16l+11)(4l+2) \equiv 14 \pmod{32} }[/math]를 정리하면 [math]\displaystyle{ 12l \equiv 24 \pmod{32} }[/math]가 나오고, 공통 약수인 4로 나누면 [math]\displaystyle{ 3l \equiv 6 \pmod 8, l \equiv 2 \pmod 8 }[/math]이 나온다. 이 단계에서는 법을 축소하지 않았으므로, 문자 치환을 계속할 필요는 없다.
• 문자 치환을 거슬러 올라간다. [math]\displaystyle{ 4l \equiv 8 \pmod{32}, k=4l+2 \equiv 10 \pmod{32}, 8k \equiv 80 \pmod{256}, y=8k+3 \equiv 83 \pmod{256} }[/math]
• 만약 [math]\displaystyle{ y=8k-3 }[/math]을 시도했다면 [math]\displaystyle{ y \equiv -83 \pmod{256} }[/math]을 찾았을 것이다. 따라서 [math]\displaystyle{ y \equiv \pm 83 \pmod{256} }[/math]이며, 원래 변수는 [math]\displaystyle{ x=2y \equiv \pm 166 \pmod{512} }[/math]이다.
• 검산: [math]\displaystyle{ x=512n \pm 166 }[/math]을 방정식에 대입하면 [math]\displaystyle{ x^2=2048n(128n \pm 83)+166^2 \equiv 932 \pmod{2048} }[/math]

원래 방정식은 2048을 법으로 하는 합동식이었지만 구한 결과는 512가 기준이 되었다. 이처럼 법이 소수의 거듭제곱일 때에는 방정식의 해가 원래 조건식과 다른 법을 기준으로 나오기도 한다.

홀수 소수의 거듭제곱

기본형만 다를 뿐 위의 2의 거듭제곱과 같이 문자 치환, 법의 축소, 공통 약수 약분을 동원하여 푸는 것은 같다.

• [math]\displaystyle{ p \mid a, p^2 \nmid a }[/math]이면 [math]\displaystyle{ x^2 \equiv a \pmod{p^{\lambda}} }[/math]의 해는 존재하지 않는다
• [math]\displaystyle{ p^2 \mid a }[/math]이면 [math]\displaystyle{ x=py }[/math]로 치환하여 항의 계수와 상수항들을 각각 [math]\displaystyle{ p^2 }[/math]으로 나눈다.
• [math]\displaystyle{ p \nmid a }[/math]이면 합동식의 법을 [math]\displaystyle{ p }[/math]로 축소하여 이차합동식을 푼다. (홀수 소수의 거듭제곱에서는 이 단계가 기본형이다)
• [math]\displaystyle{ x \equiv \pm c \pmod p }[/math]이 나오면 [math]\displaystyle{ x=pk+c }[/math]로 치환하여 원 방정식에 대입하고, 필요 시 법의 축소와 약분을 반복한다.
• 문자 치환으로 [math]\displaystyle{ x \equiv e \pmod{p^{\lambda'}} }[/math]을 도출했다면 구하고자 하는 해는 [math]\displaystyle{ x \equiv \pm e \pmod{p^{\lambda'}} }[/math]이다.

예시 문제로 [math]\displaystyle{ x^2 \equiv 430 \pmod{729} }[/math]를 풀어보자. 이 문제에서는 합동식의 우변이 729와 서로소이므로, 바로 법을 축소한다. 출발점은 법 3으로 삼아도 되지만 [math]\displaystyle{ x^2 \equiv 7 \pmod 9 }[/math]의 해가 [math]\displaystyle{ x \equiv \pm 4 \pmod 9 }[/math]임을 알고 있다면 법 9에서 출발해도 된다.

• [math]\displaystyle{ x=9k+4 }[/math]라 하면 [math]\displaystyle{ 81k^2+72k \equiv 414 \pmod{729} }[/math]이다. 공통 약수인 9로 나누면 [math]\displaystyle{ 9k^2+8k \equiv 46 \pmod{81} }[/math]이며, [math]\displaystyle{ k^2 }[/math]의 계수가 9이므로 법을 9로 축소한다. 그러면 [math]\displaystyle{ 8k \equiv 1 \pmod 9 }[/math]이고, 일차합동식을 풀면 [math]\displaystyle{ k \equiv 8 \pmod 9 }[/math]이다.
• 이제 [math]\displaystyle{ k=9l+8 }[/math]이라 하면 [math]\displaystyle{ (9k+8)k=(81l+80)(9l+8) \equiv 46 \pmod{81} }[/math]이며, 정리하면 [math]\displaystyle{ -9l \equiv 54 \pmod{81} }[/math]이다. 합동식에서 [math]\displaystyle{ l^2 }[/math]의 계수가 0으로 사라졌기에 법을 다시 축소할 필요는 없으며, 해는 이 단계에서 도출된다.
• [math]\displaystyle{ 9l \equiv 27 \pmod{81} }[/math]에서 문자 치환을 거슬러간다. [math]\displaystyle{ k \equiv 35 \pmod{81}, 9k \equiv 315 \pmod{729}, x \equiv 319 \pmod{729} }[/math]이다. 만약 [math]\displaystyle{ x=9k-4 }[/math]에서 출발했다면 [math]\displaystyle{ x \equiv -319 \pmod{729} }[/math]를 얻어냈을 것이다.
• 구하는 해는 [math]\displaystyle{ x \equiv 319 \text{ or } 410 \pmod{729} }[/math]

법 9, 25, 49, 121과 같은 소수의 제곱을 법으로 하는 이차합동식은 위에서 소개한 문자 치환을 한 단계만 거치면 해를 구할 수 있다.

법이 합성수일 때

[math]\displaystyle{ n=uv, \gcd(u, v)=1 }[/math]인 두 약수가 존재한다고 할 때, 주어진 합동식은 연립방정식으로 바뀐다.

[math]\displaystyle{ \begin{cases} x^2 \equiv a \pmod u \\ x^2 \equiv a \pmod v \end{cases} }[/math]

만약 각각의 약수가 원래 합성수와 같이 서로소인 두 약수의 곱으로 나타난다면, 연립방정식의 수는 더 늘어난다. 일반적으로 [math]\displaystyle{ n= \prod_{1 \leq i \leq k} p_i^{r_i} }[/math]의 꼴의 합성수는 [math]\displaystyle{ x^2 \equiv a \pmod{p_i^{r_i}} }[/math] 꼴의 방정식을 각각 풀어야 하며, 방정식은 [math]\displaystyle{ k }[/math]개, 즉 서로 다른 소인수의 개수만큼 분화한다.

분화한 모든 방정식에서 해가 나와야 원래 방정식에도 해가 존재한다. 만약 [math]\displaystyle{ a }[/math]가 이차비잉여가 되는 법 [math]\displaystyle{ p_i^{r_i} }[/math]이 하나라도 있다면, 원 방정식의 해는 존재하지 않는다.

가장 간단한 경우로 법이 서로 다른 두 소수의 곱일 때, [math]\displaystyle{ x \equiv \pm c_1 \pmod u, x \equiv \pm c_2 \pmod v }[/math]와 같이 구해졌다고 하면 각 부호, 즉 (+, +), (+, -), (-, +), (-, -)에 대해 [math]\displaystyle{ x \equiv c \pmod{uv} }[/math]를 도출한다. 즉 이 경우 해는 최대 4개 나오고, 서로 다른 [math]\displaystyle{ k }[/math]개 소수의 곱이었다면 해의 최대 개수는 [math]\displaystyle{ 2^k }[/math]이다. 합동식의 법을 [math]\displaystyle{ n }[/math]으로 병합하는 단계는 중국인의 나머지 정리로 풀 수 있다.

적용 예

• 문제: 1억 미만의 자연수가 있다. 이 수는 완전제곱수이고, 뒤의 네 자리 부분이 앞의 나머지 자리 부분에서 2를 더한 것과 같다. 이 조건을 만족하는 자연수를 모두 구하면?

이 문제의 조건을 달리 표현하면 [math]\displaystyle{ N=x^2=a\cdot 10^4+(a+2), x \lt 10^4, a, x \in \mathbb{N} }[/math]인 [math]\displaystyle{ N }[/math]을 구하라는 뜻이 된다. 해당 조건식은 [math]\displaystyle{ x^2=10001a+2 }[/math]로 쓸 수 있는데, 이를 이차합동식으로 바꾸면 [math]\displaystyle{ x^2 \equiv 2 \pmod{10001} }[/math]이다.

한편 [math]\displaystyle{ 10001=73 \cdot 137 }[/math]로 소인수분해가 되므로, 위 방정식은 [math]\displaystyle{ \begin{cases}x^2 \equiv 2 \pmod{73} \\ x^2 \equiv 2 \pmod{137} \end{cases} }[/math]과 같이 나눠서 푼다.

73과 137 둘 다 8로 나눈 나머지가 1이므로, 풀이 방식은 토넬리-섕크스 알고리즘을 이용한다. 결과는 [math]\displaystyle{ x \equiv \pm 32 \pmod{73}, x \equiv \pm 31 \pmod{137} }[/math]이다. 두 조건식에서 (+, +) 부호를 고르면 [math]\displaystyle{ x \equiv 1127 \pmod{10001} }[/math]이고, (+, -) 부호를 고르면 [math]\displaystyle{ x \equiv 9011 \pmod{10001} }[/math]이다. 참고로 (-, -)와 (-, +)의 경우 앞의 두 경우에서 해의 부호만 바뀐 형태가 나온다. 즉 전체 해는 [math]\displaystyle{ x \equiv y \pmod{10001}, y \in \{990, 1127, 8874, 9011 \} }[/math]이며, 원래 문제의 조건에 대입하면 구하는 답은 아래 자연수들이다.

[math]\displaystyle{ 990^2=980100, 1127^2=1270129, 8874^2=78747876, 9011^2=81198121 }[/math]

만약 문제에서 2대신 3으로 바꾼다면 문제의 답은 존재하지 않는다. 같은 방법으로 접근하면 합동식 [math]\displaystyle{ x^2 \equiv 3 \pmod{137} }[/math]을 풀어야 하는데, 3은 법 137에 대한 이차비잉여이기 때문이다.