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

66 바이트 제거됨 ,  2년 전
위키백과가 위키백과 스스로를 참조할 수 없습니다.
(integer factorization -> prime factorization. 인수분해와 "소"인수분해를 구분합니다.)
(위키백과가 위키백과 스스로를 참조할 수 없습니다.)
=== 알고리즘의 발전 ===
[[암호학]]의 발달과 함께 소인수 분해 방법도 발전해 왔으며 그 중 유의미한 것을 간추리면 아래와 같다.
* [[타원 곡선]]에 의한 알고리즘(ECM)은 <math>O\left(\exp\left(\sqrt{2 \ln(p \ln( \ln(p))}\right)\right)</math>의 [[점근 표기법|점근 속도<ref>https://ko.wikipedia.org/wiki/%EC%A0%90%EA%B7%BC_%ED%91%9C%EA%B8%B0%EB%B2%95</ref>]]로 이전의 [[잉여체]]의 성질을 이용한 알고리즘에 비해 매우 우수하다.
* [[w:General number field sieve|수범위체]](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>의 속도이며 범용 소인수분해 알고리즘에서 가장 우수하다.
* [[다중 다항식 이차체]](multiple polynomial quadratic sieve : mpqs) 알고리즘