Алгоритм Шора для 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 бит), так что экономия кубитов достигается исключительно за счет устранения счетных регистров.

• Кодирование: Так же, как в базовой стратегии (индекс группы)
• Кубиты: 2 + n_bits + ancillas (против 2t + n_bits + ancillas)
• Компромисс: Требует динамических схем (измерение в середине схемы, сброс, классически обусловленные гейты). Работает на IBM Heron r2 до 7 бит; на 8 бит+ накладные расходы на синхронизацию классической обратной связи превышают бюджет времени QPU

Стратегия 6: Модульное сложение с ripple-carry (--oracle ripple)

Реализована в ripple_carry_shor.py. Использует сумматоры с ripple-carry CDKM (Cuccaro et al. 2004) для контролируемых сложений точек, заменяя как плотные унитарные матрицы, так и схемы транспозиций с разложением на циклы.

В кодировании индексом группы точка P = kG представляется своим индексом k в циклической группе. Сложение S = sG сводится к модульному сложению классической константы s (mod n). Ключевая идея: каждое контролируемое сложение точек сводится к единственному контролируемому модульному сложению известной константы, реализованному с помощью CDKMRippleCarryAdder и IntegerComparator из Qiskit.

Оракул состоит из 2m контролируемых модульных сложений (m на каждый счетный регистр), где каждое контролируемое mod-add выполняет:

1. Загрузку константы во вспомогательный регистр через CX от управляющего кубита
2. CDKM полусумматор для сложения вспомогательного с аккумулятором (гейты только ближайших соседей)
3. Целочисленный компаратор для обнаружения переполнения (acc >= n)
4. Условное вычитание n с помощью управляемого флагом добавления 2^m1 - n
5. Снятие флага через зондирование на основе переноса

Никакое знание закрытого ключа d не используется при построении схемы. Индексы групп для степеней G вычисляются как 2^i mod n (открытые). Индексы групп для степеней Q получаются из открытого перечисления циклической группы, порожденной G — точка Q находится в этом перечислении.

• Кодирование: Индекс группы (0..n-1)
• Кубиты: 4m + 5, где m = ceil(log2(n))
• Гейты на сложение: O(m) операций CDKM, каждая из которых требует O(m) CX гейтов
• Общее масштабирование CX: O(m^3)
• Отображение на оборудование: CDKM использует только гейты ближайших соседей, что дает ~1x накладных расходов на маршрутизацию на тяжелой гексагональной топологии IBM (против 26-33x для сумматоров на QFT)

Сравнение

QFT арифметические примитивы

Код включает модульные арифметические строительные блоки на основе QFT (сумматоры Борегара/Дрейпера, модульное умножение квант-квант, модульная инверсия/отрицание) как основу для полностью арифметического кодирования координат на 256 бит. Эти примитивы были проверены на корректность с помощью симуляции Statevector для простых чисел до p=13.

Результаты

Успешно восстановлены закрытые ключи на оборудовании IBM Quantum для кривых задач до 17 бит:

Все прогоны выполнялись по плану открытого экземпляра IBM Quantum, который предоставляет 10 минут бесплатных квантовых вычислений в месяц. Полные журналы выполнения находятся в папке executions/.

Стратегия ripple-carry (Стратегия 6) обеспечила значительный скачок: с 10-бит (40 кубитов, 2M гейтов) до 17-бит (69 кубитов, 112K гейтов) — увеличение размера ключа на 7 бит при 18-кратном уменьшении количества двухкубитных гейтов. Структура гейтов ближайших соседей сумматора CDKM эффективно отображается на тяжелую гексагональную топологию IBM, сохраняя накладные расходы на маршрутизацию около 1x.

Полуклассическое PE: Динамические схемы на оборудовании IBM

Полуклассическая стратегия (--oracle google) успешно восстановила ключи на 4-бит, 6-бит и 7-бит с использованием динамических схем (сброс в середине схемы reset, классически обусловленные гейты p через if_test) на процессорах IBM Heron r2. На 7-бит схема использует всего 14 кубитов (против 26 для стандартного подхода с перестановками), создавая сопоставимое количество 2Q гейтов после транспиляции.

