Алгоритм Шора для ECDLP — Решение для Q-Day Prize

Квантовый решатель задачи дискретного логарифма на эллиптических кривых (ECDLP), созданный для Q-Day Prize Challenge компанией Project Eleven. Цель: восстановить закрытые ключи ECC на реальном квантовом оборудовании с использованием алгоритма Шора.

• Автор: Giancarlo Lelli
• Контакты: [email protected]
• LinkedIn: https://www.linkedin.com/in/giancarlolelli
• О себе: Технологический лидер с более чем 10-летним опытом в корпоративном ПО, полностековой архитектуре и облачной разработке. Образование в области компьютерных наук, практический опыт работы с .NET, Python, Rust и облачными экосистемами. В настоящее время работает специалистом по выходу на рынок в облаке, фокусируясь на архитектуре решений и продажах.

Подход

Все кривые задачи используют y^2 = x^3 + 7 над F_p (a = 0, b = 7), что соответствует семейству secp256k1. Решатель реализует двухрегистровый вариант алгоритма Шора для ECDLP:

1. Подготовить счетные регистры |j>, |k> в равномерной суперпозиции (преобразование Адамара)
2. Вычислить |j>|k>|jG + kQ> с помощью 2t контролируемых сложений точек (t = num_counting qubits)
3. Измерить регистр точек, коллапсируя его в некоторый элемент группы R
4. Применить обратное QFT к счетным регистрам
5. Измерить j, k и извлечь d из соотношения j + kd = r (mod n)

Закрытый ключ d восстанавливается путем сбора нескольких выборок (j, k), удовлетворяющих одному и тому же линейному соотношению по модулю порядка группы n. Решатель поддерживает шесть стратегий оракула для контролируемых сложений точек, которые выбираются автоматически в зависимости от размера кривой или вручную с помощью --oracle.

Стратегии оракула

Стратегия 1: Плотная унитарная (по умолчанию для n_bits <= 6)

Используется для кривых с порядком группы до ~6 бит. Реализована в projecteleven.py.

Каждое контролируемое сложение точек "add S" представляется в виде матрицы перестановок размером 2^(n+1) x 2^(n+1), применяемой через qc.unitary(). Матрица кодирует полное действие группы: верхний левый блок — единичный (control=0), нижний правый блок переставляет базисные состояния согласно отображению P -> P+S (control=1).

• Кодирование: Индекс группы (0..n-1)
• Память: O(2^{2n}) на матрицу
• Кубиты: 2t + n (два счетных регистра + регистр точки)
• Ограничение: Унитарное разложение Qiskit имеет сложность O(4^n), что делает этот подход неприменимым для кривых больше ~6 бит

Стратегия 2: Эффективное разложение перестановок (по умолчанию для n_bits > 6)

Используется для более крупных кривых. Реализована в quantum_arithmetic.py.

Вместо построения плотных матриц каждая перестановка "add S" разлагается на циклы, которые затем превращаются в транспозиции. Каждая транспозиция (обмен двух базисных состояний |a> <-> |b>) реализуется с помощью:

1. CNOT-редукции — CNOT от опорного бита ко всем другим отличающимся битам, сводящие многоразрядное различие к одноразрядному
2. Мультиконтролируемого X — гейт MCX на опорном бите, обусловленный совпадением всех остальных битов с целевым шаблоном
3. Отката CNOT — обратного шага 1 для восстановления неопорных битов

MCX использует V-цепочное разложение с (n-2) выделенными вспомогательными кубитами, что дает O(n) гейтов Тоффоли на один MCX вместо O(n^2) без вспомогательных кубитов. Каждое контролируемое сложение строится как изолированная подсхема и добавляется в виде одного непрозрачного гейта, что позволяет избежать квадратичного роста DAG в Qiskit.

• Кодирование: Индекс группы (0..n-1)
• Память: O(N) на сложение (N = порядок группы)
• Кубиты: 2t + n + (n-2) вспомогательных
• Гейты на сложение: O(N * n)

