소인수 분해

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

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

소인수 분해[편집]

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

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


소인수 분해 알고리즘[편집]

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

고전적 알고리즘[편집]

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

알고리즘의 발전[편집]

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

  • 타원 곡선에 의한 알고리즘(ECM)은 O(\exp(\sqrt(2 \ln(p \ln( \ln(p)))))의 점근 속도로 이전의 잉여체의 성질을 이용한 알고리즘에 비해 매우 우수하다.
  • 수범위체(number field sieve) 알고리즘은 b가 합성수의 bit수일 때, O\left(\exp\left(\left(\begin{matrix}\frac{64}{9}\end{matrix} b\right)^{1\over3} (\log b)^{2\over3}\right)\right)의 속도이며 범용 소인수분해 알고리즘에서 가장 우수하다.
  • 다중 다항식 이차체(multiple polynomial quadratic sieve : mpqs) 알고리즘
  • 이차 체

주석[편집]


함께읽기[편집]