На 8-бит и выше полуклассический подход становится непрактичным на текущем оборудовании IBM. Хотя if_else и reset поддерживаются на Heron r2 (подтверждено проверкой целевого бэкенда), каждая точка классической обратной связи требует полной синхронизации QPU — все 156 физических кубитов должны ожидать, пока классический контроллер обработает условие для ~16 активных кубитов. При ~295K гейтов CZ, распределенных по 16+ точкам обратной связи, накладные расходы на выполнение одного выстрела превышают бюджет времени QPU. Стандартный подход с перестановками, который выполняет то же количество гейтов в виде одного непрерывного пакета без динамических схем, успешно завершается в этом масштабе.

Приближенное усечение QFT (параметр max_corrections) сокращает количество блоков if_else с O(n^2) до O(n), сохраняя только ближайшие k коррекций фазы на шаг измерения (углы за пределами k дают вклад < pi/2^{k+1}, что ниже уровня аппаратного шума). При max_corrections=1 8-битная схема содержит 16 блоков if_else — все еще достаточно для тайм-аута на оборудовании IBM при таком количестве гейтов.

Анализ шума и точности

Оценка точности схемы

Предполагая типичную точность двухкубитного (CX) гейта IBM Quantum ~99.5%, оценочная точность схемы падает экспоненциально с количеством гейтов:

Точность схемы вычисляется как F ≈ (0.995)^{CX_count}. Для всего, что превышает 4-бит, расчетная точность астрономически мала — выходное распределение overwhelmingly является шумом.

Почему это всё ещё работает

Для 8-бит и выше каждый выстрел порождает почти уникальную битовую строку (8,128 уникальных исходов из 8,192 выстрелов на 8-бит; все 20,000 уникальны на 16-бит и 17-бит). Выход неотличим от равномерной случайной выборки на уровне битовых строк. Тем не менее, алгоритм всё равно восстанавливает правильный закрытый ключ.

Ключевая идея в том, что пост-обработка Шора устойчива к шуму так, как не устойчив анализ сырых битовых строк. Каждый выстрел дает тройку измерений (j, k, r). Извлечение вычисляет d_cand = (r - j) · k^{-1} mod n и проверяет через d_cand · G == Q. Только истинный d проходит проверку EC, поэтому даже одного правильного кандидата среди тысяч шумовых выстрелов достаточно.

Случайная тройка (j, k, r) дает правильный d_cand с вероятностью ~1/n. При S выстрелах ожидаемое количество подтвержденных попаданий от одного шума составляет ~S/n. На 17-бит (n=65,173, S=20,000) это дает ~0.3 ожидаемых шумовых попаданий — любое успешное восстановление в этом масштабе является свидетельством квантового сигнала, превышающего классический шумовой порог.

Для меньших кривых, где shots >> n (например, 10-бит с n=547 и 1,024 выстрела), шумовой порог составляет ~1,024/547 ≈ 1.9 голоса на кандидата. Даже несколько выстрелов, несущих сигнал, поднимают правильный d выше шумового порога. Это объясняет, как алгоритм достигает успеха, несмотря на точности схем, которые, казалось бы, делают вычисление невозможным.

Квантовый сигнал vs классический шум

На игрушечном масштабе шаг проверки извлечения (d_cand * G == Q) действует как фильтр, принимающий только истинный d. Это означает, что даже полностью случайные тройки (j, k, r) будут давать валидные кандидаты с частотой примерно shots / n за прогон. Когда shots >> n, случайный шум сам по себе может восстановить d с высокой вероятностью.

Чтобы проверить, дает ли квантовая схема сигнал, превышающий этот классический шумовой порог, мы запустили 6-битную задачу (n=31) с всего 8 выстрелами (намного меньше порядка группы) 10 раз на ibm_kingston:

Результат: 4/10 успехов (40%) против классического шумового базового уровня ~20% (вычислено с помощью моделирования Монте-Карло: 8 случайных битовых строк с (r-j)*k_inv mod 31, отфильтрованных через проверку). Односторонний биномиальный тест: P(X >= 4 | n=10, p=0.20) = 0.121, что указывает на двукратное улучшение по сравнению с шумовым порогом. Хотя это не является статистически значимым при p < 0.05 (для этого потребовалось бы 5+ успехов), наблюдаемая частота согласуется с квантовым сигналом, дающим примерно 1-2 дополнительных валидных пары (j, k) за прогон сверх того, что дает случайность.

