Задача о кратчайшем векторе: различия между версиями

Первыми мотивирующими приложениями редукции базиса решетки были решение целочисленных программ с фиксированным числом переменных и факторизация многочленов с рациональными коэффициентами (см. [11], [8] и [5, гл. 16]). Другие классические приложения – решение случайных экземпляров задач о суммировании подмножеств с низкой плотностью, вскрытие (усеченных) линейных конгруэнтных псевдослучайных генераторов, одновременная диофантова аппроксимация и опровержение гипотезы Мертенса (см. [ ] и [5, гл. 17]).

Последний класс приложений задач с решетками – это разработка криптографических функций (например, устойчивых к столкновениям хэш-функций, схем шифрования с открытым ключом и т.д.), основанное на кажущейся неразрешимости задачи решения <math>SVP_\gamma</math> в пределах малых коэффициентов аппроксимации. В [12, глава 8] и [ ] можно найти обзор таких приложений и указатели на соответствующую литературу. Отличительной особенностью многих таких криптографических функций, основанных на решетках, является доказанная сложность их взлома в среднем, основываясь на предположении о неразрешимости в наихудшем случае лежащей в их основе задачи на решетки.