소인수분해(영어: prime factorization, integer factorization)는 합성수를 소수의 곱으로 나타내는 방법을 말한다.

소인수분해를 일의적으로 결정하는 방법은 아직 발견되지 않았다. 현대 암호 처리에서 소인수분해의 어려움은 중요한 기준이 된다.

소인수분해

이 그림은 864의 소인수분해 과정을 그림으로 예시하고 있다. 소인수분해의 결과를 간단하게 쓰면 25×33displaystyle 2^5times 3^3이 된다.

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

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

• 4＝2×2


• 6＝2×3


• 8＝2×2×2


• 9＝3×3


• 10＝2×5


• 12＝2×2×3


• 14＝2×7


• 15＝3×5


• 16＝2×2×2×2


• 18＝2×3×3


• 20＝2×2×5


• 21＝3×7


• 22＝2×11


• 24＝2×2×2×3


• 25＝5×5


• 26＝2×13


• 27＝3×3×3


• 28＝2×2×7


• 30＝2×3×5


• 32＝2×2×2×2×2


• 33＝3×11


• 34＝2×17


• 35＝5×7


• 36＝2×2×3×3


• 38＝2×19


• 39＝3×13


• 40＝2×2×2×5


• 42＝2×3×7


• 44＝2×2×11


• 45＝3×3×5


• 46＝2×23


• 48＝2×2×2×2×3


• 49＝7×7


• 50＝2×5×5


• 51＝3×17


• 52＝2×2×13


• 54＝2×3×3×3


• 55＝5×11


• 56＝2×2×2×7


• 57＝3×19


• 58＝2×29


• 60＝2×2×3×5


• 62＝2×31


• 63＝3×3×7


• 64＝2×2×2×2×2×2


• 65＝5×13


• 66＝2×3×11


• 68＝2×2×17


• 69＝3×23


• 70＝2×5×7


• 72＝2×2×2×3×3


• 74＝2×37


• 75＝3×5×5


• 76＝2×2×19


• 77＝7×11


• 78＝2×3×13


• 80＝2×2×2×2×5


• 81＝3×3×3×3


• 82＝2×41


• 84＝2×2×3×7


• 85＝5×17


• 86＝2×43


• 87＝3×29


• 88＝2×2×2×11


• 90＝2×3×3×5


• 91＝7×13


• 92＝2×2×23


• 93＝3×31


• 94＝2×47


• 95＝5×19


• 96＝2×2×2×2×2×3


• 98＝2×7×7


• 99＝3×3×11


• 100＝2×2×5×5


• 102＝2×3×17


• 104＝2×2×2×13


• 105＝3×5×7


• 106＝2×53


• 108＝2×2×3×3×3


• 110＝2×5×11


• 111＝3×37


• 112＝2×2×2×2×7


• 114＝2×3×19


• 115＝5×23


• 116＝2×2×29


• 117＝3×3×13


• 118＝2×59


• 119＝7×17


• 120＝2×2×2×3×5


• 121＝11×11


• 122＝2×61


• 123＝3×41


• 124＝2×2×31


• 125＝5×5×5


• 126＝2×3×3×7


• 128＝2×2×2×2×2×2×2


• 129＝3×43


• 130＝2×5×13


• 132＝2×2×3×11


• 133＝7×19


• 134＝2×67


• 135＝3×3×3×5


• 136＝2×2×2×17


• 138＝2×3×23


• 140＝2×2×5×7


• 141＝3×47


• 142＝2×71


• 143＝11×13


• 144＝2×2×2×2×3×3


• 145＝5×29


• 146＝2×73


• 147＝3×7×7


• 148＝2×2×37


• 150＝2×3×5×5


• 152＝2×2×2×19


• 153＝3×3×17


• 154＝2×7×11


• 155＝5×31


• 156＝2×2×3×13


• 158＝2×79


• 159＝3×53


• 160＝2×2×2×2×2×5


• 161＝7×23


• 162＝2×3×3×3×3


• 164＝2×2×41


• 165＝3×5×11


• 166＝2×83


• 168＝2×2×2×3×7


• 169＝13×13


• 170＝2×5×17


• 171＝3×3×19


• 172＝2×2×43


• 174＝2×3×29


• 175＝5×5×7


• 176＝2×2×2×2×11


• 177＝3×59


• 178＝2×89


• 180＝2×2×3×3×5


• 182＝2×7×13


• 183＝3×61


• 184＝2×2×2×23


• 185＝5×37


• 186＝2×3×31


• 187＝11×17


• 188＝2×2×47


• 189＝3×3×3×7


• 190＝2×5×19


• 192＝2×2×2×2×2×2×3


• 194＝2×97


• 195＝3×5×13


• 196＝2×2×7×7


• 198＝2×3×3×11

소인수분해 알고리즘

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

고전적 알고리즘

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

• 윌리엄의 p+1 방법


• pollard p-1 방법

알고리즘의 발전

암호학의 발달과 함께 소인수분해 방법도 발전해 왔으며 그중 유의미한 것을 간추리면 아래와 같다.

• 
  타원 곡선에 의한 알고리즘(ECM)은 O(exp⁡(2ln⁡(pln⁡(ln⁡(p))))displaystyle Oleft(exp left(sqrt 2ln(pln(ln(p))right)right)의 점근 속도로 이전의 잉여체의 성질을 이용한 알고리즘에 비해 매우 우수하다.


• 
  수범위체(number field sieve) 알고리즘은 b가 합성수의 bit수일 때, O(exp⁡((649b)13(log⁡b)23))displaystyle Oleft(exp left(left(beginmatrixfrac 649endmatrixbright)^1 over 3(log b)^2 over 3right)right)의 속도이며 범용 소인수분해 알고리즘에서 가장 우수하다.


• 
  다중 다항식 이차체(multiple polynomial quadratic sieve : mpqs) 알고리즘


• 이차 체

같이 보기

• 약수


• 인수 분해


• 
  정수론의 기본 정리 (fundamental theorem of arithmetic)


• RSA 암호


• 시간 복잡도


• 점근 표기법

각주

이 글은 수론에 관한 토막글입니다. 여러분의 지식으로 알차게 문서를 완성해 갑시다.