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

460 바이트 추가됨 ,  8년 전
용어(인수분해->소인수분해) 및 내용 수정
잔글 (r2.7.1) (로봇이 바꿈: ar:تحليل عدد صحيح)
(용어(인수분해->소인수분해) 및 내용 수정)
'''소인수 분해'''(integer factorization, {{llang|ko-KP|씨인수분해}})는 [[합성수]]를 [[소수 (수론)|소수]]의 곱으로 나타내는 방법을 말한다.
 
매우현대의 전자기 합성수에기반 대해컴퓨터상에서 아직까지소인수 분해에 대한 효율적인다항식 인수분해시간 [[알고리즘]] 알려져 있지 않다. 단, 이론적인 양자컴퓨터에서의 다항식 시간 소인수분해 알고리즘은 존재한다. 하지만 아직까지 빠르게 소인수분해하기는 어려운 문제이며, 예를들어 193자리 수(RSA-640)가 5개월간 30개의 2.2 GHz 옵테론 CPU를 동원하여 소인수분해 되었다. 이러한 소인수 분해의 난해함은 [[RSA 암호|RSA]]와 같은 암호 알고리즘의 핵심적 부분이 된다. 컴퓨터 과학과 수학의 많은 분야에서 소인수 분해는 파생 영역을 만들었고, [[타원 곡선론]], [[대수적 정수론]], [[양자 컴퓨터]] 등등의 분야를 낳았다.
 
== 소인수분해 알고리즘 ==
어떤 자리수를 가진 모든 합성수가 인수분해하기 어려운 것은 아니다. 실제로 간단한 소수의 경우, 초등적인 이론을 이용한 손쉽게 수행가능한 소인수 판정법이 있다. 가장 어려운 경우가 두 개의 큰 소수의 곱으로 만들어진 합성수인데, 이 경우 가장 빠른 소인수분해 알고리즘을 이용하더라도 상당한 시간이 걸리게 된다.
 
=== 고전적 알고리즘 ===
고전적인 소인수분해 알고리즘은 대부분 [[페르마의 소정리]]의 성질을 이용한다.
그 중 자주 사용되는 알고리즘은 아래와 같다.
* [[윌리엄의 p+1 방법]]
* [[pollard p-1 방법]]
=== 알고리즘의 발전 ===
암호학의 발달과 함께 소인수분해 방법도 발전해 왔으며 그 중 유의미한 것을 간추리면 아래와 같다.
* [[타원 곡선]]에 의한 알고리즘(ECM)은 <math>O(\exp(\sqrt(2 \ln(p \ln( \ln(p)))))</math>의 점근 속도로 이전의 잉여체의 성질을 이용한 알고리즘에 비해 매우 우수하다.
* [[수범위체]](number field sieve) 알고리즘은 범용 소인수분해 알고리즘에서 가장 우수하다.
* [[다중 다항식 이차체]](multiple polynomial quadratic sieve : mpqs) 알고리즘
 
== 소인수 분해 ==

편집

67