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

1 바이트 제거됨 ,  8년 전
편집 요약 없음
 
소인수분해를 일의적으로 결정하는 방법은 아직 발견되지 않았다. 현대 암호 처리에서 소인수분해의 어려움은 중요한 기준이 된다.
 
현대의 전자기 기반 컴퓨터상에서 소인수 분해에 대한 [[다항식 시간 알고리즘]]은 알려져 있지 않다. 단, 이론적인 [[양자컴퓨터]]에서의 다항식 시간 소인수분해 알고리즘은 존재한다. 하지만 아직까지 빠르게 소인수분해하기는 어려운 문제이며, 예를들어 193자리 수(RSA-640)가 5개월간 30개의 2.2 GHz 옵테론 CPU를 동원하여 소인수분해 되었다. 소인수 분해의 난해함은 [[RSA 암호|RSA]]와 같은 암호 알고리즘의 핵심적 부분이 된다.
 
== 소인수 분해 ==
 
== 소인수분해 알고리즘 ==
현대의 전자기 기반 컴퓨터상에서 소인수 분해에 대한 [[다항식 시간 알고리즘]]은 알려져 있지 않다. 단, 이론적인 [[양자컴퓨터]]에서의 다항식 시간 소인수분해 알고리즘은 존재한다. 하지만 아직까지 빠르게 소인수분해하기는 어려운 문제이며, 예를들어 193자리 수(RSA-640)가 5개월간 30개의 2.2 GHz 옵테론 CPU를 동원하여 소인수분해 되었다. 소인수 분해의 난해함은 [[RSA 암호|RSA]]와 같은 암호 알고리즘의 핵심적 부분이 된다.
 
=== 고전적 알고리즘 ===

편집

67