이차 체 문서 원본 보기

{{위키데이터 속성 추적}}
{{다른 뜻|이차 수체}}
'''이차 체'''(Quadratic sieve, QS)는 어떤 큰 자연수 N을 소인수분해하기 위해 사용되는 [[소인수 분해]] 알고리즘으로, 양자컴퓨터가 상용화되었을 때 기준으로는 현재까지 발견된 알고리즘 중에서 3번째([[쇼어 알고리즘]], [[수체 체]] ([[:en:General_number_field_sieve|General number field sieve]]))로 빠른 알고리즘이며 (양자컴퓨터를 제외하면 2번째), [[w:General number field sieve|수체 체]]의 기본이 되어 수체 체보다 더 간단한 알고리즘이다.
== 기본 ==
이 알고리즘은 <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>
인 것을 개선한 것이다.
:<math>n</math>에 대한 [[소인수 분해]] 시간은 다음과 같다.
:<math>O\left(e^\sqrt{\log n \log\log n}\right)=L_n\left[{1 \over2},1\right]</math>

== 알고리즘 ==
이 알고리즘은 다음과 같이 진행된다.
<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>개 모은다.

그 다음, <math>x^2 \ \equiv\ n \pmod{p}</math>를 만족하는 자연수 ''<math>x</math>''를 구한다.

그 다음, 행렬이나 방정식을 이용하여 완전제곱수가 되게 하는 곱을 구한다. 그리고 그것들을 곱해 완전제곱꼴이 되도록 한 후 [[최대공약수|gcd]](x+y, n), [[최대공약수|gcd]](x-y, n)을 구하면 된다.

== 예시 ==
1. N=667을 소인수분해하고 싶다고 하자. 그러면, 우리는 p를 <math>\lceil\ln(\lceil \sqrt{667} \rceil^{2}-667)\rceil=3</math>개 구해야 한다. 여기서 p는 <math>\left ( \frac{N}{p} \right )=1</math>라는 조건을 만족하는 소수이다. 여기서 식의 좌변의 기호는 [[야코비 기호]]이며, 이 경우에 p의 값은 2, 3, 7이 된다. 여기서 N이 홀수이면 p에는 2가 반드시 포함된다.



2. 이차 체의 범위를 정한다. 667처럼 작은 수를 소인수분해하는 경우에는 위-아래로 8개의 수 정도만 고려해도 충분하다. 즉, 여기서 n의 값의 범위는 밑의 표에 나오는 17부터 33까지이며, 이 범위는 <math>\lfloor \sqrt{667} \rfloor \pm8=17, 33</math>에 의해서 나온 것이다. 참고로 이 범위는 수의 크기가 커짐에 따라 많이 달라지게 된다.


3. 2번에서 구한 범위 내에 있는 정수에 대해 (정수의 값)<sup>2</sup>-N의 값이 p의 값들로만 완전히 소인수분해되는지, 즉 (정수의 값)<sup>2</sup>-N이 p-smooth인지 확인한다. 이 부분에서 p의 값들로만 완전히 소인수분해되는 정수들을 모은다. 실제로는 이 부분에서 (정수)<sup>2</sup>-N을 완전히 소인수분해할 필요는 없고 2, 3, 7로 계속 나누어 보아 더 이상 나누어떨어지지 않을 때까지 나누면 된다. 만약 계속 나눠 1이 된 경우 이 수는 p의 값들로 완전히 소인수분해되는 것이고, 더 이상 나눌 수 없는데 이 값이 1보다 클 경우 이 수는 p의 값으로 완전히 소인수분해되지 않는 것이다. 이 경우, 이차 체는 다음과 같이 진행된다.
{| class="wikitable"
|+이차 체
!x<sub>r</sub>
!n
!n<sup>2</sup>-N (n<sup>2</sup>-667)
!2로 나누어지는 횟수
!3으로 나누어지는 횟수
!7로 나누어지는 횟수
!2, 3, 7로 완전히 소인수분해가 되는가?
|-
|x<sub>1</sub>
|17
| -378
|1
|3
|1
|네
|-
|x<sub>2</sub>
|18
| -343
|0
|0
|3
|네
|-
|x<sub>3</sub>
|19
| -306
|1
|2
|0
|아니오
|-
|x<sub>4</sub>
|20
| -267
|0
|1
|0
|아니오
|-
|x<sub>5</sub>
|21
| -226
|1
|0
|0
|아니오
|-
|x<sub>6</sub>
|22
| -183
|0
|1
|0
|아니오
|-
|x<sub>7</sub>
|23
| -138
|1
|1
|0
|아니오
|-
|x<sub>8</sub>
|24
| -91
|0 
|0
|1
|아니오
|-
|x<sub>9</sub>
|25
| -42
|1
|1
|1
|네
|-
|x<sub>10</sub>
|26
|9
|0
|2
|0
|네
|-
|x<sub>11</sub>
|27
|62
|1
|0
|0
|아니오
|-
|x<sub>12</sub>
|28
|117
|0
|2
|0
|아니오
|-
|x<sub>13</sub>
|29
|174
|1
|1
|0
|아니오
|-
|x<sub>14</sub>
|30
|233
|0
|0
|0
|아니오
|-
|x<sub>15</sub>
|31
|294
|1
|1
|2
|네
|-
|x<sub>16</sub>
|32
|357
|0
|1
|1
|아니오
|-
|x<sub>17</sub>
|33
|422
|1
|0
|0
|아니오
|}
4. 2, 3, 7로 완전히 소인수분해되는 수의 n값에 대해, p로 나누어지는 횟수들을 모은 행렬 (위에 나와 있는 부분 중 '네'라고 있는 부분만 뽑아 모은 행렬)을 만들고 그  행렬의 각 성분에 대하여 2로 나눈 나머지로 바꾼다. 여기서 2로 나눈 나머지를 구한 행렬을 [[전치행렬|전치]]한 행렬을 구한다. 이 예시의 경우에는, 행렬은<math>\begin{pmatrix} 1 & 3 & 1 \\ 0 & 0 & 3 \\ 1 & 1 & 1 \\ 0 & 2 & 0 \\ 1 & 1 & 2 \end{pmatrix}</math>가 되며,

