Истинная математическая структура общего метода решета числового поля (GNFS)

Конечная цель GNFS — найти $X, Y$ такие, что $X^2 \equiv Y^2 \pmod N$. Для достижения этого математики построили мост между “миром реальных целых чисел” и “миром алгебраических полей”. Этим мостом является «гомоморфизм».

Этап 1: «Гомоморфизм» (Homomorphism), соединяющий миры

1. Выбор многочлена и определение корня

Для гигантского составного числа $N$ мы выбираем некоторое целое число $m$ и многочлен $f(x)$ так, чтобы $f(m) \equiv 0 \pmod N$. (Пример: Разложите $N$ по основанию $m$ и постройте $f(x)$ из его коэффициентов. При этом предполагается, что $f(x)$ неприводим над полем рациональных чисел $\mathbb{Q}$).

Далее, пусть $\alpha$ — один из «комплексных корней» уравнения $f(x) = 0$. Естественно, $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$.

Здесь мы определяем отображение (mapping) $\phi$ из Мира A в Мир B следующим образом: $$\phi : \mathbb{Z}[\alpha] \to \mathbb{Z}/N\mathbb{Z}$$ $$\phi(\alpha) = m \pmod N$$

Это отображение $\phi$ — магическая операция, которая полностью заменяет переменную $\alpha$ в Мире A на целое число $m$ в Мире B. Это $\phi$ обладает чрезвычайно мощным свойством, называемым “Гомоморфизм колец” (Ring Homomorphism). Гомоморфизм — это свойство “перехода в другой мир без разрушения структуры сложения и умножения”. То есть выполняются следующие уравнения:

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

Что все это значит? Если мы сможем создать “полный квадрат” ($\gamma^2$) из сложного элемента $\gamma$ в “Мире A” (мире $\alpha$), мы сможем прыгнуть в “Мир B” (мир остатков) с помощью $\phi$, и форма квадрата $\phi(\gamma)^2$ будет идеально сохранена.

Этап 2: Крах разложения на простые множители и рождение «Идеала» (Ideal)

Мы хотим собрать множество подходящих элементов $(a - b\alpha)$ в Мире A ($\mathbb{Z}[\alpha]$) и перемножить их, чтобы получить «полный квадрат» (квадратичный элемент). Обычно мы могли бы разложить собранные $(a - b\alpha)$ на «простые множители» и объединить их так, чтобы все показатели степеней простых чисел стали четными (решается с помощью матриц), создавая таким образом квадрат.

Однако здесь на пути встает стена алгебраического отчаяния. В мире алгебраических полей, таких как $\mathbb{Z}[\alpha]$, “уникальность разложения на простые множители (каждое число может быть представлено как произведение простых чисел только одним способом)”, которую мы изучали в средней школе, полностью рушится.

(Пример: В некоторых мирах алгебраических полей $6 = 2 \times 3$, и в то же время $6 = (1+\sqrt{-5}) \times (1-\sqrt{-5})$, что делает невозможным узнать, какие из них являются истинными простыми числами).

Если разложение на простые множители не уникально, то головоломка “подсчета простых чисел до тех пор, пока их не станет четное количество” (метод решета) принципиально невыполнима.

Спасение Куммера и Дедекинда: «Идеал»

Этот крах был спасен концепцией “Идеала” (Ideal: Идеальное число), созданной математиками 19 века. Вместо того чтобы рассматривать сам элемент, рассматривая “множество кратных (идеал)”, порожденное этим элементом, разложение на простые множители снова стало возможным.

В кольце целых чисел алгебраического поля $\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: Два «Препятствия» и группа классов идеалов

С помощью матричных вычислений мы обнаружили, что умножение всех идеалов $(a - b\alpha)$ во множестве $S$ дает квадрат некоторого идеала $I$.

Но это еще не конец. Самая глубокая и трудная математическая стена в GNFS находится здесь.

В конечном итоге нам нужен не “квадрат идеала”, а “квадрат элемента” ($\gamma^2$) для подстановки в отображение $\phi$. Только потому, что идеал возведен в квадрат, не означает, что сам элемент возведен в квадрат. Здесь существуют два невероятно сильных математических препятствия (Obstructions).

Препятствие 1: Стена группы классов идеалов (Ideal Class Group)

Идеал $I$ не всегда является “идеалом, порожденным одним элементом (главным идеалом)”. Невозможно извлечь конкретный элемент $\gamma$ из идеала, который не является главным.

Здесь появляется концепция “Группы классов идеалов (Class Group, $Cl_K$)”. Группа классов идеалов — это группа, которая измеряет, “сколько неглавных идеалов существует в мире алгебраического поля (насколько разрушена уникальность разложения на простые множители)”. Даже если $\prod \langle a - b\alpha \rangle$ становится $I^2$, если $I$ не является единичным элементом (главным идеалом) в группе классов идеалов, мы не можем вернуть его к квадрату элемента.

Препятствие 2: Стена группы единиц (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)

Препятствие группы классов идеалов и препятствие группы единиц. Как нам их преодолеть? Здесь появляется гениальный метод, называемый “Квадратичными характерами” (Quadratic Characters), введенный криптографом Леонардом Адлеманом (буква “A” в RSA) и его коллегами.

Чтобы определить, “является ли элемент полным квадратом в алгебраическом поле”, мы используем версию символа Лежандра (квадратичного вычета) для алгебраических полей. В гигантскую матрицу (головоломку для того, чтобы сделать количество простых идеалов четным) мы тайно добавляем несколько десятков дополнительных условий (столбцов), утверждающих, что “квадратичные характеры для некоторых особых простых идеалов $\mathfrak{q}$ также все становятся равными $1$ (четными)”.

Когда мы находим множество $S$, удовлетворяющее этим дополнительным условиям с помощью матричных вычислений, глубокая теорема алгебраической теории чисел гарантирует, что “как препятствие группы классов идеалов, так и препятствие группы единиц исчезнут естественным образом с подавляющей вероятностью”.

Благодаря этому мы наконец получаем истинное уравнение:

Финальный этап: Слияние миров и взлом криптографии

Наконец, все кусочки головоломки на месте.

[Элемент в мире алгебраического поля (Мир A)] $\gamma^2 = \prod (a - b\alpha)$ (Используйте алгоритм извлечения квадратного корня, чтобы найти $\gamma$)

[Элемент в реальном мире (мир рациональных чисел)] $V^2 = \prod (a - bm)$ (Это просто обычное умножение целых чисел, поэтому квадратный корень $V$ можно найти легко)

Теперь настало время для работы первого магического моста, который мы создали, гомоморфизма $\phi$. Мы переносим элемент $\gamma$ из Мира A в Мир B (мир остатков $N$) с помощью $\phi$ (отображения, которое подставляет $m$ вместо $\alpha$).

С другой стороны, мы берем $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 секунды, и секретные простые числа $p$ и $q$, которые являются сердцем криптографии RSA, будут выведены на экран.

Это и есть полная картина “Общего метода решета числового поля (GNFS)”, который объединяет в себе суть современной математики.