소인수분해 문서 원본 보기

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

== 개요 ==
[[파일:PrimeDecompositionExample.png|오른쪽|섬네일|150px|이 그림은 864의 소인수분해 과정을 그림으로 예시하고 있다. 소인수분해의 결과를 간단하게 쓰면 <math>2^5 \times 3^3</math>이 된다.]]
[[산술의 기본 정리]](fundamental theorem of arithmetic)에 의해 모든 양의 정수는 소수들의 곱으로 표현하는 방법이 (곱셈의 [[교환법칙]]을 제외하면) 유일하게 존재한다. 그러나 산술의 기본정리는 그 소인수분해를 하는 방법을 알려주지는 않는다. 단지 존재성을 확인해 줄 뿐이다.

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

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

=== 고전적 알고리즘 ===
고전적인 소인수분해 알고리즘은 대부분 [[페르마 소정리]]를 확장한 것을 이용한다.
그중 자주 사용되는 알고리즘은 아래와 같다.
* [[윌리엄의 p+1 방법|윌리엄의 p+1 알고리즘]]
* [[폴라드의 P-1 알고리즘|폴라드의 p-1 알고리즘]]
* 폴라드 로 알고리즘
* 페르마의 알고리즘

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

== 같이 보기 ==
{{위키공용분류}}
{{포털|수학}}
* [[약수]]
* [[합성수]]
* [[인수 분해]]
** [[곱셈 공식]]
* [[정수론의 기본 정리]] (fundamental theorem of arithmetic)
* [[RSA 암호]]
* [[시간 복잡도]]
* [[점근 표기법]]

== 각주 ==
{{각주}}

{{소수}}
{{수론 알고리즘}}
{{공개 키 암호 방식}}
{{전거 통제}}

[[분류:소수]]
[[분류:소인수 분해 알고리즘]]
[[분류:컴퓨터 과학의 미해결 문제]]
[[분류:인수분해]]