이차 체

3. 기본 원리

이 알고리즘은 $x^2\; \backslash equiv\; y^2\; \backslash pmod\; n$ 이고, $(x+y,n)$와 $(x-y,n)$이 $1$이나 $n$과 같지 않다면, $n=(x+y,n)\; \backslash cdot\; (x-y,n)$인 점을 이용한다.^[2] ''n''을 인수분해하기 위해 제곱 합동 모듈러 연산을 이용하며, 두 단계로 작동한다.

1. 데이터 수집 단계: 제곱 합동으로 이어질 수 있는 정보를 수집한다.

2. 데이터 처리 단계: 수집된 데이터를 행렬에 넣고 해를 구하여 제곱 합동을 얻는다.

데이터 수집 단계는 여러 프로세서에서 병렬 컴퓨팅이 가능하지만, 데이터 처리 단계는 많은 메모리가 필요하여 여러 노드에서 효율적으로 병렬화하기 어렵다. 각 처리 노드가 전체 행렬을 저장할 만큼 충분한 메모리가 없는 경우에도 마찬가지이다. 블록 비데만 알고리즘은 각 시스템이 행렬을 보관할 수 있는 소수의 시스템에서 사용 가능하다.

제곱 합동을 찾는 간단한 방법은 임의의 숫자를 제곱하고 ''n''으로 나누어 가장 작은 음이 아닌 나머지가 제곱수가 되기를 기대하는 것이다. (예: $80^2\; \backslash equiv\; 441\; =\; 21^2\; \backslash pmod\{5959\}$). 이 방법은 큰 ''n''에서는 제곱 합동을 찾기 어렵지만, 찾으면 대부분 비자명하며 인수분해가 완료된다. 이는 페르마 인수분해법의 기본 원리이다.

제곱 체는 딕슨 인수분해법을 개선한 것이다. 페르마 방법은 ''a''²을 ''n''으로 나눈 나머지가 제곱수인 ''a''를 찾는 것이 어렵지만, 이차 체는 여러 ''a''에 대해 ''a''²/''n''의 나머지를 계산하고 그 곱이 제곱수가 되는 부분 집합을 찾는다.

예를 들어 1649를 소인수분해하면 다음과 같다.

:$41^2\; \backslash equiv\; 32,\; 42^2\; \backslash equiv\; 115,\; 43^2\; \backslash equiv\; 200\; \backslash pmod\{1649\}$

$32,\; 115,\; 200$ 중 제곱수는 없지만, $32\; \backslash cdot\; 200\; =\; 80^2$는 제곱수이다. 또한,

:$32\; \backslash cdot\; 200\; \backslash equiv\; 41^2\; \backslash cdot\; 43^2\; \backslash equiv\; (41\; \backslash cdot\; 43)^2\; \backslash equiv\; 114^2\; \backslash pmod\{1649\}$

:$41\; \backslash cdot\; 43\; \backslash equiv\; 114\; \backslash pmod\{1649\}$

$32\; \backslash cdot\; 200\; =\; 80^2$는 제곱 합동을 의미한다.

:$114^2\; \backslash equiv\; 80^2\; \backslash pmod\{1649\}$

$114^2\; -\; 80^2\; =\; (114\; +\; 80)\; \backslash cdot\; (114\; -\; 80)\; =\; 194\; \backslash cdot\; 34\; =\; k\; \backslash cdot\; 1649$ (k는 정수) 이므로,

:$1649\; =\; \backslash gcd(\; 194,\; 1649\; )\; \backslash cdot\; \backslash gcd(\; 34,\; 1649\; )\; =\; 97\; \backslash cdot\; 17$

유클리드 호제법으로 최대 공약수를 계산한다.

주어진 정수 집합에서 곱이 제곱수가 되는 부분 집합을 찾는 것이 중요하다. 산술의 기본 정리에 의해 모든 양의 정수는 소수 거듭제곱의 곱으로 유일하게 표현된다. 예를 들어 504는 2³3²5⁰7¹로 표현되며, 지수 벡터는 (3,2,0,1)이다. 두 정수를 곱하면 해당 지수 벡터를 더한다. 지수 벡터의 모든 좌표가 짝수이면 제곱수이다. (3,2,0,1) + (1,0,0,1) = (4,2,0,2)이므로 (504)(14)는 제곱수이다. 제곱수를 찾기 위해 벡터의 패리티만 고려하여 mod 2로 계산한다. (1,0,0,1) + (1,0,0,1) = (0,0,0,0)이므로, (0,1)-벡터 집합에서 영벡터 mod 2로 더해지는 부분 집합을 찾는다.

