Метод переменной окрестности для задачи факторизации целых чисел в сочетании с байесовским подходом
Аннотация
Дата поступления статьи: 20.02.2018В статье рассматривается приближённый алгоритм поиска решения задачи факторизации целых чисел путём сведения к оптимизационному варианту задачи выполнимости булевых формул, содержащей в каждом дизъюнкте ровно 3 литерала (MAX-3SAT). Для последней задачи строится непрерывный вещественнозначный функционал, глобальный минимум которого совпадает с решением MAX-3SAT. Показано использование метода простой итерации в сочетании с методом переменной окрестности и байесовским округлением. Изложено, что глобального минимума не всегда удаётся достигнуть из-за наличия на траектории поиска локальных экстремумов, однако точки, соответствующие локальным оптимумам, могут быть проанализированы на предмет совпадения отдельных компонент решения с точным. Приведены результаты численных экспериментов, которые показали, что разработанный гибридный метод определяет верно на 7% бит выполняющего набора больше чем предшествующие разработки авторов. Также представленный метод поиска задачи факторизации рассмотрен с позиции защищенности квантовых каналов связи в системах квантового распределения ключа. Описана типовая структура системы квантового распределения ключа.
Ключевые слова: задача факторизации целых чисел, оптимизационный вариант задачи выполнимости булевых формул (MAX-3SAT), метод переменой окрестности, вещественнозачный фнкционал представления MAX-3SAT, квантовое распределение ключа
05.13.01 - Системный анализ, управление и обработка информации (по отраслям)
05.13.18 - Математическое моделирование, численные методы и комплексы программ