【Полное понимание через формулы】 Почему сильнейший классический «GNFS» проигрывает квантовым алгоритмам? Смена парадигмы в факторизации

Информационная безопасность в современном интернет-обществе защищена криптографией с открытым ключом, такой как RSA. Основа безопасности RSA опирается на тот факт, что “факторизация огромных составных чисел вычислительно крайне сложна” .

В этой статье мы раскроем математический механизм “Общего метода решета числового поля” (GNFS) — самого мощного алгоритма факторизации для классических компьютеров, и подробно разберем, почему он полностью побежден “Алгоритмом Шора” , открытым Питером Шором. Мы глубоко исследуем эту смену парадигмы с помощью математических формул и концептуальных схем.

1. Подход к факторизации в классических вычислениях: развитие метода факторизации Ферма

Задача факторизации — это задача поиска простых чисел $p, q$, таких что $N = p \times q$ для заданного составного числа $N$.

Основная идея сводится к поиску нетривиальных $x, y$, удовлетворяющих следующему сравнению:

$$ x^2 \equiv y^2 \pmod N $$

Если мы преобразуем это, то получим:

$$ x^2 - y^2 \equiv 0 \pmod N $$ $$ (x - y)(x + y) \equiv 0 \pmod N $$

Здесь, если $x \not\equiv \pm y \pmod N$, мы можем получить нетривиальный делитель $N$, вычислив $\gcd(x-y, N)$ или $\gcd(x+y, N)$. Этот факт лежит в основе современных алгоритмов факторизации, таких как GNFS.

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

“GNFS” — это самый быстрый алгоритм факторизации для классических компьютеров из известных на сегодняшний день. Его временная сложность требует субэкспоненциального (Sub-exponential) времени.

Сложность GNFS

Если предположить, что количество цифр $N$ равно $b = \log_2 N$, сложность GNFS может быть выражена следующим образом:

$$ O\left( \exp \left( \left(\frac{64}{9} b\right)^{1/3} (\log b)^{2/3} \right) \right) $$

Как видно из этой формулы, сложность представляет собой не полиномиальное время, а “субэкспоненциальное время” , что лишь немного медленнее экспоненциального. Тем не менее, с увеличением количества цифр время вычислений возрастает астрономически.

Математический механизм GNFS

GNFS можно условно разделить на 4 этапа:

Выбор многочленов (Polynomial Selection)
Просеивание (Sieving)
Редукция матрицы (Matrix Reduction)
Вычисление квадратного корня (Square Root)

2.1. Выбор многочленов и алгебраическое числовое поле

Сначала выбираются неприводимые многочлены $f(x)$ и $g(x)$ с целыми коэффициентами. Они задаются так, чтобы иметь общий корень $m$ по модулю $N$. То есть:

$$ f(m) \equiv 0 \pmod N $$ $$ g(m) \equiv 0 \pmod N $$

Обычно $g(x)$ выбирается как многочлен первой степени $g(x) = x - m$. Если корень $f(x)$ обозначить как $\alpha$, образуется “алгебраическое числовое поле” (Number Field) $\mathbb{Q}(\alpha)$. Мы сравниваем операции в кольце $\mathbb{Q}(\alpha)$ и операции в обычном кольце целых чисел $\mathbb{Z}$ посредством гомоморфизма $\phi: \alpha \mapsto m$.

2.2. Просеивание (Sieving)

Далее мы ищем большое количество пар взаимно простых целых чисел $(a, b)$. Цель — найти такие пары, чтобы оба следующих значения были “B-гладкими” (B-smooth, то есть состоящими только из относительно малых простых множителей):

$a - bm$ (значение в кольце целых чисел)
$b^d f(a/b)$ (соответствует норме $N(a - b\alpha)$ в алгебраическом поле)

Здесь используется метод быстрого поиска, называемый “Решето” (Sieve). Это позволяет эффективно извлекать пары $(a, b)$, удовлетворяющие условиям, из огромного числа кандидатов.

2.3. Редукция матрицы (Linear Algebra over GF(2))

Из собранных пар $(a, b)$ мы формируем векторы показателей степени и находим левое нуль-пространство огромной разреженной матрицы над $\mathbb{F}_2$ (поле, содержащее только 0 и 1).

