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

Размер кривой	Стандартные кубиты	Полуклассические кубиты	Экономия	Проверено на оборудовании
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)