Алгоритмы для задачи о кратчайшем векторе целочисленной решетки

В данной работе решается задача о векторе целочисленной решетки. В настоящее время существует большое количество алгоритмов способные решить данную проблему. Задача является актуальной из-за того, что она непосредственно связана с криптографией. Решетка – это множество всех целочисленных линейных комбинаций заданной системы векторов. В случае, когда вектора имеют целые координаты, решетка, поражденная ими, называется целочисленной. задача состоит в поиске кратчайшего не нулевого вектора решетки, заданной столбцами А. Для решения этой задачи существует большое количество алгоритмов. Существуют детерминированные, рандомизированные, точные, приблеженные алгоритмы. Самыми известными считаются алгоритмы Кэннона, LLL – алгоритм, а также алгоритм, основанный на свойствах диаграмм Воронова. В большинстве алгоритмов основным параметром от которого зависит сложность, является размерность. Так как задача является NP-трудной, то зависимость сложности от размерности является экспонициальной. Изучению быстродействия алгоритма работы [] и посвящена выпускная работа. Эти исследования помогут лучше понять какие алгоритмы для решения задачи SVP могут применяться в различных ситуациях Данный вопрос является актуальным так как существует большой спектр прикладных задач, например, из сферы криптографии, которые используют решения SVP как важную подзадачу.