이차 체: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Number0316 (토론 | 기여) 잔글편집 요약 없음 |
Number0316 (토론 | 기여) 활용 문단을 추가했습니다. |
||
1번째 줄:
{{다른 뜻|이차 수체}}
'''이차 체'''(Quadratic sieve, QS)는 어떤 큰 자연수 N을 소인수분해하기 위해 사용되는 [[소인수 분해]] 알고리즘으로, 양자컴퓨터가 상용화되었을 때 기준으로는 현재까지 발견된 알고리즘 중에서 3번째([[쇼어 알고리즘]], [[수체
== 기본 ==
이 알고리즘은 <math>x^2=y^2(mod \ n)</math>이고, <math>(x+y,n)</math>와 <math>(x-y,n)</math>이 <math>1</math>이나 <math>n</math>과 같지 않다면, <math>n=(x+y,n)*(x-y,n)</math>
10번째 줄:
이 알고리즘은 다음과 같이 진행된다.
<math>y(x)=\left(\left\lfloor\sqrt{n}\right\rfloor+x\right)^2-n</math>
인 함수 <math>y(x)</math>를 정의한다. 이때, 이 함수는 달라질 수도 있다.
그 다음, <math>x^2 \ \equiv\ p \pmod{n}</math>인 소수 ''<math>p</math>'' ([[제곱잉여]])를 <math>\lceil\ln(\lceil\sqrt{x}\rceil^2-x)\rceil</math>개 모은다.
184번째 줄:
7. 이때, x<sup>2</sup>≡y<sup>2</sup> (mod N)이라는 관계식이 성립하게 된다. 따라서 N의 약수는 [[최대공약수|gcd]](x-y, N), gcd(x+y, N)이 되며, N=gcd(x-y, N) ⋅ gcd(x+y, N)이 된다. 예시의 경우, N=667=gcd(26-3, 667) ⋅ gcd(26+3, 667)=23 ⋅ 29가 된다.
실제로 이렇게 작은 수를 소인수분해할 때에는 이차 체 알고리즘은 효율적이지 않다. 보통 이차 체는 50자리가 넘고 약수가 2개 정도 있는 수를 소인수분해할 때 쓰인다.
== 활용 ==
이차 체 알고리즘은 발견 당시에는 다른 알고리즘들에 비해서 매우 빠른 알고리즘이었기 때문에 큰 수를 소인수분해할 때 많이 쓰였으며, 요즘에는 렌스트라의 타원곡선 알고리즘 (ECM, Elliptic Curve Method)을 특정 크기 미만의 약수들을 모두 구하게 하여 약수가 2개밖에 없는 것이 확인되거나 2개가 될 때까지 나눈 후 이 알고리즘을 적용한다. 보통 두 약수의 크기가 비슷할 때 잘 작동하며, 100자리 이상의 정수를 소인수분해할 때에는 [[수체 체]] (GNFS, General Number Field Sieve)알고리즘을 더 많이 사용한다. 또한 RSA-129를 소인수분해할 때 이 알고리즘을 조금 더 확장한 다중 함수 이차 체 (MPQS, Multiple Polynomial Quadratic Sieve)를 사용하기도 했다.
== 같이 보기 ==
| |||