환 $\backslash mathbb\{Z\}/2\backslash mathbb\{Z\}$는 2차 갈루아 체이므로, mod 2 계산에서 0이 아닌 숫자(1)로 나눌 수 있어 선형 대수 문제로 볼 수 있다. 선형 대수 정리에 의해 각 벡터가 항목보다 많으면 선형 종속성이 존재하며, 가우스 소거법으로 찾을 수 있다.

많은 임의의 숫자를 mod ''n''으로 제곱하면 다양한 소수 인수가 생성되어 긴 벡터와 큰 행렬이 생긴다. ''a''² mod ''n''이 작은 소수 인수를 갖는 ''a''(매끄러운 수)를 찾는 것이 중요하다. 매끄러운 숫자만 사용하면 벡터와 행렬이 작아진다. 이차 체는 체론을 사용하여 매끄러운 숫자를 찾는다.

4. 알고리즘

이차 체 알고리즘은 $x^2\; \backslash equiv\; y^2\; \backslash pmod\; n$ 형태의 합동식을 찾아, $n\; =\; \backslash gcd(x+y,\; n)\; \backslash cdot\; \backslash gcd(x-y,\; n)$으로 소인수분해하는 방법이다.^[2] 이 알고리즘은 딕슨 인수분해법을 개선한 것이다. 실행 시간은 다음과 같다.

:$O\backslash left(e^\backslash sqrt\{\backslash log\; n\; \backslash log\backslash log\; n\}\backslash right)=L\_n\backslash left[\{1\; \backslash over2\},1\backslash right]$

알고리즘의 핵심 아이디어는 다음과 같다.

1. $y(x)\; =\; (\backslash lfloor\; \backslash sqrt\{n\}\; \backslash rfloor\; +\; x)^2\; -\; n$ 함수를 정의한다. (이 함수는 변경될 수 있다.)

2. $x^2\; \backslash equiv\; p\; \backslash pmod\; n$인 소수 ''p'' (제곱잉여)들을 찾는다.

3. $x^2\; \backslash equiv\; n\; \backslash pmod\; p$를 만족하는 ''x''를 찾는다.

4. 행렬 등을 이용해 완전제곱수가 되는 곱을 찾고, 이들을 곱해 완전제곱꼴로 만든다.

5. gcd(x+y, n)와 gcd(x-y, n)을 계산하여 ''n''의 약수를 구한다.
N=667 소인수분해 예시:1. p값: 야코비 기호를 이용하여 $\backslash left(\backslash frac\{N\}\{p\}\backslash right)\; =\; 1$을 만족하는 p = 2, 3, 7을 찾는다.

2. 범위: $\backslash lfloor\; \backslash sqrt\{667\}\; \backslash rfloor\; \backslash pm\; 8\; =\; 17,\; 33$ 범위를 설정한다.

3. p-smooth 확인: (정수)²-667이 2, 3, 7로만 소인수분해되는지 확인한다. (자세한 과정은 하위 섹션의 표 참고)

4. 행렬: p-smooth인 n값에 대해 p로 나누어지는 횟수를 나타내는 행렬을 만들고, 2로 나눈 나머지를 계산한 후 전치행렬을 구한다.

5. v 행렬: 전치 행렬과 곱했을 때 영벡터가 되는 행렬 v^T를 찾고, 전치하여 v를 구한다.

6. x, y: v에서 1인 성분에 대응하는 n 값으로 x, y를 계산한다.

7. 소인수분해: gcd(x-y, N), gcd(x+y, N)을 계산하여 667 = 23 ⋅ 29를 얻는다.
참고:

• 작은 수에는 폴라드 로 알고리즘 등 다른 알고리즘이 더 효율적이다.
• 이차 체는 50자리 이상, 약수가 2개인 수에 주로 사용된다.
• 데이터 수집 단계는 병렬 컴퓨팅이 가능하지만, 데이터 처리 단계는 메모리 요구량이 크고 병렬화가 어렵다. 블록 비데만 알고리즘이 사용될 수 있다.
• 페르마 인수분해법은 단일 숫자 a를 찾는 반면, 이차 체는 여러 a에 대해 a²/n의 나머지를 계산하고 곱이 제곱수가 되는 부분 집합을 찾는다.

