일반 수체 체법(GNFS)의 진정한 수학적 구조

GNFS의 궁극적인 목적은 $X^2 \equiv Y^2 \pmod N$이 되는 $X, Y$를 찾는 것입니다. 이를 달성하기 위해 수학자들은 「현실의 정수 세계」 와 「대수체의 세계」 사이에 다리를 놓았습니다. 그 다리가 바로 「준동형 사상」입니다.

제1단계: 세계를 연결하는 「준동형 사상(Homomorphism)」

1. 다항식의 선정과 근의 정의

거대한 합성수 $N$에 대해, 어떤 정수 $m$과 다항식 $f(x)$를 선택하여, $f(m) \equiv 0 \pmod N$이 되도록 합니다. (예: $N$을 $m$진수로 전개하고, 그 계수로부터 $f(x)$를 만듭니다. 이때 $f(x)$는 유리수체 $\mathbb{Q}$ 위에서 기약(더 이상 인수분해할 수 없음)이라고 가정합니다).

다음으로, 방정식 $f(x) = 0$의 「복소수에서의 근」 중 하나를 $\alpha$로 둡니다. 당연히 $f(\alpha) = 0$입니다. $\alpha$는 정수가 아니라, 루트나 허수를 포함하는 복잡한 수(대수적 수)입니다.

2. 환(Ring)과 준동형 사상의 구축

여기서 두 개의 수학적인 「환(덧셈과 곱셈이 정의된 세계)」을 준비합니다.

• 세계A: $\mathbb{Z}[\alpha]$ ($\alpha$를 포함하는 대수적 정수환) $a + b\alpha + c\alpha^2 + \dots$ 형태로 표현되는 수의 세계입니다.
• 세계B: $\mathbb{Z}/N\mathbb{Z}$ ($N$으로 나눈 나머지의 환) $0$부터 $N-1$까지의 정수로만 구성된, 합동식(모듈로)의 세계입니다.

여기서 세계A에서 세계B로, 다음과 같은 매핑(사상) $\phi$를 정의합니다. $$\phi : \mathbb{Z}[\alpha] \to \mathbb{Z}/N\mathbb{Z}$$ $$\phi(\alpha) = m \pmod N$$

이 사상 $\phi$는 세계A의 변수 $\alpha$를 그대로 세계B의 정수 $m$으로 바꿔치기하는 마법의 조작입니다. 이 $\phi$는 「환 준동형 사상(Ring Homomorphism)」 이라는 극히 강력한 성질을 가지고 있습니다. 준동형이란 「덧셈이나 곱셈의 구조를 깨뜨리지 않고 다른 세계로 워프시키는」 성질을 의미합니다. 즉, 다음 식이 성립합니다.

• $\phi(X \times Y) = \phi(X) \times \phi(Y)$
• $\phi(X^2) = \phi(X)^2$

이것이 무엇을 의미할까요? 만약 우리가 「세계A($\alpha$의 세계)」에서 어떤 복잡한 요소 $\gamma$의 「제곱($\gamma^2$)」 을 만들 수 있다면, 그것을 $\phi$로 「세계B(나머지의 세계)」로 워프시켜도 ** 훌륭하게 제곱의 형태 $\phi(\gamma)^2$가 유지된다** 는 것입니다.

제2단계: 소인수분해의 붕괴와 「아이디얼(Ideal)」의 탄생

우리는 세계A($\mathbb{Z}[\alpha]$) 안에서 적당한 요소 $(a - b\alpha)$를 많이 모아, 그것들을 곱해서 「완전한 제곱(평방원)」을 만들고자 합니다. 보통이라면 모은 $(a - b\alpha)$를 각각 「소인수분해」해서, 소수의 지수가 모두 짝수가 되도록 조합(행렬로 풂)하면 제곱을 만들 수 있습니다.

하지만, 여기서 대수학의 절망적인 장벽이 앞을 가로막습니다. $\mathbb{Z}[\alpha]$와 같은 대수체의 세계에서는, 중학교 때 배우는 「소인수분해의 유일성(어떤 수도 소수의 곱셈으로 단 한 가지로만 표현할 수 있다)」이 붕괴되어 버리는 것입니다.

(예: 어떤 대수체의 세계에서는 $6 = 2 \times 3$ 이며, 동시에 $6 = (1+\sqrt{-5}) \times (1-\sqrt{-5})$ 가 되어버려, 어느 쪽이 진짜 소수인지 알 수 없게 됩니다)