17은 (1, 3, 1)에, 18은 (0, 0, 3)에, ... 이런 식으로 대응한다. 이 행렬의 각 성분을 2로 나눈 나머지를 모은 행렬을 구하면 <math>\begin{pmatrix} 1 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \\ 0 & 0 & 0 \\ 1 & 1 & 0 \end{pmatrix}</math>가 되고, 이 행렬을 전치하면 <math>\begin{pmatrix} 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 \end{pmatrix}</math>이 된다.


5. 전치한 행렬과 곱하고 각 성분을 2로 나눈 나머지로 바꿨을 때 열이 하나밖에 없는 제로벡터가 나오도록 하는 행렬 '''v<sup>T</sup>'''를 구하고, 이 행렬 '''v<sup>T</sup>'''를 전치하여 행이 하나인 행렬 '''v'''를 구한다. 이 예시의 경우, <math>\begin{pmatrix} 1 & 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 \end{pmatrix}\cdot v^{T}=\begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} \pmod 2</math>가 되고, 이때 행렬 <math>v^{T}</math>를 구하면 <math>\begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \\ 0 \end{pmatrix}</math>이 된다. (이 부분에서, 행렬 '''v<sup>T</sup>'''로는 여러 행렬이 가능할 수도 있다) 이제 이 행렬을 전치하면 <math>v = \begin{pmatrix} 0 & 0 & 0 & 1 & 0 \\ \end{pmatrix}</math>이 된다. 


6. '''v'''의 성분들 중에 1인 곳들을 찾고, 그 부분에 대응하는 n의 값을 순서대로 각각 a<sub>r</sub>이라 한다. 이때, <math>x=a_1a_2a_3\cdots a_r\pmod N</math>, <math>y= \sqrt {(a_1^2-N)\cdot(a_2^2-N)\cdots(a_r^2-N)} </math>이라는 공식을 이용해서 x와 y의 값을 구한다. 이 예시의 경우, x=a<sub>1</sub>=26이 되고, y=(a<sub>1</sub><sup>2</sup>-667)<sup>1/2</sup>=(26<sup>2</sup>-667)<sup>1/2</sup>=3이 된다.


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가 된다.

실제로 이렇게 작은 수를 소인수분해할 때에는 이차 체 알고리즘은 효율적이지 않다. 667처럼 작은 수의 경우에는 [[폴라드 로 알고리즘]]이나 직접 나누기, 또는 [[폴라드의 P-1 알고리즘|폴라드의 p-1 알고리즘]]을 더 많이 사용하며, 보통 이차 체는 50자리가 넘고 약수가 2개 있는 수를 소인수분해할 때 쓰인다.

== 활용 ==
이차 체 알고리즘은 발견 당시에는 다른 알고리즘들에 비해서 매우 빠른 알고리즘이었기 때문에 큰 수를 소인수분해할 때 많이 쓰였으며, 요즘에는 [[렌스트라의 타원곡선 알고리즘]] (ECM, Elliptic Curve Method)을 특정 크기 미만의 약수들을 모두 구하게 하여 약수가 2개밖에 없는 것이 확인되거나 2개가 될 때까지 나눈 후 이 알고리즘을 적용한다. 보통 두 약수의 크기가 비슷할 때 잘 작동하며, 100자리 이상의 정수를 소인수분해할 때에는 [[수체 체]] (GNFS, General Number Field Sieve) 알고리즘을 더 많이 사용한다. 또한 RSA-129를 소인수분해할 때 이 알고리즘을 조금 더 확장하여 여러 개의 함수를 이용하는 (f(x)=x<sup>2</sup>-N 이외에 여러 함수를 사용한다) 다중 함수 이차 체 (MPQS, Multiple Polynomial Quadratic Sieve)를 사용하기도 했다.

== 같이 보기 ==
* [[내림 함수와 올림 함수|내림함수와 올림함수]]
* [[시간 복잡도]]
* [[점근 표기법]]

* [[:en:Lenstra_elliptic-curve_factorization|타원곡선 알고리즘]]
{{수론 알고리즘}}

[[분류:소인수 분해 알고리즘]]