4. 1. 1. 매끄러움 경계(Smoothness Bound) 설정

4. 2. 2. 데이터 수집 (체질 단계)

• p의 값을 구하기 위해 먼저 다음 식을 계산한다.

• 야코비 기호를 이용해 p를 구한다.

• 위의 식을 만족하는 p는 2, 3, 7이다. N이 홀수이면 p에는 2가 항상 포함된다.

• n의 값의 범위는 아래 표와 같이 17부터 33까지이다.
• 이 범위는 $\backslash lfloor\; \backslash sqrt\{667\}\; \backslash rfloor\; \backslash pm8=17,\; 33$으로 계산된다.
• 이 범위는 수의 크기에 따라 달라진다.

• (정수의 값)²-N이 p-smooth인지 확인하는 과정이다.
• p의 값들로만 완전히 소인수분해되는 정수들을 모은다.
• 실제로 (정수)²-N을 완전히 소인수분해할 필요는 없고, 2, 3, 7로 계속 나누어 본다.
• 계속 나눠서 1이 되면, 이 수는 p의 값들로 완전히 소인수분해되는 것이다.
• 더 이상 나눌 수 없는데 1보다 크면, 이 수는 p의 값들로 완전히 소인수분해되지 않는 것이다.

4. 3. 3. 데이터 처리 (행렬 처리 단계)

4단계에서는 2, 3, 7로 완전히 소인수분해되는 수의 n값(17, 18, 25, 26, 31)에 대해, p로 나누어지는 횟수들을 모은 행렬을 만든다. 그 후 행렬의 각 성분을 2로 나눈 나머지로 바꾼다.

• 17은 (1, 3, 1)
• 18은 (0, 0, 3)
• 25는 (1, 1, 1)
• 26은 (0, 2, 0)
• 31은 (1, 1, 2)

4. 4. 4. 제곱근 계산 및 최대공약수 계산

• $y(x)=(\backslash left\backslash lfloor\backslash sqrt\{n\}\backslash right\backslash rfloor+x\backslash right)^2-n$ 형태의 함수 $y(x)$를 정의한다. (이 함수는 변경될 수 있다.)

• $x^2\; \backslash \; \backslash equiv\backslash \; p\; \backslash pmod\{n\}$를 만족하는 소수 ''p'' (제곱잉여)를 $\backslash lceil\backslash ln(\backslash lceil\backslash sqrt\{x\}\backslash rceil^2-x)\backslash rceil$개 수집한다.

• $x^2\; \backslash \; \backslash equiv\backslash \; n\; \backslash pmod\{p\}$를 만족하는 자연수 ''x''를 찾는다.

• 행렬 또는 방정식을 이용하여 완전제곱수가 되는 곱을 찾는다.
• 찾은 곱들을 곱하여 완전제곱꼴로 만든다.

• gcd(x+y, n)와 gcd(x-y, n)을 계산하여 ''n''의 약수를 구한다.

• $\backslash lceil\backslash ln(\backslash lceil\; \backslash sqrt\{667\}\; \backslash rceil^\{2\}-667)\backslash rceil=3$개의 p를 구한다.
• $\backslash left\; (\; \backslash frac\{N\}\{p\}\; \backslash right\; )=1$ (야코비 기호)를 만족하는 p는 2, 3, 7이다. (N이 홀수이면 p는 항상 2를 포함한다.)

• $\backslash lfloor\; \backslash sqrt\{667\}\; \backslash rfloor\; \backslash pm8=17,\; 33$ 범위를 설정한다. (범위는 수의 크기에 따라 달라진다.)

• 범위 내 정수들의 제곱에서 N을 뺀 값((정수)²-N)이 2, 3, 7로만 소인수분해되는지 확인한다.
• 2, 3, 7로 계속 나누어 1이 되면 p-smooth이고, 1보다 큰 값이 남으면 p-smooth가 아니다.

4. 행렬 생성 및 전치:

