소인수분해

소인수분해(영어: prime factorization, integer factorization)는 1보다 큰 자연수를 소인수(소수인 인수)들만의 곱으로 나타내는 것 또는 합성수를 소수의 곱으로 나타내는 방법을 말한다. 소인수분해를 일의적으로 결정하는 공식은 아직 발견되지 않았다. 현대 암호 처리에서 소인수분해의 어려움은 중요한 기준이 된다.

Thumb — 이 그림은 864의 소인수분해 과정을 그림으로 예시하고 있다. 소인수분해의 결과를 간단하게 쓰면 $2^{5}\times 3^{3}$ 이 된다.

산술의 기본 정리(fundamental theorem of arithmetic)에 의해 모든 양의 정수는 소수들의 곱으로 표현하는 방법이 (곱셈의 교환법칙을 제외하면) 유일하게 존재한다. 그러나 산술의 기본정리는 그 소인수분해를 하는 방법을 알려주지는 않는다. 단지 존재성을 확인해 줄 뿐이다.

아래는 200 이하 합성수의 소인수분해이다.^[1]

4＝2×2(2²)
6＝2×3
8＝2×2×2(2³)
9＝3×3(3²)
10＝2×5
12＝2×2×3(2²x3)
14＝2×7
15＝3×5
16＝2×2×2×2(2⁴)
18＝2×3×3(2x3²)
20＝2×2×5(2²x5)
21＝3×7
22＝2×11
24＝2×2×2×3(2³x3)
25＝5×5(5²)
26＝2×13
27＝3×3×3(3³)
28＝2×2×7(2²x7)
30＝2×3×5
32＝2×2×2×2×2(2⁵)
33＝3×11
34＝2×17
35＝5×7
36＝2×2×3×3(2²x3²)
38＝2×19
39＝3×13
40＝2×2×2×5(2³x5)
42＝2×3×7
44＝2×2×11
45＝3×3×5(3²x5)
46＝2×23
48＝2×2×2×2×3(2⁴x3)
49＝7×7(7²)
50＝2×5×5(2x5²)
51＝3×17
52＝2×2×13(2²x13)
54＝2×3×3×3(2x3³)
55＝5×11
56＝2×2×2×7(2³x7)
57＝3×19
58＝2×29
60＝2×2×3×5(2²x3x5)
62＝2×31
63＝3×3×7(3²x7)
64＝2×2×2×2×2×2(2⁶)
65＝5×13
66＝2×3×11
68＝2×2×17(2²x17)
69＝3×23
70＝2×5×7
72＝2×2×2×3×3(2³x3²)
74＝2×37
75＝3×5×5(3x5²)
76＝2×2×19(2²x19)
77＝7×11
78＝2×3×13
80＝2×2×2×2×5(2⁴x5)
81＝3×3×3×3(3⁴)
82＝2×41
84＝2×2×3×7(2²x3x7)
85＝5×17
86＝2×43
87＝3×29
88＝2×2×2×11(2³x11)
90＝2×3×3×5(2x3²x5)
91＝7×13
92＝2×2×23(2²x23)
93＝3×31
94＝2×47
95＝5×19
96＝2×2×2×2×2×3(2⁵x3)
98＝2×7×7(2x7²)
99＝3×3×11(3²x11)
100＝2×2×5×5(2²x5²)
102＝2×3×17
104＝2×2×2×13(2³x13)
105＝3×5×7
106＝2×53
108＝2×2×3×3×3(2²x3³)
110＝2×5×11
111＝3×37
112＝2×2×2×2×7(2⁴x7)
114＝2×3×19
115＝5×23
116＝2×2×29(2²x29)
117＝3×3×13(3²x13)
118＝2×59
119＝7×17
120＝2×2×2×3×5(2³x3x5)
121＝11×11(11²)
122＝2×61
123＝3×41
124＝2×2×31(2²x31)
125＝5×5×5(5³)
126＝2×3×3×7(2x3²x7)
128＝2×2×2×2×2×2×2(2⁷)
129＝3×43
130＝2×5×13
132＝2×2×3×11(2²x3x11)
133＝7×19
134＝2×67
135＝3×3×3×5(3³x5)
136＝2×2×2×17(2³x17)
138＝2×3×23
140＝2×2×5×7(2²x5x7)
141＝3×47
142＝2×71
143＝11×13
144＝2×2×2×2×3×3(2⁴x3²)
145＝5×29
146＝2×73
147＝3×7×7(3x7²)
148＝2×2×37(2²x37)
150＝2×3×5×5(2x3x5²)
152＝2×2×2×19(2³x19)
153＝3×3×17(3²x17)
154＝2×7×11
155＝5×31
156＝2×2×3×13(2²x3x13)
158＝2×79
159＝3×53
160＝2×2×2×2×2×5(2⁵x5)
161＝7×23
162＝2×3×3×3×3(2x3⁴)
164＝2×2×41(2²x41)
165＝3×5×11
166＝2×83
168＝2×2×2×3×7(2³x3x7)
169＝13×13(13²)
170＝2×5×17
171＝3×3×19(3²x19)
172＝2×2×43(2²x43)
174＝2×3×29
175＝5×5×7(5²x7)
176＝2×2×2×2×11(2⁴x11)
177＝3×59
178＝2×89
180＝2×2×3×3×5(2²x3²)
182＝2×7×13
183＝3×61
184＝2×2×2×23(2³x23)
185＝5×37
186＝2×3×31
187＝11×17
188＝2×2×47(2²x47)
189＝3×3×3×7(3³x7)
190＝2×5×19
192＝2×2×2×2×2×2×3(2⁶x3)
194＝2×97
195＝3×5×13
196＝2×2×7×7(2²x7²)
198＝2×3×3×11(2x3²x11)
200＝2×2×2×5×5(2³x5²)

