이차 체 편집하기

'''이차 체'''(Quadratic sieve)는 큰 수의 [[소인수분해]]를 빠르게 셈하는 알고리즘이다. 1981년 미국의 수학자인 칼 포메란스(Carl Pomerance)가 고안하였고, 실제로 1994년 이 방법으로 [[RSA 수|RSA-129]]의 해답을 찾아냈다.<ref>Mark Janeba(1994), [http://www.willamette.edu/~mjaneba/rsa129.html Factoring Challenge Conquered]</ref>

이 방법은 현재까지 알려진 전통적 소인수분해법<ref>일반 컴퓨터로 푸는 방법으로, 양자컴퓨터를 이용한 [[쇼어 소인수분해법]]은 논외.</ref> 중 [[수체 체]] 다음으로 빠르며, 알고리즘 설계는 이차 체 쪽이 훨씬 간결하다.  <math>10^{70} < N < 10^{100}</math>범위, 즉 대략 [[무량대수]]에서 [[구골]] 사이 크기에서 가장 빠르게 작동하는 것으로 알려져 있다. 이 범위 아래 수는 [[렌스트라 타원 곡선 소인수분해법]]을 많이 이용한다.

== 아이디어 ==
이 알고리즘의 기본 목표는 소인수분해하고자 하는 합성수 <math>N</math>에 대해 <math>x^2 \equiv y^2 \pmod N</math>을 만족하는 순서쌍 <math>(x, y)</math>를 찾고, <math>\gcd(x+y, N), \gcd(x-y, N)</math>을 셈해서 해당 수의 비자명한 약수를 찾는 것이다. 사실상 [[페르마 소인수분해법]]을 효율적으로 개선한 방법이라 할 수 있다.

한 예로 <math>N=625649</math>를 소인수분해하려고 한다. 여기서 <math>\lfloor \sqrt{N} \rfloor = 790</math>임에 착안하여 이 주변에서 제곱 합동식을 찾아본다.

<math>N= \begin{cases} 791^2-32 \\ 792^2-1615 \\ 793^2-3200 \end{cases}</math>을 변형하면 <math>\begin{cases} 791^2 \equiv 32 \\ 792^2 \equiv 1615 \\ 793^2 \equiv 3200 \end{cases} \pmod N</math>이라 쓸 수 있다. [[페르마 소인수분해법]]을 따른다면 값을 차츰 올려서 <math>N=807^2-160^2=647 \cdot 967</math>과 같이 제곱의 차 형태를 찾기에 이를 것이다. 그런데 이차 체에서는 앞서 찾은 합동식들을 조합한다.

먼저 각 합동식의 우변을 소인수분해하면 <math>\begin{cases} 791^2 \equiv 2^5 \\ 792^2 \equiv 5\cdot 17\cdot 19 \\ 793^2 \equiv 2^7\cdot 5^2 \end{cases} \pmod N</math>이 된다. 여기서 셋 중 어느 것도 우변이 제곱이 아니지만, 첫째 식과 셋째 식을 곱한다면 양 변이 제곱이 되게끔 만들 수 있다.

<math>(791 \cdot 793)^2 \equiv (2^6 \cdot 5)^2 \pmod N</math>이제 양 변의 괄호 내부 항을 셈해서 <math>\mod N</math>을 취하면 <math>1614^2 \equiv 320^2 \pmod N, (x, y)=(1614, 320)</math>을 찾게 된다. 따라서 <math>\gcd(x+y, N)=\gcd(1934, 625649)=967, \gcd(x-y, N)=\gcd(1294, 625649)=647</math>을 이끌어내고, <math>N=647 \cdot 967</math>임을 확인할 수 있다.

위 계산 방식이 이차 체의 접근 방식이다. 좌변을 "임의의 자연수의 제곱"으로 놓고 그 제곱수와 합동인 우변 값들을 찾는다. 그 다음 우변의 값들 중 곱해서 제곱수가 되는 조합을 찾아서 위 문단에서와 같이 제곱 합동식을 유도해낸다. 그리고 그 합동식으로부터 비자명한 약수를 찾으면, 알고리즘은 성공한다.

=== 소인수 기저 ===
임의의 자연수가 <math>n=p_1^{r_1}\cdot p_2^{r_2}\cdots \cdot p_k^{r_k}</math>와 같이 소인수분해될 때, 이 자연수가 [[제곱수]]이기 위한 필요충분조건은 <math>r_1 \equiv r_2 \equiv \cdots \equiv 0 \pmod 2</math>, 즉 모든 소인수의 지수가 짝수가 되는 것이다. 그러므로 앞서 말한 "우변의 곱으로 제곱수를 만들기"라는 목표는 곧 소인수의 지수의 홀짝성을 조사하는 일이 된다.

우리가 관심을 가질 합성수는 작은 소수들로 나누어지지 않는다는 전제를 깔고 들어간다. 직접 나누기로 쉽게 찾을 수 있기 때문. 그러므로 [[르장드르 기호]] 값인 <math>\left(\frac{N}{p} \right)</math>이 0이 되는 경우는 생각하지 않는다.

* 어떤 작은 소수 <math>p</math>와 서로소인 큰 합성수 <math>N</math>, 그리고 무작위로 고른 자연수 <math>x</math>에 대해, (□)<math>p \mid x^2-N</math>이 성립할 확률은 <math>\frac{1}{p}</math>이다.

하지만 이는 정확하지 않은 표현이다. 좀 더 엄밀히는 [[이차잉여]]로 확률을 구분해야 한다. 어떤 합동식 <math>N \equiv a^2 \pmod p</math>를 만족하는 <math>a (p \nmid a)</math>가 존재한다면, 즉 <math>N</math>이 법 <math>p</math>에 대한 이차잉여이면, <math>N-x^2 \equiv a^2-x^2 \equiv 0 \pmod p</math>가 되고, <math>x \equiv \pm a \pmod p</math>로 해가 두 개 존재한다. 반면 이차잉여가 아닌 경우, <math>N-x^2 \equiv 0 \pmod p</math>의 해는 존재하지 않는다. 따라서 위의 (□) 구절은 아래와 같이 고쳐야 한다.

* 3 이상인 소수에 대해 <math>p \mid x^2-N</math>이 성립할 확률은 <math>\left(\frac{N}{p} \right)=1</math>일 때 <math>\frac{2}{p}</math>, <math>\left(\frac{N}{p} \right)=-1</math>일 때 0이다. <math>p=2</math>의 경우 확률은 언제나 2분의 1이다.

가령 어떤 합성수가 법 5에 대한 이차잉여가 아니면 (즉 일의 자리가 3 또는 7이면) <math>N-x^2</math>의 값이 5의 배수가 되는 건 불가능하고, 이에 따라 소인수분해 시 소인수 5는 전혀 등장하지 않는다.

앞서 말한 "확률"이란 <math>N-x^2</math>을 소인수분해할 때 해당 소인수가 등장할 확률을 말한다. 소수가 작을수록 소인수는 빈번하게 등장하므로, 알고리즘을 세우기에 앞서 '''소인수 기저'''(factor base)를 작성해야 한다. 이는 <math>\left(\frac{N}{p} \right)=1</math>인 작은 소수들을 모은 집합을 말하며, 어떤 값이 이 기저 내에서 완전히 소인수분해가 되는지 여부를 알아본다. 단, 여기서는 <math>N-x^2<0</math>인 경우도 포함할 것이며, 이 경우 -1은 비록 소수가 아니지만 '부호' 역할을 하며 소인수 기저에 필요하다.

== 알고리즘 ==
소인수분해를 할 합성수 <math>N</math>을 입력 받고 다음 과정을 시행한다.

* 소인수 기저의 길이를 임의로 지정하거나, 소인수 크기의 상한값을 정한다.
* 소인수 기저가 될 집합인 <math>\mathcal{B}={-1, 2}</math>를 지정하고, <math>p=3</math>부터 시작해서 <math>\left(\frac{N}{p} \right)</math>의 값이 +1인 소수들만을 모아서 위 집합에 집어넣는다.
** <math>\mathcal{B}={p_0, p_1, \cdots p_{n-1}}\ (p_0=-1)</math>과 같이 정리가 되면 이 목록을 메모리에 저장한다.
* 함수 <math>y(x, a)=x^2-a^2N</math>을 지정한다.
* <math>y(x, a)</math>의 절댓값이 작은 순서쌍 <math>(x, a)</math>를 중심으로 함숫값들을 셈한다. 여기서 순서쌍 내 두 값은 서로소이다.
** 즉 <math>a=1</math>부터 시작해서 <math>x=\lfloor a\sqrt{N} \rfloor \pm \delta, \delta \in \{0, 1, 2, \cdots\}</math>를 차례대로 대입한다.
* <math>y(x)</math>의 값이 <math>\mathcal{B}</math> 내의 소인수들로 완전히 소인수분해가 되는지 여부를 조사한다.
** 이 조건을 만족하면 해당 합동식<math>x_k^2 \equiv y(x_k) \pmod N, y(x_k)=p_0^{r_{k0}}p_1^{r_{k1}}\cdot \cdots \cdot p_{n-1}^{r_{k(n-1)}}</math> 중 <math>x_k, u_k=(r_{k0}, r_{k1}, \cdots r_{k(n-1)})</math>을 메모리에 저장한다.
* (◇) <math>x_k, u_k</math>의 값들이 <math>m</math>쌍 모이면, 합동식 찾기를 종료한다. 여기서 <math>m (\leq n)</math>은 아래 계산을 위한 충분한 개수이다.
* <math>v_k=(s_{k0}, s_{k1}, \cdots s_{k(n-1)}), s=\begin{cases} 0 (r \text{even}) \\ 1 (r \text{odd}) \end{cases}</math>를 셈한다. 즉 <math>u_k</math>가 소인수의 실제 지수를 기록한 것이라면, <math>v_k</math>는 지수의 홀짝 여부를 나타낸 것이다.
* <math>\displaystyle \sum_{k \in A} v_k=0</math>을 만족하는 <math>A \subset \{0, 1, \cdots m \}</math>를 찾는다. 여기서 벡터의 연산은 환 <math>\mathbb{Z}/2\mathbb{Z}</math> 내에서 이루어지며, 모든 성분은 0 또는 1로 구성된다. 또, 해당 조건을 만족하는 부분집합 <math>A</math>는 여러 개 나올 수 있지만 알고리즘에서는 그 중 하나를 찾아낸다.
** 만약 부분집합을 찾지 못했다면, (◇) 단계로 돌아가서 합동식을 추가로 찾고 (즉 <math>m</math>의 값을 올리고) 부분집합 찾기를 다시 시도한다.
* <math>j \in A</math>인 인덱스에 대해, 앞서 저장해둔 <math>x_j, u_j=(r_{0j}, r_{1j}, \cdots r_{(n-1)j})</math> 식들을 모두 불러온다.
* <math>\displaystyle X=\prod_{j}x_j,\ R_i=\frac{1}{2} \sum_{j}r_{ij},\ Y=\prod_{i=0}^{n} p_i^{R_i}</math>를 셈하면 구하려는 제곱합동식 <math>X^2 \equiv Y^2 \pmod N</math>을 이끌어낸다.
* <math>\gcd(X \pm Y, N)</math>을 셈해서 주어진 합성수의 비자명한 약수를 찾아내면, 알고리즘은 성공한다.

== 적용 예 ==
<math>N=1874583551</math>을 이차 체를 이용하여 소인수분해를 해보자.

가장 먼저 구성할 것은 소인수 기저이다. <math>p \geq 3</math>인 소수들에 대해 <math>\left(\frac{N}{p}\right)=1</math>을 만족하는 것들을 모아 소인수 기저에 넣는다. 여기서는 -1과 2를 포함해서 30개를 찾아보자.

* <math>N \equiv 2 \pmod 3 \Rightarrow \left(\frac{N}{p}\right)=\left(\frac{2}{3}\right) =-1</math> 그러므로 3은 소인수 기저에 들어가지 않는다.
* <math>N \equiv 1 \pmod 5 \Rightarrow \left(\frac{N}{p}\right)=\left(\frac{1}{5}\right) =1</math> 그러므로 5는 소인수 기저에 들어간다.

이렇게 작은 소수들에 대해 이차 잉여 여부를 조사하면 아래와 같이 소인수 기저를 얻는다.
* <math>\begin{align} \mathcal{B} = &\{-1, 2, 5, 7, 11, 13, 31, 37, 41, 43, 67, 71, 89, 107, 109, 113,\\ &131, 139, 151, 163, 179, 181, 191, 193, 197, 211, 229, 233, 239, 241\} \end{align}</math>

다음으로 함수 <math>y(x, a)=x^2-a^2N</math>을 지정하고, <math>a=1</math>부터 시작해서 <math>|y(x, a)| < 10^{7}</math>인 조건 내에서 함숫값들을 셈한다. 그리고 각 함숫값들이 위의 소인수 기저로 완전히 소인수분해가 되는 지 확인한다. (즉 가장 큰 소인수가 241 이하이면 된다)

* 예를 들어 <math>y(43296, 1) = -39935 = (-1) \cdot 5 \cdot 7^2 \cdot 163</math>의 경우 가장 큰 소인수가 241보다 작으므로 정보 하나를 얻었다. 이제 해당 소인수들을 위의 소인수 기저 상의 번호로 대응하고, 각 소인수의 지수를 벡터 형태로 쓴다.
** <math>x_1=43296, u_1=(1, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)</math>
** -1은 맨 앞 성분이고, 뒤이어 2, 5, 7, … 소인수의 지수 부분을 이어 적는다.
* 마찬가지로 다른 조건식들을 계속해서 찾는다: <math>y(43306, 1) = 826085 = 5 \cdot 13 \cdot 71 \cdot 179</math>
** <math>x_2=43306, u_2=(0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0)</math>

이렇게 해서 조건식 30개를 찾고 나면, 이제 주어진 벡터 <math>v_k</math>를 정리한다. 아래 표는 해당 벡터를 가장 나중 성분이 0으로 연속된 개수가 많은 순으로 정렬한 것이다.

{|class="wikitable mw-collapsible mw-collapsed"
! <math>k</math> !! <math>x_k, a_k</math> !! <math>y(x_k, a_k)</math> !! <math>v_k</math>
|-
| 1 || 129896, 3 || 1718857 || (0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
|-
| 2 || 43336, 1 || 3425345 || (0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
|-
| 3 || 43238, 1 || -5058907 || (1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
|-
| 4 || 216491, 5 || 3764306 || (0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
|-
| 5 || 43262, 1 || -2982907 || (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
|-
| 6 || 129853, 3 || -9450350 || (1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
|-
| 7 || 43235, 1 || -5318326 || (1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
|-
| 8 || 43278, 1 || -1598267 || (1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
|-
| 9 || 43377, 1 || 6980578 || (0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
|-
| 10 || 43309, 1 || 1085930 || (0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
|-
| 11 || 216483, 5 || 300514 || (0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
|-
| 12 || 86567, 2 || -4488715 || (1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
|-
| 13 || 43387, 1 || 7848218 || (0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
|-
| 14 || 43349, 1 || 4552250 || (0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
|-
| 15 || 43239, 1 || -4972430 || (1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
|-
| 16 || 43296, 1 || -39935 || (1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
|-
| 17 || 43306, 1 || 826085 || (0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0)
|-
| 18 || 216471, 5 || -4894934 || (1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0)
|-
| 19 || 259771, 6 || -4035395 || (1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0)
|-
| 20 || 86573, 2 || -3449875 || (1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0)
|-
| 21 || 43274, 1 || -1944475 || (1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0)
|-
| 22 || 43254, 1 || -3675035 || (1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0)
|-
| 23 || 216467, 5 || -6626686 || (1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0)
|-
| 24 || 43248, 1 || -4194047 || (1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0)
|-
| 25 || 43371, 1 || 6460090 || (0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0)
|-
| 26 || 86611, 2 || 3131117 || (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0)
|-
| 27 || 129884, 3 || -1398503 || (1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0)
|-
| 28 || 173179, 4 || -2370775 || (1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0)
|-
| 29 || 43245, 1 || -4453526 || (1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0)
|-
| 30 || 43267, 1 || -2550262 || (1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)
|-
|}

이제 표의 정보를 토대로 <math>\displaystyle \sum_{k \in A} v_k=0</math>을 만족하는 부분집합을 찾으면 <math>A= \{1, 2, 3, 8, 11, 13, 14, 22, 25, 27 \}</math>이 나온다. 이제 이들 번호에 해당하는 제곱합동식 <math>x_k^2 \equiv y(x_k, a_k) \pmod N</math>을 불러온다.

<math> \begin{cases} 129896^2 \equiv 7 \cdot 31 \cdot 89^2 \\ 43336^2 \equiv 5 \cdot 7^2 \cdot 11 \cdot 31 \cdot 41 \\ 43238^2 \equiv (-1) \cdot 7^6 \cdot 43 \\ 43278^2 \equiv (-1) \cdot 11 \cdot 31 \cdot 43 \cdot 109 \\ 216483^2 \equiv 2 \cdot 31 \cdot 37 \cdot 131 \\ 43387^2 \equiv 2 \cdot 7 \cdot 37 \cdot 109 \cdot 139 \\ 43349^2 \equiv 2 \cdot 5^3 \cdot 131 \cdot 139 \\ 43254^2 \equiv (-1) \cdot 5 \cdot 7 \cdot 13 \cdot 41 \cdot 197 \\ 43371^2 \equiv 2 \cdot 5 \cdot 7 \cdot 13 \cdot 31 \cdot 229 \\ 129884^2 \equiv (-1) \cdot 31 \cdot 197 \cdot 229 \end{cases} \pmod N</math>

주어진 식들을 모두 곱한다. 먼저 좌변의 경우 제곱을 묶고 그 항들끼리 계산한다.
* <math>\text{LHS} = (129896 \cdot 43336 \cdot \cdots 129884)^2 \equiv 1272181894^2 \pmod N</math>

그 다음 우변의 경우 지수끼리 먼저 더하고 제곱을 묶어낸 다음 내부의 항들끼리 계산한다. (-1) 항은 짝수 개가 모여 1이 되므로 곱셈에서 사라진다.
* <math>\text{RHS} = (2^2 \cdot 5^3 \cdot 7^6 \cdot 11 \cdot 13 \cdot 31^3 \cdot 37 \cdot 41 \cdot 43 \cdot 89 \cdot 109 \cdot 131 \cdot 139 \cdot 197 \cdot 229)^2 \equiv 1457008352^2 \pmod N</math>

따라서 우리는 제곱합동식 <math>X^2 \equiv Y^2 \pmod N, X=1272181894, Y=1457008352</math>를 얻어냈다. 이로부터 <math>\gcd(X+Y, N)=9473</math>과 같이 약수 하나를 찾고, <math>N=1874583551=9473 \cdot 197887</math>이 되어 알고리즘은 성공한다. (물론 <math>\gcd(X-Y, N)=197887</math>을 이용해도 된다)

※ '''참고''': 제곱합동식을 유도해냈다고 해서 반드시 알고리즘이 성공하는 것은 아니다. 위의 예시에서 제곱합동식이 만들어질 조건으로 <math>A=\{3, 4, 5, 7, 8, 9, 11, 14, 22, 23 \}</math>도 있긴 하나, 이 부분집합을 기준으로 계산하면 <math>805901911^2 \equiv 805901911^2 \pmod N</math>과 같이 자명한 합동식이 나와서, 원하는 약수를 얻어낼 수 없다. 비자명한 약수가 나오려면 <math>X \pm Y \not \equiv 0 \pmod N</math>이어야 한다.

== 보충 설명 ==
이상 소개한 이차 체는 합성수가 커질수록 [[수체 체]]와 더불어 진가를 발휘한다. 물론 여기서 합성수는 아주 큰 소수의 곱으로 이루어져 있을 때이다. 만약 작은 소인수들이 포함되어 있다면, 직접 나누기 및 [[렌스트라 타원 곡선 소인수분해법]] 등으로 소인수를 찾아서 사전에 수의 크기를 줄여놓는 것이 더 좋다. 그렇게 해서 남은 여인수가 여전히 큰 합성수이면, 최후의 한 방으로 이차 체나 수체 체를 적용한다.

=== 소인수 기저 관련 ===
이차 체의 핵심이 되는 소인수 기저를 구하는 목적은 바로 <math>p \mid x^2-a^2N</math> 조건식이 불가능한 작은 소수들을 사전에 걸러내는 것이다. 즉 <math>\left(\frac{N}{p} \right)=-1</math>인 소수들이 이에 해당하며, 이들 수로 나누어떨어지는지 여부를 확인할 필요는 없다. 가령 위에서 소개한 예시에서는 <math>x^2-a^2N</math>이 3으로 나누어떨어지는 경우가 '''절대 없기에''', 3의 배수 여부는 바로 스킵할 수 있다.

한편 <math>x^2 \equiv y \pmod N</math> 관계식에서 좌변은 임의의 자연수의 제곱이며 우변은 좌변을 <math>N</math>으로 나눈 나머지를 의미한다. 이때 우변의 절댓값이 가급적 작아야 소인수 기저 내의 소수들의 곱으로만 이루어진 합성수를 찾을 수 있다. 따라서 합동식을 조사할 때 <math>x \approx \sqrt{bN}</math> 범위에서 <math>y=x^2-bN, x^2 \equiv y \pmod N</math>을 찾게 된다.

그런데 여기서 <math>b=a^2</math>, 즉 계수는 1, 4, 9와 같이 완전제곱수가 되어야 하는데, 이는 바로 소인수 기저 때문이다. 소인수 기저는 <math>\mathcal{B}= \{-1, 2 \} \cup \left \{p: 3 \leq p \leq n, \left(\frac{N}{p} \right)=1 \right \}</math>과 같이 쓸 수 있다. (위 적용 예에서는 <math>n=250</math>)

문제는 저 [[르장드르 기호]] 조건인데, 가령 <math>x^2-bN</math>이 어떤 소수 <math>p</math>의 배수일 필요조건은 <math>x^2 \equiv bN \pmod p</math> 즉 <math>bN</math>이 법 <math>p</math>에 대한 [[이차잉여]]인 것이다. 다시 말해 <math>\left(\frac{bN}{p} \right)=1</math>이어야 하는데, 만약 <math>\left(\frac{N}{p} \right)=\left(\frac{b}{p} \right)=-1</math>이면 <math>p \not \in \mathcal{B}</math>이다. 즉 앞서 구한 소인수 기저 외의 소수로 나누어떨어질 수 있게 되므로, 소인수 기저의 이점이 무효화된다.

이를 방지하려면 모든 홀수 소수에 대해 르장드르 기호 값이 1인 계수를 고르면 된다. 즉 <math>b=a^2 \Rightarrow \left(\frac{bN}{p} \right) = \left(\frac{a}{p} \right)^2 \left(\frac{N}{p} \right) = \left(\frac{N}{p} \right)</math>이 되게 하면, 주어진 소인수 기저 내의 원소들로 유지할 수 있다. 이것이 <math>y(x, a)=x^2-a^2N</math>으로 함수를 지정하는 이유이다.

{{각주}}
{{수론 알고리즘}}
[[분류:알고리즘]]