소인수분해

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

매우 큰 합성수에 대해 아직까지 효율적인 인수분해 알고리즘이 알려져 있지 않다. 193자리 수(RSA-640)가 5개월간 30개의 2.2 GHz 옵테론 CPU를 동원하여 소인수분해 되었다. 이러한 소인수 분해의 난해함은 RSA와 같은 암호 알고리즘의 핵심적 부분이 된다. 컴퓨터 과학과 수학의 많은 분야에서 소인수 분해는 파생 영역을 만들었고, 타원 곡선론, 대수적 정수론, 양자 컴퓨터 등등의 분야를 낳았다.

어떤 자리수를 가진 모든 합성수가 인수분해하기 어려운 것은 아니다. 실제로 간단한 소수의 경우, 초등적인 이론을 이용한 손쉽게 수행가능한 소인수 판정법이 있다. 가장 어려운 경우가 두 개의 큰 소수의 곱으로 만들어진 합성수인데, 이 경우 가장 빠른 소인수분해 알고리즘을 이용하더라도 상당한 시간이 걸리게 된다.

소인수 분해

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

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

함께읽기

• 약수
• 인수분해
• 정수론의 기본 정리 (fundamental theorem of arithmetic)
• RSA 암호