현대의 전자기 기반 컴퓨터상에서 소인수분해에 대한 다항식 시간 알고리즘은 알려져 있지 않다. 단, 이론적인 양자컴퓨터에서의 다항식 시간 소인수분해 알고리즘 (쇼어의 알고리즘)은 존재한다. 하지만 아직까지 어떤 합성수를 다항 시간 안에 소인수분해하기는 어려운 문제이며, 예를 들어 193자리 수(RSA-640)는 5개월간 30개의 2.2 GHz 옵테론 CPU를 동원하여 소인수분해 되었다. 소인수분해의 난해함은 RSA와 같은 현대 암호의 핵심적 부분이 된다.

고전적 알고리즘

고전적인 소인수분해 알고리즘은 대부분 페르마 소정리를 확장한 것을 이용한다. 그중 자주 사용되는 알고리즘은 아래와 같다.

윌리엄의 p+1 알고리즘
폴라드의 p-1 알고리즘
폴라드 로 알고리즘
페르마의 알고리즘

알고리즘의 발전

암호학의 발달과 함께 소인수분해 방법도 발전해 왔으며 그중 가장 효율적인 알고리즘들을 간추리면 아래와 같다.

렌스트라의 타원곡선 알고리즘 (Elliptic Curve Method, ECM): 타원곡선의 성질을 이용하여 어떤 수를 소인수분해하는 알고리즘으로, 가장 작은 소인수의 크기에 따라서 실행 시간이 결정된다. 이 알고리즘의 실행 시간은 $O\left(\exp \left({\sqrt {2\ln(p\ln(\ln(p))}}\right)\right)$ 로 이전의 잉여체의 성질을 이용한 알고리즘에 비해 매우 우수하다.
수체 체(General Number Field Sieve, GNFS) 알고리즘은 이차 체 알고리즘을 발전시킨 것으로 일반 컴퓨터로 실행시킬 수 있는 알고리즘 중에서는 가장 빠른 알고리즘이다. b가 합성수의 비트수일 때, 이 알고리즘은 $O\left(\exp \left(\left({\begin{matrix}{\frac {64}{9}}\end{matrix}}b\right)^{1 \over 3}(\log b)^{2 \over 3}\right)\right)$ 의 시간복잡도를 가진다.
특수 수체 체 (Special Number Field Sieve, SNFS) 알고리즘은 r, e, s가 자연수일 때, r^e ± s 꼴인 자연수에 대해서 작동하는 알고리즘이다. 여기서 r, s의 값이 커지면 속도가 급속도로 느려지기 때문에 r, s가 작은 자연수에 대해서만 잘 작동하며 사용할 수 있다.
다중 다항식 이차체 (Multiple Polynomial Quadratic Sieve, MPQS) 알고리즘은 이차 체 알고리즘을 확장시킨 알고리즘으로, 한 개의 함수를 이용하는 이차 체와는 달리 여러 개의 함수를 이용하는 알고리즘이다.
이차 체 (Quadratic Sieve, QS) 알고리즘은 100자리 이하의 자연수를 소인수분해할 때 적합하며, 보통 어떤 합성수의 소인수들의 크기가 비슷할 때 잘 작동한다.