×

Вы используете устаревший браузер Internet Explorer. Некоторые функции сайта им не поддерживаются.

Рекомендуем установить один из следующих браузеров: Firefox, Opera или Chrome.

Контактная информация

+7-863-218-40-00 доб.200-80
ivdon3@bk.ru

Метод переменной окрестности для задачи факторизации целых чисел в сочетании с байесовским подходом

Аннотация

Огородников Ю.Ю., Плёнкин А.П.

Дата поступления статьи: 20.02.2018

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

Ключевые слова: задача факторизации целых чисел, оптимизационный вариант задачи выполнимости булевых формул (MAX-3SAT), метод переменой окрестности, вещественнозачный фнкционал представления MAX-3SAT, квантовое распределение ключа

05.13.01 - Системный анализ, управление и обработка информации (по отраслям)

05.13.18 - Математическое моделирование, численные методы и комплексы программ

Начиная с № 3 2014 на сайте журнала статьи предоставлены только в PDF и Word Форматах.

Читать статью в формате PDF