Этот результат находится между классическим шумовым порогом и областью теоретического квантового преимущества. При больших размерах кривых, где n >> shots, шумовой базовый уровень падает ниже 1%, и любое успешное восстановление ключа становится убедительным свидетельством квантовых вычислений.

Быстрый старт```bash

git clone https://github.com/GiancarloLelli/quantum.git cd quantum

python -m venv . Scripts\Activate.ps1 # For Windows only

pip install -r requirements.txt

### Как запустить

Вам нужна учетная запись [IBM Quantum](https://quantum.ibm.com/). Передайте свой API-токен при первом запуске, и он будет сохранен локально:```bash
# Solve the 4-bit challenge curve:
python projecteleven.py --challenge 4 --token YOUR_IBM_TOKEN --backend ibm_marrakesh

# Subsequent runs (token already saved):
python projecteleven.py --challenge 4 --backend ibm_marrakesh

# Use the coordinate-based quantum oracle:
python projecteleven.py --challenge 4 --oracle coordinate --backend ibm_marrakesh

# Use the arithmetic oracle (coordinate encoding + QFT primitives):
python projecteleven.py --challenge 4 --oracle arithmetic --backend ibm_marrakesh

# Use ripple-carry modular addition (CDKM — best for 8-bit+):
python projecteleven.py --challenge 16 --oracle ripple --backend ibm_fez --shots 20000

# Use Google semiclassical phase estimation (qubit-recycled):
python projecteleven.py --challenge 4 --oracle google --backend ibm_marrakesh

# Use a specific IBM Quantum instance:
python projecteleven.py --challenge 4 --instance ibm-q/open/main --backend ibm_marrakesh

# Verify curve parameters without quantum execution:
python projecteleven.py --curve curve_4 --verify-only

Параметры CLI

Структура проекта```

projecteleven.py # Shor solver — dense unitary approach + CLI entry point quantum_arithmetic.py # Efficient permutation decomposition + QFT arithmetic primitives quantum_oracle.py # Coordinate-based oracle + arithmetic oracle framework google_semiclassical.py # Google semiclassical PE — qubit-recycled phase estimation ripple_carry_shor.py # Ripple-carry modular addition oracle (CDKM) — best for 8-bit+ input_curves.json # Challenge curves (4-bit to 30-bit) problem/curves.py # Curve generation utility requirements.txt # qiskit, qiskit-ibm-runtime

## Ссылки

- P. Shor, ["Алгоритмы для квантовых вычислений: дискретные логарифмы и факторизация"](https://arxiv.org/abs/quant-ph/9508027) (1994)
- S. Beauregard, ["Схема алгоритма Шора с использованием 2n+3 кубитов"](https://arxiv.org/abs/quant-ph/0205095) (2003)
- S. A. Cuccaro, T. G. Draper, S. A. Kutin, D. P. Moulton, ["Новая квантовая схема сложения с переносом"](https://arxiv.org/abs/quant-ph/0410184) (2004)
- M. Roetteler, M. Naehrig, K. Svore, K. Lauter, ["Оценки квантовых ресурсов для вычисления дискретных логарифмов на эллиптических кривых"](https://arxiv.org/abs/1706.06752) (2017)
- R. Griffiths, C.-S. Niu, ["Полуклассическое преобразование Фурье для квантовых вычислений"](https://arxiv.org/abs/quant-ph/9511007) (1996)
- R. Babbush et al., ["Защита криптовалют на эллиптических кривых от квантовых уязвимостей: оценки ресурсов и меры смягчения"](https://quantumai.google/static/site-assets/downloads/cryptocurrency-whitepaper.pdf) (2026)

## Лицензия

Этот проект является заявкой на конкурс Q-Day Prize и распространяется под [лицензией MIT](https://github.com/yuvadm/quantumslop/blob/HEAD/LICENSE)