Вычислительные методы в дискретной математике

Об алгоритмах LLL-редукции при решении задачи HNP и их сравнительном анализе

В. И. Янов


Аннотация: Исследуется метод решения задачи нахождения скрытого числа (HNP — Hidden Number Problem) путём сведения её к задаче поиска ближайшего вектора. Проводится тестирование различных реализаций алгоритмов LLL- и BKZ-редукции решёток, которые являются основными инструментами для решения задач нахождения кратчайших векторов. Особое внимание уделяется сравнению экспериментальных сложностей двух реализованных алгоритмов: программы fpLLL, основанной на методе P. Q. Nguyen и D. Stehle с квадратичной трудоёмкостью 2009 г., и алгоритма из работы K. Ryan и N. Heninger 2023 г. Это даёт возможность оценить прогресс в области улучшения эффективности и скорости выполнения задачи нахождения скрытых чисел. Ключевую роль в экспериментах играет тщательное отслеживание зависимостей трудоёмкостей алгоритмов по мере роста размерности решётки и её максимального элемента, что позволяет выявить ограничения текущих подходов и предложить области для дальнейшего исследования и улучшения методов решения задачи HNP.

Ключевые слова: LLL-редукция, BKZ-редукция, HNP, fpLLL, алгоритм Ryan — Heninger.

УДК: 511.482

DOI: 10.17223/2226308X/18/61