소인수분해가 한 가지로 정해지지 않으면, 「소수의 개수를 세어 짝수 개로 만든다」는 퍼즐(체법)을 원리적으로 실행할 수 없습니다.

쿠머와 데데킨트의 구원: 「아이디얼」

이 붕괴를 구원한 것이, 19세기의 수학자들이 만들어낸 「아이디얼(Ideal: 이상수)」 이라는 개념입니다. 요소 자체가 아니라, 그 요소가 생성하는 「배수의 집합(아이디얼)」을 생각함으로써 다시 소인수분해를 가능하게 한 것입니다.

대수체의 정수환 $\mathcal{O}_K$($\mathbb{Z}[\alpha]$를 포함하는 더 완전한 환)에서, 요소는 유일하게 소인수분해할 수 없어도, 「아이디얼은 반드시 『소 아이디얼($\mathfrak{p}$)』의 곱으로 단 한 가지로 소인수분해할 수 있다」 는 것이 증명되어 있습니다.

따라서 GNFS에서는 요소 $(a - b\alpha)$ 자체를 분해하는 것이 아니라, 그것이 생성하는 단항 아이디얼 $\langle a - b\alpha \rangle$을 소 아이디얼 분해 합니다.

제3단계: 노름(Norm)과 두 개의 체(Sieve)

그렇다면, 아이디얼 $\langle a - b\alpha \rangle$이 어떤 소 아이디얼로 분해되는지 어떻게 알 수 있을까요? 여기서 「노름(Norm)」 이라는 함수를 사용합니다. 노름이란, 대수체의 복잡한 요소를 「평범한 현실의 정수 $\mathbb{Z}$」로 변환하는 함수입니다.

요소 $(a - b\alpha)$의 노름은 $b^d f(a/b)$라는 간단한 다항식 계산으로 구할 수 있습니다($d$는 $f(x)$의 차수).

대수학의 정리에 의해, 「어떤 아이디얼의 노름이 작은 소수로 완전히 분해될 수 있다면(매끄럽다면), 그 원래의 아이디얼도 작은 소 아이디얼로 완전히 분해될 수 있다」 는 것이 알려져 있습니다.

그래서 GNFS는 대량의 정수 쌍 $(a, b)$에 대해 다음 두 가지를 동시에 계산하고, 양쪽 모두가 「매끄러운 수」가 되는 쌍만을 수집합니다.

1. 유리 체(Rational Sieve): $a - bm$ (현실 세계의 값)
2. 대수 체(Algebraic Sieve): $b^d f(a/b)$ (대수체의 세계에서의 노름)

양쪽 모두 매끄러운 쌍 $(a, b)$를 수천만 개 모아, 아이디얼의 소인수분해 데이터(소 아이디얼이 몇 개 포함되어 있는지)를 거대한 행렬(GF(2) 위에서의 선형대수)로 풀어, 「곱하면 모든 소 아이디얼의 지수가 짝수가 되는」 쌍의 집합 $S$를 찾습니다.

제4단계: 앞을 가로막는 두 개의 「장애물」과 아이디얼 류군

행렬 계산을 통해 집합 $S$에 속하는 $(a - b\alpha)$의 아이디얼을 모두 곱하면, 어떤 아이디얼 $I$의 제곱이 된다는 것을 알았습니다.

하지만 아직 끝나지 않았습니다. GNFS에서 가장 깊고, 가장 어려운 수학의 벽이 여기에 있습니다.

우리가 마지막으로 원하는 것은 「아이디얼의 제곱」이 아니라, 사상 $\phi$에 대입하기 위한 「요소의 제곱($\gamma^2$)」 입니다. 아이디얼의 제곱이 되었다고 해서, 요소 자체가 제곱이 되어 있다는 보장은 없습니다. 여기에는 두 가지 강력한 수학적 장애물(Obstruction) 이 존재합니다.

장애물①: 아이디얼 류군(Ideal Class Group)의 벽

아이디얼 $I$는 반드시 「하나의 요소로 생성되는 아이디얼(단항 아이디얼)」이라고는 할 수 없습니다. 단항 아이디얼이 아닌 아이디얼에서 구체적인 요소 $\gamma$를 꺼내는 것은 불가능합니다.

여기서 「아이디얼 류군(Class Group, $Cl_K$)」 이라는 개념이 등장합니다. 아이디얼 류군이란, 「그 대수체의 세계에 단항 아이디얼이 아닌 아이디얼이 얼마나 존재하는가(소인수분해의 유일성이 얼마나 깨져 있는가)」를 측정하는 군입니다. $\prod \langle a - b\alpha \rangle$이 $I^2$이 되었다고 해도, $I$가 아이디얼 류군에서 단위원(단항 아이디얼)이 아니라면, 요소의 제곱으로 되돌릴 수 없습니다.

