유리수 체

유리수 체(Rational sieve)는 자연수를 소인수분해하는 방법으로, 제곱의 차 형태를 만들어낸다. 이차 체의 변형된 방법이자 수체 체의 가장 간단한 형태라 할 수 있다. 알고리즘의 효율 자체는 낮지만 과정은 간단한 편에 속한다.

아이디어

알고리즘의 목표는 주어진 홀수 합성수 [math]\displaystyle{ N }[/math]에 대해 제곱 합동식인 [math]\displaystyle{ x^2 \equiv y^2 \pmod N }[/math]을 찾는 것이다. 이차 체에서는 함수 [math]\displaystyle{ f(x, a)=x^2-a^2N }[/math]을 상정하고 [math]\displaystyle{ x^2 \equiv f(x, a) \pmod N }[/math]을 세운 다음 [math]\displaystyle{ \prod_{k=1}^{n} f(x_k, a_k)=y^2 }[/math]을 만족하는 순서쌍 [math]\displaystyle{ (x, a) }[/math]를 세우는 것이다. 여기서는 자유 변수를 [math]\displaystyle{ x^2 }[/math] 대신, 자잘한 소인수들로 나눠지는 자연수 기준으로 삼는다.

[math]\displaystyle{ \mathcal{B}=\{-1\} \cup \{\text{prime }p: p\lt M \} }[/math]는 특정 값 미만의 소수들과 부호 인자(-1)의 집합을 나타내며, 이를 소인수 기저라 한다. 유리수 체의 목표는 합동식 [math]\displaystyle{ z \equiv z+aN \pmod N }[/math]을 찾는 것이며, 조건은 [math]\displaystyle{ z, z+aN }[/math]이 [math]\displaystyle{ \mathcal{B} }[/math] 내의 소수들로 모두 소인수분해가 되는 것이다. 음수의 경우 (-1)의 지수를 1로 취급한다. 여기서 [math]\displaystyle{ a }[/math]는 0이 아닌 정수이다.

