소인수분해: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
위키백과가 위키백과 스스로를 참조할 수 없습니다. |
KEEPONandON (토론 | 기여) 소인수분해는 붙여 쓰는것이 맞습니다. |
||
1번째 줄:
'''
==
[[파일:PrimeDecompositionExample.png|right|thumb|150px|이 그림은 864의
[[산술의 기본 정리]](fundamental theorem of arithmetic)에 의해 모든 양의 정수는 소수들의 곱으로 표현하는 방법이 (곱의 순서를 바꾸는 것을 제외하면) 유일하게 존재한다. 그러나 산술의 기본정리는 그
아래는 [[20]] 이하 [[합성수]]의 소인수분해이다.
20번째 줄:
* 20=2×2×5
==
현대의 전자기 기반 컴퓨터상에서
=== 고전적 알고리즘 ===
고전적인
그 중 자주 사용되는 알고리즘은 아래와 같다.
* [[윌리엄의 p+1 방법]]
30번째 줄:
=== 알고리즘의 발전 ===
[[암호학]]의 발달과 함께
* [[타원 곡선]]에 의한 알고리즘(ECM)은 <math>O\left(\exp\left(\sqrt{2 \ln(p \ln( \ln(p))}\right)\right)</math>의 [[점근 표기법|점근 속도]]로 이전의 [[잉여체]]의 성질을 이용한 알고리즘에 비해 매우 우수하다.
* [[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>의 속도이며 범용 소인수분해 알고리즘에서 가장 우수하다.
|