Квантовый алгоритм решения уравнения нелля с использованием поиска скрытой подгруппы

Abstract

В данной работе рассматривается квантовый алгоритм нахождения минимального решения уравнения Пелля x2-dy2 =1 для заданного п-битного числа d, не являющегося полным квадратом. Используется метод поиска скрытой подгруппы, позволяющий эффективно определять приближенное значение [R], где R = log (x1+y1√d). Проведенные квантовые измерения показали, что наиболее вероятный результат соответствует [R] =0, что позволяет классическими методами вычислить минимальное решение уравнения Пелля. Алгоритм использует разложение √d в цепную дробь, определяет период и вычисляет соответствующую фундаментальную пару (x1, y1). Результаты симуляции на квантовом компьютере подтверждают полиномиальную сложность нахождения R, что существенно превосходит известные классические алгоритмы. Предложенный метод имеет важные криптографические последствия, так как он потенциально угрожает безопасности криптосистем на основе уравнения Пелля, таких как схема Бухмана-Вильямса.