달리 말하면 유리수 [math]\displaystyle{ \frac{z+aN}{z} (z \nmid N) }[/math]이 기약분수이고, 분모·분자가 모두 해당 소인수 기저 내 소수들로 나누어질 때의 값을 취합하는 것이다. 이 조건을 만족하는 유리수를 [math]\displaystyle{ \text{#}(\mathcal{B}) }[/math]개 이상 찾으면, 그 유리수들의 집합의 부분집합 [math]\displaystyle{ A }[/math]가 존재해서 [math]\displaystyle{ \prod_{r_k \in A}r_k=s^2, s \in \mathbb{Q} }[/math]를 만족하게 된다.

여기서 [math]\displaystyle{ r_k=\frac{z_k+a_kN}{z_k}, s=\frac{y}{x} }[/math]라 하면, [math]\displaystyle{ x^2 \prod_{r_k \in A}(z_k+N) =y^2 \prod_{r_k \in A}z_k }[/math]와 같이 고쳐쓸 수 있다. 그런데 [math]\displaystyle{ \prod_{r_k \in A}(z_k+N) \equiv \prod_{r_k \in A}z_k \pmod N }[/math]이므로, 결국에는 [math]\displaystyle{ x^2 \equiv y^2 \pmod N }[/math]에 도달한다. 그리고 [math]\displaystyle{ \gcd(x \pm y, N) }[/math]을 셈해서 주어진 자연수의 비자명한 약수를 찾으면, 알고리즘은 성공한다.

알고리즘

소인수분해할 합성수 [math]\displaystyle{ N }[/math]을 입력 받고 다음 과정을 시행한다. 전체적인 과정은 이차 체와 흡사하다.

• (-1)을 포함하여 소인수 기저에 들어갈 소수의 개수를 정하고 소인수 기저 [math]\displaystyle{ \mathcal{B}=\{-1, 2, 3, \cdots p_m\} }[/math]을 세운다.
• [math]\displaystyle{ N }[/math]주변에서 [math]\displaystyle{ \mathcal{B} }[/math] 내의 소수들로 모두 나눠지는 자연수[math]\displaystyle{ w }[/math]를 찾는다. 그 다음 0 주변의 정수 [math]\displaystyle{ z=w-N }[/math] 역시 해당 소인수 기저의 소수들로 모두 나눠지는지 알아본다.
• 바로 위 조건을 만족하는 유리수 [math]\displaystyle{ \frac{u}{z} }[/math]의 소인수 지수를 순서쌍[math]\displaystyle{ u_k }[/math]와 홀짝 여부 순서쌍 [math]\displaystyle{ v_k }[/math]로 기록한다. 이때 분모 부분은 지수가 음수가 된다.
  • 이를테면 [math]\displaystyle{ \frac{2890}{9}=2 \cdot 3^{-2} \cdot 5 \cdot 17^2 }[/math]의 경우 [math]\displaystyle{ u_k=(0, 1, -2, 1, 0, 0, 0, 2), v_k=(0, 1, 0, 0, 0, 0, 0) }[/math]이 된다. 순서쌍의 첫 항은 (-1)의 지수를, 둘째 항부터 소인수들의 지수를 나타낸다. [math]\displaystyle{ v_k }[/math]의 성분은 인덱스가 같은 [math]\displaystyle{ u_k }[/math]의 성분이 짝수이면 0, 홀수이면 1로 기록한다.
• 필요시 [math]\displaystyle{ aN (a \in \mathbb{N}) }[/math]의 주변 자연수에 대해서도 위 단계를 시행한다.
• 위 조건을 만족하는 유리수들을 원하는 개수만큼 찾으면, 그 중에서 [math]\displaystyle{ \sum_{k \in A} v_k=0 }[/math]을 만족하는 인덱스의 부분집합 [math]\displaystyle{ A }[/math]를 찾는다. 단, [math]\displaystyle{ v_k }[/math]의 성분 덧셈은 [math]\displaystyle{ \mathbb{Z}/2\mathbb{Z} }[/math] 위에서 이루어지며, 값은 0 또는 1만으로 구분한다.
• [math]\displaystyle{ U=\frac{1}{2}\sum_{k \in A} u_k }[/math]를 셈하고, 이 순서쌍에 해당하는 유리수 [math]\displaystyle{ \frac{y}{x} }[/math]를 도출한다.
• [math]\displaystyle{ \gcd(x \pm y, N) }[/math]을 셈해서 비자명한 약수를 찾으면 알고리즘은 성공한다. 만약 찾지 못한다면, 위에서 다른 인덱수 부분집합 [math]\displaystyle{ A' }[/math]을 찾거나 새 유리수를 추가로 찾는다.

적용 예

[math]\displaystyle{ N=10830961 }[/math]을 유리수 체로 소인수분해를 해보자. 이 예시에서는 소인수 기저를 100 이하의 소수 및 -1로 잡을 것이며, 성분은 총 26개가 된다.

[math]\displaystyle{ \mathcal{B}=\{-1, 2, 3, 5, \cdots 97\} }[/math]

그 다음 [math]\displaystyle{ aN }[/math]에 가깝고, 위 소인수 기저 내의 모든 소수들로 나눠지는 [math]\displaystyle{ w }[/math]를 찾는다. 그리고 [math]\displaystyle{ z=w-aN }[/math]도 마찬가지로 위 소인수들로 전부 나눠지는지 확인한다. 이 조건을 만족하는 두 수에 대해 [math]\displaystyle{ q_k=\frac{w_k}{z_k} }[/math]와 지수를 나타내는 순서쌍 [math]\displaystyle{ u_k, v_k }[/math]를 기록한다.

한 예로 [math]\displaystyle{ w_1=10830000, a_1=1 }[/math]이라 하면 [math]\displaystyle{ z_1=w_1-a_1N=-961 }[/math]이며, 두 수를 각각 소인수분해하면 [math]\displaystyle{ w_1=2^4 \cdot 3 \cdot 5^4 \cdot 19^2, z_1=(-1) \cdot 31^2 }[/math]을 얻는다. 따라서 모든 소인수가 소인수 기저 [math]\displaystyle{ \mathcal{B} }[/math] 안에 들어가므로 이 유리수를 기록한다.

• [math]\displaystyle{ q_1=\frac{w_1}{z_1}=(-1) \cdot 2^4 \cdot 3 \cdot 5^4 \cdot 19^2 \cdot 31^{-2} }[/math]
• [math]\displaystyle{ u_k=(1, 4, 1, 4, 0, 0, 0, 0, 2, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) }[/math]: 첫 성분은 (-1), 그 다음부터는 2부터 97까지의 소수의 지수를 나타낸다.
• [math]\displaystyle{ v_k=(1, 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) }[/math]: 바로 위 벡터의 홀짝 여부를 0과 1로 나타낸 것이다.

이 문제에서는 아래 표와 같이 유리수 26개를 찾게 된다. 벡터 뒷부분의 연속항 0의 개수가 많은 순서로 정렬.

[math]\displaystyle{ k }[/math]	[math]\displaystyle{ w_k, a_k }[/math]	[math]\displaystyle{ z_k }[/math]	[math]\displaystyle{ v_k }[/math]
1	10830000, 1	-961	(1, 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	10832888, 1	1927	(0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
3	10829000, 1	-1961	(1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0)
4	10831338, 1	377	(0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0)
5	10831121, 1	160	(0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0)
6	10831831, 1	870	(0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0)
7	32493664, 3	781	(0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0)
8	10831689, 1	728	(0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0)
9	32492008, 3	-875	(1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0)
10	10829696, 1	-1265	(1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0)
11	10831216, 1	255	(0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0)
12	32491382, 3	-1501	(1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0)
13	21661405, 2	-517	(1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0)
14	10831500, 1	539	(0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0)
15	10831210, 1	249	(0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0)
16	10829757, 1	-1204	(1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0)
17	10829550, 1	-1411	(1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0)
18	21662511, 2	589	(0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0)
19	10830232, 1	-729	(1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0)
20	21660375, 2	-1547	(1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0)
21	10830855, 1	-106	(1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0)
22	32493188, 3	305	(0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0)
23	10830677, 1	-284	(1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0)
24	10829715, 1	-1246	(1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0)
25	32492090, 3	-793	(1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1)
26	32491120, 3	-1763	(1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1)

이제 표의 정보를 토대로 [math]\displaystyle{ \displaystyle \sum_{k \in A} v_k=0 }[/math]을 만족하는 부분집합을 찾으면 [math]\displaystyle{ A= \{1, 4, 5, 6, 7, 12, 19, 20, 21, 23, 25, 26 \} }[/math]이 나온다. 그 다음 이들 인덱스에 해당하는 유리수의 [math]\displaystyle{ u_k }[/math]를 불러오면 아래와 같이 각 유리수를 소수들의 곱 또는 몫으로 나타낼 수 있다.

[math]\displaystyle{ \begin{cases} q_1=(-1) \cdot 2^4 \cdot 3 \cdot 5^4 \cdot 19^2 \cdot 31^{-2}, & q_4=2 \cdot 3^2 \cdot 7 \cdot 13^{-1} \cdot 29^{-1} \cdot 31 \cdot 47 \cdot 59 \\ q_5=2^-5 \cdot 5^{-1} \cdot 7 \cdot 19 \cdot 31 \cdot 37 \cdot 71, & q_6=2^{-1} \cdot 3^{-1} \cdot 5^{-1} \cdot 29^{-1} \cdot 41 \cdot 61^2 \cdot 71 \\ q_7=2^5 \cdot 7^2 \cdot 11^{-1} \cdot 17 \cdot 23 \cdot 53 \cdot 71^{-1}, & q_{12}=(-1) \cdot 2 \cdot 7 \cdot 11 \cdot 19^{-1} \cdot 47 \cdot 67^2 \cdot 79^{-1} \\ q_{19}=(-1) \cdot 2^3 \cdot 3^-6 \cdot 7 \cdot 41 \cdot 53 \cdot 89, & q_{20}=(-1) \cdot 3 \cdot 5^3 \cdot 7^{-1} \cdot 11 \cdot 13^{-1} \cdot 17^{-1} \cdot 59 \cdot 89 \\ q_{21}=(-1) \cdot 2^{-1} \cdot 3 \cdot 5 \cdot 7 \cdot 19 \cdot 53^{-1} \cdot 61 \cdot 89, & q_{23}=(-1) \cdot 2^-2 \cdot 11 \cdot 13 \cdot 23 \cdot 37 \cdot 71^{-1} \cdot 89 \\ q_{25}=(-1) \cdot 2 \cdot 5 \cdot 13^{-1} \cdot 19 \cdot 41 \cdot 43 \cdot 61^{-1} \cdot 97, & q_{26}=(-1) \cdot 2^4 \cdot 5 \cdot 41^{-1} \cdot 43^{-1} \cdot 53 \cdot 79 \cdot 97 \end{cases} }[/math]

주어진 식들을 모두 곱한다. 이때 곱셈은 [math]\displaystyle{ \sum_{k \in A}u_k }[/math]와 같이 지수의 덧셈으로 셈한다. 벡터들을 더한 후, 지수가 양수인 항은 분자로, 음수인 항은 분모로 보낸다.

[math]\displaystyle{ \prod_{k \in A}q_k=\left( \frac{2^5 \cdot 5^4 \cdot 7^3 \cdot 11 \cdot 19^2 \cdot 23 \cdot 37 \cdot 41 \cdot 47 \cdot 53 \cdot 59 \cdot 61 \cdot 67 \cdot 89^2 \cdot 97}{3 \cdot 13 \cdot 29} \right)^2 }[/math]

따라서 제곱 내 분수의 분모를 [math]\displaystyle{ x }[/math], 분자를 [math]\displaystyle{ y }[/math]라 하면 알고리즘의 원리에 의해 [math]\displaystyle{ x^2 \equiv y^2 \pmod N }[/math]이다. 또, [math]\displaystyle{ x \equiv 1131, y \equiv 8169081 \pmod N }[/math]이므로 [math]\displaystyle{ 1131^2 \equiv 8169081^2 \pmod N }[/math]을 알 수 있다.

두 항의 합과 원래 수의 최대공약수를 구하면 [math]\displaystyle{ \gcd(8169081+1131, N)=4177 }[/math]과 같이 약수 하나를 찾고, [math]\displaystyle{ N=2593 \cdot 4177 }[/math]임을 알 수 있다. 물론 [math]\displaystyle{ \gcd(8169081-1131, N)=2593 }[/math]을 이용해도 된다.

※ 참고: 제곱합동식을 유도해냈다고 해서 반드시 알고리즘이 성공하는 것은 아니다. 위의 예시에서 제곱합동식이 만들어질 조건으로 [math]\displaystyle{ A=\{1, 4, 7, 13, 20, 21, 23, 24 \} }[/math]도 있긴 하나, 이 부분집합을 기준으로 계산하면 [math]\displaystyle{ 71^2 \equiv 10830890^2 \pmod N }[/math]과 같이 나온다. 이때 제곱 내 항을 더하면 원래 수와 일치해서, 원하는 약수를 얻어낼 수 없다. 비자명한 약수가 나오려면 [math]\displaystyle{ x \pm y \not \equiv 0 \pmod N }[/math]이어야 한다.

덧붙이기

이 방법이나 이차 체와 같이 제곱합동식을 유도하는 소인수분해법은 합성수가 아주 큰 소수들의 곱으로 이루어져 있을 때 효율적으로 작동한다. 주어진 수에 작은 소인수를 포함하고 있다면 직접 나누기나 렌스트라 타원곡선 소인수분해법 등으로 찾는 것이 더 좋다.

수체 체 방법도 위와 같이 소인수 기저 내 소인수들로 모두 나눠지는 수들을 찾고, 유리수 체의 발전된 형태를 하고 있다. 단, 이쪽은 유리수 대신 어떤 대수적 수를 기반으로 한 확대체 [math]\displaystyle{ \mathbb{Q}(\theta) }[/math] 내에서 다루며 알고리즘 설계 과정은 훨씬 복잡해진다.

유리수 체에서 [math]\displaystyle{ q=\frac{w}{w-aN} }[/math]을 구할 때 [math]\displaystyle{ w, a }[/math]는 서로소여야 한다. 만약 둘 사이에 공약수가 존재하면, [math]\displaystyle{ w=gw', a=ga', z'=w'-a'N }[/math]이라 할 때 [math]\displaystyle{ z=w-aN=g(w'-a'N)=gz' }[/math]이다. 그러면 [math]\displaystyle{ q=\frac{w}{z}, q'=\frac{w'}{z'} }[/math] 두 유리수는 서로 같은 값이 되고, 이는 둘이 독립된 정보가 아님을 뜻한다. 즉 알고리즘을 돌릴 때 [math]\displaystyle{ w, a }[/math]에 대해 조사했다면 [math]\displaystyle{ gz, ga }[/math]는 알아볼 필요가 없어진다.

또, 위 적용 예에서는 제곱합동식을 만들 때 유리수들을 모두 곱했지만, 실제로는 [math]\displaystyle{ \prod_{k \in A}q_k^{e_k} }[/math]와 같이 변형해도 (제곱합동식이 달라질 뿐) 마찬가지로 약수를 찾을 수 있다. 여기서 [math]\displaystyle{ e_k }[/math]는 임의의 홀수 정수이다. 즉 어떤 유리수는 그대로 곱하고, 어떤 유리수는 역수를 곱해도 된다.

같이 보기

• 이차 체
• 수체 체