RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Информ. и её примен.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Информ. и её примен., 2019, том 13, выпуск 2, страницы 37–46 (Mi ia591)  

Об одном методе решения систем квадратичных булевых уравнений, использующем локальные аффинности

О. А. Логачевa, А. А. Сукаевb, С. Н. Федоровb

a Институт проблем информатики Федерального исследовательского центра «Информатика и управление» Российской академии наук
b Московский государственный университет имени М. В. Ломоносова

Аннотация: Как известно, вычислительная задача решения систем нелинейных уравнений над полем из двух элементов является NP-трудной. Этим обстоятельством обусловливается стремление исследователей разрабатывать алгоритмы ее решения, минимизирующие необходимые вычислительные ресурсы для тех или иных классов систем уравнений. В статье предлагается метод решения систем квадратичных булевых уравнений, использующий представление функций их аффинными нормальными формами, т. е. в некотором смысле аппроксимацию квадратичных функций кусочно-аффинными. Для каждого уравнения на основе такого представления строится набор систем небольшого числа линейных уравнений, а затем ищется совместная комбинация этих линейных систем для различных исходных уравнений. Исходная нелинейная задача, таким образом, сводится, по большому счету, к проверке совместности серии линейных систем от того же числа переменных. Метод может быть эффективно распараллелен и, несмотря на большую трудоемкость в худшем случае, допускает ряд эвристик, уменьшающих время его выполнения.

Ключевые слова: булева функция, система квадратичных булевых уравнений, разбиение векторного пространства, плоскость, локальная аффинность, аффинная нормальная форма, алгебраический криптоанализ.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 18-29-03124_мк
Работа выполнена при частичной поддержке РФФИ (проект 18-29-03124 мк).


DOI: https://doi.org/10.14357/19922264190206

Полный текст: PDF файл (213 kB)

Реферативные базы данных:

Тип публикации: Статья
Поступила в редакцию: 01.04.2019

Образец цитирования: О. А. Логачев, А. А. Сукаев, С. Н. Федоров, “Об одном методе решения систем квадратичных булевых уравнений, использующем локальные аффинности”, Информ. и её примен., 13:2 (2019), 37–46

Цитирование в формате AMSBIB
\RBibitem{LogSukFed19}
\by О.~А.~Логачев, А.~А.~Сукаев, С.~Н.~Федоров
\paper Об одном методе решения систем квадратичных булевых уравнений, использующем локальные аффинности
\jour Информ. и её примен.
\yr 2019
\vol 13
\issue 2
\pages 37--46
\mathnet{http://mi.mathnet.ru/ia591}
\crossref{https://doi.org/10.14357/19922264190206}
\elib{http://elibrary.ru/item.asp?id=38233327}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/ia591
  • http://mi.mathnet.ru/rus/ia/v13/i2/p37

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Информатика и её применения
    Просмотров:
    Эта страница:12
    Полный текст:5
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019