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

기본편집

이 알고리즘은  이고,    이나  과 같지 않다면,   인 걸 발전시킨 것이다.

 에 대한 소인수 분해 시간은 다음과 같다.
 

알고리즘편집

이 알고리즘은 다음과 같이 진행된다.   인 함수  를 정의한다.

그 다음,  인 소수   (제곱잉여)를 여러 개 모은다.

그 다음,  를 만족하는 자연수  를 구한다.

그 다음, 그것들을 곱해 완전제곱꼴이 되도록 하면 된다.

함께 보기편집