소인수분해

위키백과, 우리 모두의 백과사전.
(소인수 분해에서 넘어옴)
둘러보기로 가기 검색하러 가기

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

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

소인수분해[편집]

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

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

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

  • 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

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

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

고전적 알고리즘[편집]

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

알고리즘의 발전[편집]

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

  • 타원 곡선에 의한 알고리즘(ECM)은 점근 속도로 이전의 잉여체의 성질을 이용한 알고리즘에 비해 매우 우수하다.
  • 수범위체(number field sieve) 알고리즘은 b가 합성수의 bit수일 때, 의 속도이며 범용 소인수분해 알고리즘에서 가장 우수하다.
  • 다중 다항식 이차체(multiple polynomial quadratic sieve : mpqs) 알고리즘
  • 이차 체

같이 보기[편집]

각주[편집]