Стратегия 3: Координатный квантовый оракул (--oracle coordinate)

Доступна для кривых размером до ~6 бит. Реализована в quantum_oracle.py.

Вместо кодирования точек как индексов группы, квантовый регистр хранит фактические (x, y) координаты полярных элементов в двоичном виде плюс флаг тождественности. Разметка регистра точки:

• x_reg: f_bits кубитов (f_bits = ceil(log2(p)))
• y_reg: f_bits кубитов
• id_flag: 1 кубит (1 = точка на бесконечности)

Каждое контролируемое "add S" вычисляется по формуле сложения EC для всех допустимых кодировок координат, порождая перестановку в регистре координат. Эта перестановка разлагается на циклы и транспозиции с использованием той же инфраструктуры CNOT-редукции + MCX, что и Стратегия 2.

• Кодирование: (x, y, id_flag) координаты
• Кубиты: 2t + 2f_bits + 1 + max(0, 2f_bits - 1) вспомогательных
• Гейты на сложение: O(N * f_bits)

Стратегия 4: Арифметический оракул (--oracle arithmetic)

Фреймворк для полиномиально масштабируемого сложения точек. Реализован в quantum_oracle.py и quantum_arithmetic.py.

Использует кодирование координат (аналогично Стратегии 3) с модульными арифметическими примитивами на основе QFT в качестве строительных блоков для полностью арифметического сложения точек. Код включает протестированные реализации:

• Модульного сумматора Борегара — на основе QFT (target + constant) mod p с правильным освобождением вспомогательных кубитов
• Модульного умножения квант-квант — |a>|b>|0> -> |a>|b>|a*b mod p> через shift-and-add с явным модульным удвоением, O(n^3) гейтов
• Перестановки модульной инверсии — |x> -> |x^{-1} mod p> через транспозиции таблицы поиска
• Контролируемого модульного сложения квант-квант — Контролируемое |a> -> |a + b mod p> с редукцией Борегара

Арифметические примитивы обеспечивают масштабирование O(n^3) на сложение точки по сравнению с O(N*n) для подхода с перестановками. Однако операции на основе QFT имеют постоянный множитель примерно в 150 раз больше, что делает арифметический подход эффективным только для кривых с порядком группы выше ~20 бит. Для текущих размеров задач (до 12 бит) сумматор на основе перестановок остается более быстрым и используется по умолчанию.

Стратегия 5: Полуклассическое оценивание фазы от Google (--oracle google)

Реализована в google_semiclassical.py. Вдохновлена техникой оценивания фазы с переработкой кубитов от Griffiths & Niu (1996), примененной в масштабе в Babbush et al. (2026) для оценок ресурсов ECDLP на secp256k1. Статья Babbush et al. была опубликована 30 марта 2026 года.

Заменяет два много-кубитных счетных регистра (j, k) и массовое обратное QFT на два одиночных перерабатываемых кубита и классически обусловленные коррекции фазы. Каждый бит счетного регистра обрабатывается последовательно: подготовка в |+>, применение контролируемого сложения точек, коррекция фазы на основе всех ранее измеренных битов, затем измерение. Примитивы динамических схем reset + if_test в Qiskit позволяют реализовать это на оборудовании IBM Quantum.

Оракул для контролируемых сложений точек делегируется существующей инфраструктуре (плотная унитарная для <= 6 бит, эффективная перестановка для > 6 бит), так что экономия кубитов достигается исключительно за счет устранения счетных регистров.

Размер кривой	Стандартные кубиты	Полуклассические кубиты	Экономия	Проверено на оборудовании
4-бит (n=7)	11	5	55%	Да
6-бит (n=31)	17	7	59%	Да
7-бит (n=79)	26 + anc	14	46%	Да
8-бит (n=139)	25 + anc	10 + anc	60%	Нет (накладные расходы синхронизации QPU)
10-бит (n=547)	31 + anc	12 + anc	61%	Нет (накладные расходы синхронизации QPU)