• p-smooth인 n값에 대해 p로 나누어지는 횟수를 나타내는 행렬을 만든다.
• 각 성분을 2로 나눈 나머지로 바꾼 후 전치행렬을 구한다.
• 예시:
• 초기 행렬:
• 2로 나눈 나머지:
• 전치 행렬:

• 전치 행렬과 곱했을 때 열이 하나뿐인 제로벡터가 되는 행렬 '''v^T'''를 구한다.
• '''v^T'''를 전치하여 행이 하나인 행렬 '''v'''를 구한다.
• 예시:
• $v^\{T\}\; =\; \backslash begin\{pmatrix\}\; 0\; \backslash \backslash \; 0\; \backslash \backslash \; 0\; \backslash \backslash \; 1\; \backslash \backslash \; 0\; \backslash end\{pmatrix\}$

• '''v'''에서 1인 성분에 대응하는 n 값을 a_r이라 한다.
• $x=a\_1a\_2a\_3\backslash cdots\; a\_r\backslash pmod\; N$, $y=\; \backslash sqrt\; \{(a\_1^2-N)\backslash cdot(a\_2^2-N)\backslash cdots(a\_r^2-N)\}$ 공식을 이용한다.
• 예시: x = 26, y = 3

• x²≡y² (mod N) 관계를 이용한다.
• N의 약수는 gcd(x-y, N), gcd(x+y, N)이다.
• N = gcd(x-y, N) ⋅ gcd(x+y, N)
• 예시: 667 = gcd(23, 667) ⋅ gcd(29, 667) = 23 ⋅ 29

• 작은 수(예: 667)의 소인수분해에는 이차 체 알고리즘이 비효율적이다. 폴라드 로 알고리즘, 시도 나눗셈, 폴라드의 p-1 알고리즘 등이 더 효율적이다.
• 이차 체는 주로 50자리 이상이고 약수가 2개 있는 수를 소인수분해할 때 사용된다.

• 방정식의 곱의 지수를 행렬로 표현 (mod 2):

• 왼쪽 영공간을 이용하여 해를 구함:
• 세 방정식의 곱은 제곱(mod N): $29\; \backslash cdot\; 782\; \backslash cdot\; 22678\; =\; 22678^2$
• $124^2\; \backslash cdot\; 127^2\; \backslash cdot\; 195^2\; =\; 3070860^2$
• $22678^2\; \backslash equiv\; 3070860^2\; \backslash pmod\{15347\}$
• GCD(3070860 - 22678, 15347) = 103 (15347의 자명하지 않은 인수), 다른 하나는 149.

5. 최적화 기법

이차 체는 ''x''² ≡ ''y''² (mod ''n'')보다 훨씬 약한 조건을 만족하는 정수 쌍 ''x''와 ''y''(''x'')를 찾는다. 여기서 ''y''(''x'')는 ''x''의 함수이다. 이 알고리즘은 '인수 기저'라고 하는 소수 집합을 선택하고, ''y''(''x'') = ''x''² mod ''n''의 최소 절대 나머지가 인수 기저에서 완전히 인수분해되는 ''x''를 찾으려고 시도한다. 이러한 ''y'' 값은 인수 기저에 대해 '부드럽다'고 한다.

인수 기저에서 분해되는 ''y''(''x'') 값의 인수분해는 ''x'' 값과 함께 '관계'라고 한다. 이차 체는 ''x''를 √''n''에 가깝게 하여 관계를 찾는 과정을 가속화한다. 이렇게 하면 ''y''(''x'')가 작아져 부드러워질 가능성이 높아진다.

:$y(x)=\backslash left(\backslash left\backslash lceil\backslash sqrt\{n\}\backslash right\backslash rceil+x\backslash right)^2-n\backslash hbox\{\; (여기서\; \}x\backslash hbox\{는\; 작은\; 정수)\}$

:$y(x)\backslash approx\; 2x\backslash left\backslash lceil\backslash sqrt\{n\}\backslash right\backslash rceil$

