Алгоритм Шора для ECDLP — Заявка на конкурс Q-Day Prize

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

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

Подход

Все кривые конкурса используют 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(). Матрица кодирует полное групповое действие: верхний левый блок — тождественная матрица (управление=0), нижний правый блок переставляет базисные состояния согласно отображению P -> P+S (управление=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) — вентиль 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 = точка на бесконечности)

Каждое управляемое «добавление S» вычисляется на основе формулы сложения на эллиптической кривой для всех допустимых кодировок координат, создавая перестановку на регистре координат. Эта перестановка разлагается на транспозиции с использованием той же инфраструктуры сокращения 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-ориентированными примитивами модулярной арифметики в качестве строительных блоков для полностью арифметического сложения точек. Код включает проверенные реализации:

• Модулярный сумматор Борегара (Beauregard) — на основе QFT (сложение (цель + константа) mod p) с корректным снятием вспомогательных воздействий
• Квантово-квантовое модулярное умножение — |a>|b>|0> -> |a>|b>|a*b mod p> через сдвиг-и-сложение с явным модулярным удвоением, 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 + вспомогательные (против 2t + n_bits + вспомогательные)
• Компромисс: Требуются динамические схемы (измерения в середине схемы, сброс, классически обусловленные вентили). Работает на IBM Heron r2 до 7 бит; начиная с 8 бит накладные расходы на синхронизацию классической обратной связи превышают временной бюджет QPU

Стратегия 6: Рябь-перенос модулярного сложения (--oracle ripple)

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

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

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

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 heavy-hex (против 26-33x для QFT-сумматоров)

Сравнение

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

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

Результаты

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

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

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

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

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

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

В игрушечном масштабе этап проверки при извлечении (d_cand * G == Q) действует как фильтр, который принимает только истинное d. Это означает, что даже чисто случайные тройки (j, k, r) будут давать правильных кандидатов с частотой примерно выстрелы / n за один запуск. Когда выстрелы >> 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, что указывает на 2-кратное улучшение по сравнению с шумовым порогом. Хотя по отдельности это не является статистически значимым на уровне p < 0.05 (для этого потребовалось бы 5+ успехов), наблюдаемая частота согласуется с квантовым сигналом, обеспечивающим примерно 1-2 дополнительных допустимых пар (j, k) за запуск сверх того, что даёт случайность.

Этот результат находится между классическим шумовым порогом и областью теоретического квантового преимущества. При больших размерах кривых, где n >> выстрелы, шумовой базовый уровень падает ниже 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 token при первом запуске, и он будет сохранен локально:```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

Опции командной строки

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

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 Challenge, выпущенной под [лицензией MIT](https://github.com/giancarlolelli/quantum/blob/HEAD/LICENSE)