КВАНТОВЫЙ АЛГОРИТМ РЕШЕНИЯ УРАВНЕНИЯ ПЕЛЛЯ НА ОСНОВЕ ЗАДАЧИ ПОИСКА СКРЫТОЙ ПОДГРУППЫ
Мухамедиева Д.Т., Раупова М.Х., Тагаев Ф.А.
В данной работе рассматривается квантовый алгоритм нахождения минимального решения уравнения Пелля для заданного n-битного числа , не являющегося полным квадратом. Используется метод поиска скрытой подгруппы, позволяющий эффективно определять приближённое значение , где . Проведённые квантовые измерения показали, что наиболее вероятный результат соответствует , что позволяет классическими методами вычислить минимальное решение уравнения Пелля. Алгоритм использует разложение в цепную дробь, определяет период и вычисляет соответствующую фундаментальную пару . Результаты симуляции на квантовом компьютере подтверждают полиномиальную сложность нахождения R, что существенно превосходит известные классические алгоритмы. Предложенный метод имеет важные криптографические последствия, так как он потенциально угрожает безопасности криптосистем на основе уравнения Пелля, таких как схема Бухмана-Вильямса.
•Dec 13, 2025•0 citations