이차 체

이차 체(Quadratic sieve)는 큰 수의 소인수분해를 빠르게 셈하는 알고리즘이다. 1981년 미국의 수학자인 칼 포메란스(Carl Pomerance)가 고안하였고, 실제로 1994년 이 방법으로 RSA-129의 해답을 찾아냈다.

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

아이디어

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

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

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

먼저 각 합동식의 우변을 소인수분해하면 [math]\displaystyle{ \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]\displaystyle{ (791 \cdot 793)^2 \equiv (2^6 \cdot 5)^2 \pmod N }[/math]이제 양 변의 괄호 내부 항을 셈해서 [math]\displaystyle{ \mod N }[/math]을 취하면 [math]\displaystyle{ 1614^2 \equiv 320^2 \pmod N, (x, y)=(1614, 320) }[/math]을 찾게 된다. 따라서 [math]\displaystyle{ \gcd(x+y, N)=\gcd(1934, 625649)=967, \gcd(x-y, N)=\gcd(1294, 625649)=647 }[/math]을 이끌어내고, [math]\displaystyle{ N=647 \cdot 967 }[/math]임을 확인할 수 있다.

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

소인수 기저

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

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

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

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

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

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

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

알고리즘

소인수분해를 할 합성수 [math]\displaystyle{ N }[/math]을 입력 받고 다음 과정을 시행한다.

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

적용 예

[math]\displaystyle{ N=1874583551 }[/math]을 이차 체를 이용하여 소인수분해를 해보자.

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

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

이렇게 작은 소수들에 대해 이차 잉여 여부를 조사하면 아래와 같이 소인수 기저를 얻는다.

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

• 예를 들어 [math]\displaystyle{ y(43296, 1) = -39935 = (-1) \cdot 5 \cdot 7^2 \cdot 163 }[/math]의 경우 가장 큰 소인수가 241보다 작으므로 정보 하나를 얻었다. 이제 해당 소인수들을 위의 소인수 기저 상의 번호로 대응하고, 각 소인수의 지수를 벡터 형태로 쓴다.
  • [math]\displaystyle{ 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]\displaystyle{ y(43306, 1) = 826085 = 5 \cdot 13 \cdot 71 \cdot 179 }[/math]
  • [math]\displaystyle{ 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]\displaystyle{ v_k }[/math]를 정리한다. 아래 표는 해당 벡터를 가장 나중 성분이 0으로 연속된 개수가 많은 순으로 정렬한 것이다.

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

[math]\displaystyle{ \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]\displaystyle{ \text{LHS} = (129896 \cdot 43336 \cdot \cdots 129884)^2 \equiv 1272181894^2 \pmod N }[/math]

그 다음 우변의 경우 지수끼리 먼저 더하고 제곱을 묶어낸 다음 내부의 항들끼리 계산한다. (-1) 항은 짝수 개가 모여 1이 되므로 곱셈에서 사라진다.

• [math]\displaystyle{ \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]\displaystyle{ X^2 \equiv Y^2 \pmod N, X=1272181894, Y=1457008352 }[/math]를 얻어냈다. 이로부터 [math]\displaystyle{ \gcd(X+Y, N)=9473 }[/math]과 같이 약수 하나를 찾고, [math]\displaystyle{ N=1874583551=9473 \cdot 197887 }[/math]이 되어 알고리즘은 성공한다. (물론 [math]\displaystyle{ \gcd(X-Y, N)=197887 }[/math]을 이용해도 된다)

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

보충 설명

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

소인수 기저 관련

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

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

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

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

이를 방지하려면 모든 홀수 소수에 대해 르장드르 기호 값이 1인 계수를 고르면 된다. 즉 [math]\displaystyle{ 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]\displaystyle{ y(x, a)=x^2-a^2N }[/math]으로 함수를 지정하는 이유이다.

같이 보기

• 유리수 체
• 수체 체