이차 체

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

이차 체(Quadratic sieve)는 소인수 분해 알고리즘으로 3번째(쇼어 알고리즘, 수 체)로 빠른 알고리즘 이며, 수 체보다 훨씬 간단하다.

기본[편집]

이 알고리즘은 x^2=y^2(mod n)이고, (x+y,n)와 (x-y,n)이 1이나 n과 같지 않다면, n=(x+y,n)*(x-y,n) 인 걸 발전시킨 것이다. n에 대한 소인수 분해 시간은 다음과 같다.

알고리즘[편집]

이 알고리즘은 다음과 같이 진행된다. 인 함수 를 정의한다. 그 다음, 인 소수 p(제곱잉여)를 여러 개 모은다. 그 다음, 를 만족하는 자연수 x를 구한다. 그 다음, 그것들을 곱해 완전제곱꼴이 되도록 하면 된다.