Мы находим вектор решения $v$ так, чтобы соотношения $ \prod (a_i - b_i m) $ и $ \prod (a_i - b_i \alpha) $ становились полными квадратами. Это не что иное, как решение системы линейных уравнений:

$$ M \mathbf{x} \equiv \mathbf{0} \pmod 2 $$

Здесь используются продвинутые алгоритмы численных вычислений, такие как алгоритм блочного Ланцоша (Block Lanczos) или блочного Видемана (Block Wiedemann).

2.4. Вычисление квадратного корня

Наконец, мы извлекаем квадратный корень как в алгебраическом числовом поле, так и в кольце целых чисел, что приводит к соотношению $x^2 \equiv y^2 \pmod N$. Затем мы вычисляем $\gcd(x-y, N)$ и получаем делитель.

3. Прорыв квантовых вычислений: “Алгоритм Шора”

В то время как GNFS требует субэкспоненциального времени, “Алгоритм Шора” , опубликованный Питером Шором в 1994 году, может решить эту задачу за “полиномиальное время” с использованием квантового компьютера.

Сложность Алгоритма Шора

Если предположить, что количество кубитов равно $O(\log N)$, то временная сложность составит:

$$ O((\log N)^3) $$

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

Обзор Алгоритма Шора: Сведение к задаче поиска периода

Алгоритм Шора искусно сводит задачу факторизации к “задаче поиска периода” .

Выберите случайное целое число $a$, взаимно простое с $N$ ($1 < a < N$).
Определите функцию $f(x) = a^x \bmod N$.
Найдите период $r$ функции $f(x)$, то есть наименьшее положительное целое число $r$ такое, что $a^r \equiv 1 \pmod N$.
Если $r$ четное, проверьте, не выполняется ли $a^{r/2} \not\equiv -1 \pmod N$, и вычислите $\gcd(a^{r/2} \pm 1, N)$ для получения простого делителя.

Этот шаг 3, то есть “нахождение периода $r$” , является узким местом, требующим экспоненциального времени на классическом компьютере. Однако квантовый компьютер решает это мгновенно, используя “квантовую суперпозицию” и “Квантовое преобразование Фурье” (QFT).

4. Квантовое преобразование Фурье (QFT) и извлечение периода

Давайте подробнее рассмотрим математические операции над квантовыми состояниями, которые лежат в основе Алгоритма Шора.

4.1. Генерация квантовой суперпозиции

Сначала подготовьте 2 квантовых регистра. Регистр 1 хранит состояние суперпозиции входных данных $x$, а регистр 2 хранит результат вычисления функции $f(x)$. Примените преобразование Адамара (Hadamard Transform) к начальному состоянию $|0\rangle |0\rangle$, чтобы создать суперпозицию всех возможных значений $x$.

$$ |\psi_1\rangle = \frac{1}{\sqrt{Q}} \sum_{x=0}^{Q-1} |x\rangle |0\rangle $$

(где $Q$ — это степень двойки, удовлетворяющая $N^2 \le Q < 2N^2$)

Далее используйте квантовый оракул $U_f$ для вычисления $f(x) = a^x \bmod N$ и сохраните результат в регистре 2.

$$ |\psi_2\rangle = U_f |\psi_1\rangle = \frac{1}{\sqrt{Q}} \sum_{x=0}^{Q-1} |x\rangle |a^x \bmod N\rangle $$

Предположим теперь, что регистр 2 измеряется (теоретически, даже если он не измеряется, математическая структура та же). Если наблюдается некоторое значение $y = a^{x_0} \bmod N$, состояние регистра 1 коллапсирует в суперпозицию всех $x$, удовлетворяющих $f(x) = y$. Если предположить, что период равен $r$, такие $x$ будут иметь вид $x_0, x_0 + r, x_0 + 2r, \dots$

$$ |\psi_3\rangle = \frac{1}{\sqrt{M}} \sum_{k=0}^{M-1} |x_0 + kr\rangle $$

(где $M \approx Q/r$ — количество членов)

Это состояние содержит информацию о периоде $r$, но прямое измерение даст лишь случайное $x_0 + kr$, и период $r$ останется неизвестным. Здесь вступает в дело QFT.

4.2. Применение Квантового преобразования Фурье (QFT)

QFT — это операция, применяющая дискретное преобразование Фурье к амплитудам квантового состояния. Действие QFT на состояние $|x\rangle$ определяется следующим образом:

$$ \text{QFT} |x\rangle = \frac{1}{\sqrt{Q}} \sum_{y=0}^{Q-1} e^{2\pi i \frac{xy}{Q}} |y\rangle $$

Когда это применяется к $|\psi_3\rangle$, возникает фазовая интерференция (квантовая интерференция).

$$ |\psi_4\rangle = \text{QFT} |\psi_3\rangle = \frac{1}{\sqrt{MQ}} \sum_{y=0}^{Q-1} \sum_{k=0}^{M-1} e^{2\pi i \frac{(x_0 + kr)y}{Q}} |y\rangle $$

Если мы раскроем сумму в этой формуле, появится следующая часть:

$$ \sum_{k=0}^{M-1} e^{2\pi i \frac{kry}{Q}} $$

Сумма этой геометрической прогрессии взаимно усиливается (Конструктивная интерференция, Constructive Interference) только когда $ry/Q$ близко к целому числу, и взаимно уничтожается (Деструктивная интерференция, Destructive Interference) в других случаях.

Следовательно, состояние $|y\rangle$, измеряемое с высокой вероятностью, будет целым числом $y$, удовлетворяющим условию:

$$ \frac{y}{Q} \approx \frac{c}{r} $$

(где $c$ — некоторое целое число).

4.3. Определение периода через разложение в цепную дробь

После получения $y$ в результате измерения используйте классический компьютер для выполнения “разложения в цепную дробь” (Continued Fraction Expansion) $y/Q$. Это позволяет вычислить подходящую дробь $c/r$ для $y/Q$ и с высокой эффективностью извлечь кандидата на период $r$ из знаменателя.

5. Сравнение концептуальных моделей и смена парадигмы

Чтобы интуитивно понять разницу между GNFS и Алгоритмом Шора, приводится концептуальная схема с использованием нотации Mermaid.

Концептуальная схема Алгоритма Шора с использованием квантовой схемы

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
graph TD
    A[Начальное состояние: 0...0] --> B[Суперпозиция всех состояний через преобразование Адамара]
    B --> C[Операция модульного возведения в степень a^x mod N]
    C -->|Квантовая запутанность| D[Коллапс в состояние с периодичностью]
    D --> E[Квантовое преобразование Фурье QFT]
    E -->|Усиление вероятности через интерференцию| F[Измерение: Получение y]
    F --> G[Классическая обработка: Цепная дробь]
    G --> H[Обнаружение периода r]
    H --> I[Вычисление простых множителей N]
    
    style A fill:#f9f,stroke:#333,stroke-width:2px
    style E fill:#bbf,stroke:#333,stroke-width:2px
    style I fill:#bfb,stroke:#333,stroke-width:2px

Суть смены парадигмы

GNFS использует подход “поиска соотношений внутри математического пространства (алгебраического поля)” . Однако, поскольку пространство поиска расширяется экспоненциально относительно количества цифр, расшифровка становится практически невозможной при длине ключа свыше 2048 бит с использованием классических вычислительных мощностей (даже с учетом распараллеливания).

С другой стороны, алгоритм Шора использует “волновую природу квантовой интерференции” . Он оценивает все пути вычислений в состоянии суперпозиции одновременно, подавляет (ослабляет) ненужные ответы с помощью QFT и усиливает только амплитуду вероятности для правильного периода. При этом подход заключается не в поиске в пространстве, а в переходе в совершенно другое измерение: “позволить правильному ответу проявиться самому” .

6. Заключение

В этой статье мы глубоко сравнили математическую основу и структуру алгоритмов между “GNFS” , который является пределом классических вычислений, и “Алгоритмом Шора” , который демонстрирует мощь квантовых вычислений.

В то время как GNFS использует математические ухищрения, такие как выбор многочленов и вычисления с огромными матрицами, чтобы снизить сложность до субэкспоненциального времени, Алгоритм Шора достигает прямого прорыва до полиномиального времени, объединяя базовые принципы квантовой механики (суперпозицию и интерференцию) с математическим инструментом (QFT).

В настоящее время не существует отказоустойчивого квантового компьютера (FTQC) практического масштаба (тысячи кубитов), способного запустить Алгоритм Шора. Однако именно наличие этой теоретической и математической смены парадигмы является главной причиной ускорения глобального перехода к постквантовой криптографии (PQC: Post-Quantum Cryptography) во всем мире уже сегодня.