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

 

== 소인수분해 ==

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

 

* [[윌리엄의 p+1 방법]]

* [[pollard p-1 방법]]

=== 알고리즘의 발전 ===

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