이차 체

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

이차 체(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에 대한 소인수 분해 시간은 다음과 같다: O\left(e^\sqrt{\log n \log\log n}\right)=L_n\left[1/2,1\right]

알고리즘[편집]

이 알고리즘은 다음과 같이 진행된다. y(x)=\left(\left\lfloor\sqrt{n}\right\rfloor+x\right)^2-n 인 함수 y(x)를 정의한다. 그 다음, x^2 \ \equiv\ p \pmod{n}인 소수 p(제곱잉여)를 여러 개 모은다. 그 다음, x^2 \ \equiv\ n \pmod{p}를 만족하는 자연수 x를 구한다. 그 다음, 그것들을 곱해 완전제곱꼴이 되도록 하면 된다.