zerowang030221/quantum-algorithm-for-elliptic-curve-discrete-logarithms-with-space-efficient-point-additionФреймворк оценки ресурсов на основе Qiskit для пространственно-эффективных квантовых схем модульного инвертирования и аффинного сложения точек, используемых в алгоритмах дискретного логарифмирования на эллиптических кривых.
Этот репозиторий содержит код на Qiskit для оценки ресурсов схем эффективного по пространству квантового модулярного обращения и аффинного сложения точек, используемых в контексте дискретного логарифмирования на эллиптических кривых.
Текущая кодовая база сосредоточена на трёх рабочих процессах:
.
├── README.md
│
├── eea_model/: оригинальная классическая эталонная реализация EEA, используемая для прототипирования алгоритма и проверки корректности.
│
├── run_eea_s835_fastdual_recursive_chunks_checkpoint.py
├── run_eea_s835_fastdual_recursive_chunks_checkpoint_nctopt.py
├── count_s835_fastdual_wrapped_point_addition_blocks_compiled.py
│
├── eea_circuit.py
├── eea_circuit_s835_fastdual.py
├── eea_circuit_s835_lowaux.py
├── eea_circuit_updated.py
├── under1000_eea_shared_s835_fastdual_wrapped.py
├── under1000_modular_arithmetic_base.py
│
├── point_addition_fig14_s835_fastdual_wrapped_quadratic.py
├── quadratic_fig15_inplace_s835_fastdual_wrapped.py
├── quadratic_gidney_arithmetic.py
├── quadratic_lazy_instruction.py
├── quadratic_modular_arithmetic.py
├── quadratic_squ_minus.py
│
├── ccx_recursive_block_counter.py
├── nct_template_segment_optimizer.py
│
├── test_eea_strict_main.py
└── test_point_addition_strict_main.py
run_eea_s835_fastdual_recursive_chunks_checkpoint.py
Подсчитывает шаги EEA Algorithm-3 рекурсивно, с контрольными точками по частям.
run_eea_s835_fastdual_recursive_chunks_checkpoint_nctopt.py
Тот же рабочий процесс подсчёта EEA, но с локальной NCT-шаблонной оптимизацией.
count_s835_fastdual_wrapped_point_addition_blocks_compiled.py
Подсчитывает обёрнутую схему сложения точек путём рекурсивного подсчёта переиспользуемых скомпилированных подблоков и сборки повторяющихся арифметических компонентов с точной кратностью.
eea_circuit_s835_fastdual.py: Основная реализация производственной схемы EEA.eea_circuit_s835_lowaux.py: Вспомогательные процедуры с низким количеством вспомогательных кубитов, используемые основной реализацией.eea_circuit_updated.py: Общие строительные блоки EEA и утилиты рекурсивного подсчёта ресурсов.eea_circuit.py: Обёртка для обратной совместимости для тестов.point_addition_fig14_s835_fastdual_wrapped_quadratic.py: строит обёрнутую схему аффинного сложения точек, соответствующую расписанию Fig.14.quadratic_fig15_inplace_s835_fastdual_wrapped.py: строит структуру Fig.15 для деления и умножения на месте с EEA, умножением, измерением, сбросом и фазовой коррекцией с прямым управлением.quadratic_modular_arithmetic.py: инструкции модульного сложения/вычитания, умножения, обратного умножения, удвоения и деления пополам, используемые счётчиком сложения точек.quadratic_gidney_arithmetic.py: примитивы арифметики в стиле Гидни и помощники для измерения и прямого управления, используемые слоем квадратичной модульной арифметики.quadratic_squ_minus.py: блок square-minus, используемый в расписании аффинного сложения точек.under1000_eea_shared_s835_fastdual_wrapped.py: общая обёртка EEA и помощник, используемые схемой сложения точек.under1000_modular_arithmetic_base.py: небольшие общие утилиты модульной арифметики.ccx_recursive_block_counter.py: рекурсивный счётчик для схем Qiskit с политиками для MCX-расширения и SWAP-расширения.nct_template_segment_optimizer.py: локальный оптимизатор на основе шаблонов для сегментов {X, CX, CCX}.Рекомендуемое окружение:
Установите основную зависимость с помощью:
python -m pip install --upgrade pip
python -m pip install qiskit
Запустите набор тестов:
python test_eea_strict_main.py
python test_point_addition_strict_main.py
Для более быстрой проверки сложения точек (smoke test):
python test_point_addition_strict_main.py --skip-n256 --skip-report
Стандартная точка входа для подсчёта EEA:
python run_eea_s835_fastdual_recursive_chunks_checkpoint.py \
--n 192 \
--chunk-size 25 \
--measurement-uncompute \
--resume \
--workdir eea_s835_fastdual_chunks25 \
--out eea_s835_fastdual_algorithm3_recursive_chunks_n192_measurement.json
Важные аргументы:
--n: разрядность.--T-max: необязательное переопределение количества шагов Algorithm-3; по умолчанию используется значение из eea.get_n_config(n).--chunk-size: количество шагов Algorithm-3, подсчитываемых за одну контрольную часть.--aux-size: необязательное переопределение пула вспомогательных кубитов; если опущено, размер вспомогательной разметки вычисляется автоматически.--measurement-uncompute: включает отмену вычислений на основе измерений в подсчитываемых блоках EEA.--resume: повторно использует существующие непустые JSON-файлы частей в --workdir.--workdir: каталог для файлов контрольных точек каждой части.--out: накопительный JSON-сводка, записываемая после каждой части.Скрипт создаёт файлы для каждой части, например:
eea_s835_fastdual_chunks25/eea_s835_fastdual_n192_T0001_0025.json
и накопительный выходной JSON, содержащий такие поля, как:
mode
n
T_max
num_qubits
len_width
shift_width
aux_size
measurement_based
ops
chunks
elapsed_s_so_far
Точка входа для оптимизированного подсчёта:
python run_eea_s835_fastdual_recursive_chunks_checkpoint_nctopt.py \
--n 128 \
--chunk-size 25 \
--measurement-uncompute \
--templates small-nct \
--rounds 1 \
--max-nct-segment-gates 40 \
--segment-timeout-s 10 \
--timeout-mode auto \
--resume \
--workdir eea_s835_fastdual_chunks_nctopt_failopen_r1_128_seg40_to10 \
--out eea_s835_fastdual_algorithm3_recursive_chunks_n128_measurement_nctopt_failopen_r1_seg40_to10.json
Этот рабочий процесс пытается выполнить локальную шаблонную оптимизацию сегментов {X, CX, CCX}. Он спроектирован как ограниченный счётчик с отказоустойчивостью: если оптимизация шага завершается по таймауту или вызывает исключение, этот шаг подсчитывается точно без шаблонных раундов и затем сохраняется в контрольной точке, так что итоговые подсчитанные значения остаются полными.
Полезные аргументы в дополнение к стандартным аргументам EEA:
--templates {small-nct,all-nct}: выбор библиотеки шаблонов.--rounds: количество раундов шаблонной оптимизации.--max-nct-segment-gates: максимальный размер обратимого сегмента, отправляемого на шаблонную оптимизацию.--max-nct-segment-qubits: максимальное количество кубитов в сегменте.--segment-timeout-s: таймаут для оптимизации отдельного сегмента.--step-timeout-s: таймаут для всего шага Algorithm-3 перед откатом к неизменённому подсчёту.--fallback-step-timeout-s: таймаут для точного запасного подсчёта.--force: пересчитывать, даже если контрольные точки шагов/частей уже существуют.--ignore-policy-mismatch: повторно использовать старые контрольные точки, даже если политика оптимизации отличается; в основном для отладки.Оптимизированный рабочий процесс записывает контрольные точки на уровне шагов в:
<workdir>/steps/
и сводки на уровне частей в:
<workdir>/
Счётчик сложения точек зависит от JSON-файла EEA Algorithm-3, полученного одним из описанных выше рабочих процессов EEA. Значение --n счётчика сложения точек должно совпадать с полем n в JSON EEA.
Пример для n=64:
python run_eea_s835_fastdual_recursive_chunks_checkpoint.py \
--n 64 \
--chunk-size 25 \
--measurement-uncompute \
--resume \
--workdir eea_s835_fastdual_chunks25_n64 \
--out eea_s835_fastdual_algorithm3_recursive_chunks_n64_measurement.json
Затем выполните:
python count_s835_fastdual_wrapped_point_addition_blocks_compiled.py \
--n 64 \
--eea-steps-json eea_s835_fastdual_algorithm3_recursive_chunks_n64_measurement.json \
--out point_addition_s835_fastdual_wrapped_blocks_compiled_counts_n64.json
Пример для оптимизированного вывода EEA n=128:
python count_s835_fastdual_wrapped_point_addition_blocks_compiled.py \
--n 128 \
--eea-steps-json eea_s835_fastdual_algorithm3_recursive_chunks_n128_measurement_nctopt_failopen_r1_seg40_to10.json \
--out point_addition_s835_fastdual_wrapped_blocks_compiled_counts_n128.json
Важные аргументы:
--n: разрядность.--p: модуль; по умолчанию используется простое число secp256k1.--s-qubits: необязательное переопределение размера общего арифметического регистра EEA.--point-constant {secp256k1-generator,zero,custom}: выбор константы точки для обновления постоянной координаты Fig.14.--x2, --y2: пользовательские координаты точки; обязательны при использовании --point-constant custom.--eea-steps-json: JSON-файл, содержащий рекурсивные подсчёты EEA Algorithm-3.--allow-eea-n-mismatch: переопределение только для отладки, позволяющее различать n в JSON EEA и запрошенное --n.--mcx-policy {clean-vchain,keep}: политика расширения MCX для рекурсивного подсчёта.Отчёт о выводе включает:
counting_mode
n
p
point_constant_kind
qiskit_width_report
eea_meta
block_summaries
raw_block_counters
key_ccx
validation
elapsed_s
Счётчик сложения точек строит переиспользуемые схемы Qiskit, рекурсивно подсчитывает их в базисе {CCX, CX, X}, а затем собирает более крупные повторяющиеся блоки, такие как умножение, обратное умножение, деление на месте, умножение на месте, square-minus и общий блок сложения точек Fig.14.
Этот репозиторий включает два простых драйвера тестов на Python. Они намеренно написаны без pytest, Aer или полной симуляции векторов состояний. Тесты рекурсивно раскрывают определения Qiskit, где это уместно, и моделируют состояния вычислительного базиса для тоффоли-сетевых блоков.
Тесты EEA находятся в:
test_eea_strict_main.py
Запустите стандартный набор EEA с помощью:
python test_eea_strict_main.py
Стандартный набор проверяет:
n;3, 5, 7, 11, 13, 17, с использованием как точного подсчёта шагов, так и фиксированного T_max;3, 5, 7.Полезные варианты:
# Только быстрые структурные и блочные тесты.
python test_eea_strict_main.py --skip-endpoint --skip-alg1
# Включить более тяжёлый эталонный тест PDF/Table-4 p=37, x=13.
python test_eea_strict_main.py --table4
# Тестировать все значения x для простых чисел больше 13.
python test_eea_strict_main.py --primes 3 5 7 11 13 17 --mid-all-x --verbose
Тесты сложения точек находятся в:
test_point_addition_strict_main.py
Запустите стандартный набор сложения точек с помощью:
python test_point_addition_strict_main.py
Стандартный набор сложения точек проверяет:
n=256: 835 = 1 + 3*256 + 66;H, measure, reset, классически управляемый Z и swap;Матрица регрессии для больших простых чисел охватывает репрезентативные пары разрядности поля n и простого модуля p в диапазоне от 12-битных до 512-битных простых полей. Тестируемые экземпляры включают, например, n=16, p=65521, n=32, p=4294967291, простое число secp256k1 при n=256 и репрезентативные простые числа при n=128, 160, 192, 224, 384, 512.
Для каждой пары (n,p) тесты включают граничные, симметричные, случайные и относительно длинные трассы EEA. Полная компилированная арифметическая сборка выполняется только для выбранных экземпляров средней ширины, в то время как более крупные пары (n,p) используются для проверки построения схемы, размещения регистров, расписания и путей рекурсивного подсчёта ресурсов.
Полезные варианты:
# Пропустить малый интегрированный отчёт и проверять только построение/расписание/сборку.
python test_point_addition_strict_main.py --skip-report
# Быстрый smoke-тест, который также пропускает проверку построения для n=256.
python test_point_addition_strict_main.py --skip-n256 --skip-report
# Использовать другое малое простое число/ширину для проверки компилированных блоков.
python test_point_addition_strict_main.py --n 5 --p 17
Если Qiskit не установлен, test_point_addition_strict_main.py печатает сообщение о пропуске и завершается успешно. Строгий тест EEA требует Qiskit, поскольку он строит блочные гейты EEA/PDF.
В нашей статье сообщаются численные результаты оценки ресурсов для:
n = 64, 128, 160, 192, 224, 256, 384, 512
Типичный рабочий процесс:
n;n;key_ccx, block_summaries и qiskit_width_report из выходного отчёта.Для больших разрядностей используйте --resume и сохраняйте каталоги --workdir, так как контрольные точки частей и шагов предназначены для поддержки прерванных длинных запусков.
Если вы используете эту кодовую базу в своём исследовании, пожалуйста, цитируйте:
@misc{luo2026quantumalgorithmellipticcurve,
title={Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition},
author={Han Luo and Ziyi Yang and Jingquan Luo and Ziruo Wang and Yuexin Su and Xiaoming Sun and Lvzhou Li and Tongyang Li},
year={2026},
eprint={2607.13816},
archivePrefix={arXiv},
primaryClass={quant-ph},
url={https://arxiv.org/abs/2607.13816},
}
--validate-full-mul: для небольших n рекурсивно подсчитывает полные определения умножения/возведения в квадрат и сравнивает их с собранными блочными подсчётами.--out: путь к выходному JSON.