장애물②: 단수군(Unit Group)의 벽

만약 운 좋게 $I$가 단항 아이디얼 $\langle \gamma \rangle$이었다고 해봅시다. 그러면 $\prod \langle a - b\alpha \rangle = \langle \gamma^2 \rangle$이 됩니다. 「좋아, 요소도 제곱이다!」라고 생각할지 모르지만, 큰 착각입니다.

아이디얼(배수의 집합)이 같다는 것이 요소가 완전히 같다는 것을 의미하지는 않습니다. 반드시 「단수(Unit: 역수도 정수가 되는 수. 1이나 -1 등)」 의 차이가 발생합니다. 즉, 실제 요소의 등식은 다음과 같이 됩니다.

($u$는 단수군 $U_K$의 요소)

이 단수 $u$ 자체가 무언가의 제곱(평방원)이 아니라면, 좌변은 절대로 「완전한 요소의 제곱」이 될 수 없습니다.

제5단계: 애들먼의 마법 「이차 잉여 지표(Quadratic Characters)」

아이디얼 류군의 장애물과 단수군의 장애물. 이 두 가지를 어떻게 뛰어넘을 것인가? 여기서 암호학자 레너드 애들먼(RSA의 “A”) 등이 도입한 천재적인 수법 「이차 잉여 지표(Quadratic Characters)」 가 등장합니다.

「어떤 요소가 대수체 안에서 완전히 제곱이 되어 있는가?」를 판정하기 위해, 르장드르 기호(이차 잉여)의 대수체 버전을 사용합니다. 아까의 거대한 행렬(소 아이디얼의 개수를 짝수로 만들기 위한 퍼즐)에 「몇 가지 특별한 소 아이디얼 $\mathfrak{q}$에 대한 이차 잉여 지표도 모두 $1$(짝수)이 된다」는 추가 조건(열)을 수십 개 정도 몰래 덧붙이는 것입니다.

행렬 계산에 의해 이 추가 조건조차도 만족하는 집합 $S$를 찾았을 때, 대수적 정수론의 깊은 정리에 의해 「아이디얼 류군의 장애물도, 단수군의 장애물도, 압도적인 확률로 자연스럽게 소멸한다」 는 것이 보장됩니다.

이를 통해 마침내 우리는 진정한 등식을 손에 넣게 됩니다.

최종 단계: 세계의 융합과 암호 붕괴

드디어 퍼즐의 모든 조각이 맞춰졌습니다.

【대수체의 세계(세계A)의 요소】 $\gamma^2 = \prod (a - b\alpha)$ (이것을 제곱근 알고리즘을 사용하여 $\gamma$를 구합니다)

【현실의 세계(유리수의 세계)의 요소】 $V^2 = \prod (a - bm)$ (이쪽은 단순한 정수의 곱셈이므로, 평범하게 제곱근 $V$가 구해집니다)

자, 맨 처음에 만든 마법의 다리, 준동형 사상 $\phi$ 가 나설 차례입니다. 세계A의 요소 $\gamma$를, $\phi$($\alpha$에 $m$을 대입하는 사상)를 사용하여 세계B($N$의 나머지 세계)로 워프시킵니다.

한편, 현실 세계에서 만든 $V$를 그대로 나머지 세계로 가져가 $X$로 둡니다.

준동형 사상의 「구조를 보존하는」 성질에 의해, 세계A에서 성립하던 제곱의 관계는 세계B(모듈로 $N$의 세계)에서도 완전히 보존되어 있습니다. 게다가 원래의 쌍 $(a, b)$는 $a - b\alpha$와 $a - bm$이라는 형태로 대응되어 만들어졌기 때문에, 이 $X$와 $Y$는 모듈로 $N$의 세계에서 격돌하며 다음의 절대적인 등식을 낳습니다.

$$X^2 \equiv Y^2 \pmod N$$

이제 이 $X$와 $Y$가 자명한 해($X \equiv \pm Y$)가 아니기를 기도하며, $\gcd(X - Y, N)$ 을 계산합니다.

비자명한 해라면, 유클리드 호제법이 0.001초 만에 실행되며 RSA 암호의 심장부인 비밀 소수 $p$와 $q$가 출력 화면에 인쇄됩니다.

이것이 현대 수학의 정수를 모은 「일반 수체 체법(GNFS)」의 완전한 모습 입니다.