"소인수분해"의 두 판 사이의 차이

11 바이트 추가됨 ,  5년 전
잔글
편집 요약 없음
잔글
'''소인수 분해'''(integer factorization, {{문화어|씨인수분해}})는 [[합성수]]를 [[소수 (수론)|소수]]의 곱으로 나타내는 방법을 말한다.
 
소인수분해를소인수 분해를 일의적으로 결정하는 방법은 아직 발견되지 않았다. 현대 암호 처리에서 소인수분해의소인수 분해의 어려움은 중요한 기준이 된다.
 
== 소인수 분해 ==
[[파일:PrimeDecompositionExample.png|right|thumb|150px|이 그림은 864의 소인수분해소인수 분해 과정을 그림으로 예시하고 있다. 소인수분해의소인수 분해의 결과를 간단하게 쓰면 <math>2^5 \times 3^3</math>이 된다.]]
[[산술의 기본 정리]](fundamental theorem of arithmetic)에 의해 모든 양의 정수는 소수들의 곱으로 표현하는 방법이 (곱의 순서를 바꾸는 것을 제외하면) 유일하게 존재한다. 그러나 산술의 기본정리는 그 소인수 분해를 하는 방법을 알려주지는 않는다. 단지 존재성만 확인해 줄 뿐이다.
 
 
== 소인수분해소인수 분해 알고리즘 ==
현대의 전자기 기반 컴퓨터상에서 소인수 분해에 대한 [[다항식 시간 알고리즘]]은 알려져 있지 않다. 단, 이론적인 [[양자컴퓨터]]에서의 [[쇼어 알고리즘|다항식 시간 소인수분해소인수 분해 알고리즘]]은 존재한다. 하지만 아직까지 빠르게 소인수분해하기는소인수 분해하기는 어려운 문제이며, 예를들어 193자리 수(RSA-640)가 5개월간 30개의 2.2 GHz 옵테론 CPU를 동원하여 소인수분해소인수 분해 되었다. 소인수 분해의 난해함은 [[RSA 암호|RSA]]와 같은 암호 알고리즘의 핵심적 부분이 된다.
 
=== 고전적 알고리즘 ===
고전적인 소인수분해소인수 분해 알고리즘은 대부분 [[페르마의 소정리]]의 성질을 이용한다.
그 중 자주 사용되는 알고리즘은 아래와 같다.
* [[윌리엄의 p+1 방법]]
=== 알고리즘의 발전 ===
[[암호학]]의 발달과 함께 소인수분해소인수 분해 방법도 발전해 왔으며 그 중 유의미한 것을 간추리면 아래와 같다.
* [[타원 곡선]]에 의한 알고리즘(ECM)은 <math>O(\exp(\sqrt(2 \ln(p \ln( \ln(p)))))</math>의 점근 속도로 이전의 [[잉여체]]의 성질을 이용한 알고리즘에 비해 매우 우수하다.
* [[수범위체]](number field sieve) 알고리즘은 b가 합성수의 bit수일 때, <math>O\left(\exp\left(\left(\begin{matrix}\frac{64}{9}\end{matrix} b\right)^{1\over3} (\log b)^{2\over3}\right)\right)</math>의 속도이며 범용 소인수분해 알고리즘에서 가장 우수하다.
== 함께읽기 ==
* [[약수]]
* [[인수분해인수 분해]]
* [[정수론의 기본 정리]] (fundamental theorem of arithmetic)
* [[RSA 암호]]