이는 ''y''가 2''x''''n''의 차수임을 의미한다. 그러나 ''y''가 √''n''에 ''x''를 곱한 값에 비례하여 선형적으로 증가한다는 의미이기도 하다.

부드러움을 증가시키는 또 다른 방법은 단순히 인수 기저의 크기를 늘리는 것이다. 그러나 선형 종속성의 존재를 보장하려면 인수 기저의 소수 개수보다 최소한 하나 이상의 부드러운 관계를 찾아야 한다.

5. 1. 다중 다항식 (Multiple Polynomials)

5. 2. 큰 소수 변형 (Large Prime Variation)

6. 활용

이차 체 알고리즘은 발견 당시 다른 알고리즘들에 비해 매우 빨라 큰 수를 소인수분해할 때 많이 쓰였다. 요즘에는 렌스트라의 타원곡선 알고리즘 (ECM)으로 특정 크기 미만의 약수들을 모두 구하고, 약수가 2개밖에 없는 것이 확인되거나 2개가 될 때까지 나눈 후 이 알고리즘을 적용한다. 보통 두 약수의 크기가 비슷할 때 잘 작동하며, 100자리 이상의 정수를 소인수분해할 때에는 수체 체 (GNFS) 알고리즘을 더 많이 사용한다.^[3]

일반 수체 체 (NFS)가 발견되기 전까지, QS는 점근적으로 가장 빠른 범용 인수분해 알고리즘으로 알려져 있었다. 현재, 렌스트라 타원 곡선 인수분해는 QS와 동일한 점근적 실행 시간을 갖지만, QS가 단일 정밀도 연산을 사용하기 때문에 실제로는 더 빠르다.^[3]

1994년 4월 2일, RSA-129의 인수분해가 QS를 사용하여 완료되었다. 이는 129자리 숫자였으며, 64자리와 65자리의 두 개의 큰 소수의 곱이었다. 데이터 수집 단계는 인터넷을 통해 분산 방식으로 5000 MIPS-년이 소요되었고, 데이터 처리 단계는 Bellcore(현재 Telcordia Technologies)의 MasPar 슈퍼컴퓨터에서 45시간이 걸렸다. 이는 1996년 4월 10일에 NFS를 사용하여 RSA-130을 인수분해하기 전까지 범용 알고리즘으로 수행된 가장 큰 인수분해였다.^[3]

현재 QS 인수분해 기록은 2020년 6월에 패트릭 콘서가 약 6,000 코어 시간 동안 6일 동안 사용하여 인수분해한 140자리(463비트) RSA-140이다.^[3]

이차 체 알고리즘의 다양한 구현체는 다음과 같다.

7. 한계

렌스트라 타원 곡선 인수분해는 이차 체(QS)와 점근적 실행 시간이 동일하지만(n이 동일한 크기의 소수 인수를 정확히 두 개 갖는 경우), 실제로는 QS가 더 빠르다. 왜냐하면 QS는 타원 곡선 방법에서 사용되는 다중 정밀도 연산 대신 단일 정밀도 연산을 사용하기 때문이다.^[3]

1994년 4월 2일, RSA-129의 인수분해가 QS를 사용하여 완료되었다. 이는 129자리의 숫자였으며, 64자리와 65자리의 두 개의 큰 소수의 곱이었다. 이 인수분해의 인수 기저는 524339개의 소수를 포함했다. 데이터 수집 단계는 인터넷을 통해 분산 방식으로 5000 MIPS-년이 소요되었고, 수집된 데이터는 총 2GB였다. 데이터 처리 단계는 Bellcore(현재 Telcordia Technologies)의 MasPar (대규모 병렬) 슈퍼컴퓨터에서 45시간이 걸렸다. 이는 1996년 4월 10일에 일반 수체 체(NFS)를 사용하여 RSA-130을 인수분해하기 전까지 범용 알고리즘으로 수행된 가장 큰 인수분해였다. 그 이후로 인수분해된 모든 RSA 숫자는 NFS를 사용하여 인수분해되었다.^[3]

현재 QS 인수분해 기록은 2020년 6월에 패트릭 콘서가 약 6,000 코어 시간 동안 6일 동안 사용하여 인수분해한 140자리(463비트) RSA-140이다.^[3]

참조

_[1] 서적 Analysis and Comparison of Some Integer Factoring Algorithms Math. Centre Tract 154, Amsterdam 1982
_[2] 뉴스 A Tale of Two Sieves https://www.ams.org/[...] 1996-12
_[3] 웹사이트 Useless Accomplishment: RSA-140 Factorization with Quadratic Sieve - mersenneforum.org https://www.mersenne[...] 2020-07-07