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

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

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



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






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


Дискрет. матем., 2006, том 18, выпуск 3, страницы 138–151 (Mi dm66)  

Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)

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

В. В. Баев


Аннотация: Алгебраический метод широко используется при анализе фильтрующих генераторов псевдослучайных последовательностей. Он основан на получении булевых уравнений низкой степени относительно битов начального состояния генератора. Задача получения таких уравнений сводится к поиску обнуляющих множителей (аннигиляторов) низкой степени для фильтрующей булевой функции. Наличие ненулевых низкостепенных аннигиляторов снижает сложность определения начального состояния генератора по его выходной последовательности.
В работе исследуется задача нахождения всех низкостепенных аннигиляторов для булевой функции, заданной в виде многочлена от нескольких переменных. Предлагаются два новых алгоритма решения этой задачи. Их сложности оцениваются сверху полиномами от количества переменных функции и от количества мономов в многочлене, который задает эту функцию. Рассмотрено также применение этих алгоритмов для реализации алгебраического метода по трем известным сценариям, в соответствии с которыми получаются уравнения низкой степени.

DOI: https://doi.org/10.4213/dm66

Полный текст: PDF файл (1313 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Discrete Mathematics and Applications, 2006, 16:5, 439–452

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

УДК: 519.7
Статья поступила: 15.06.2005

Образец цитирования: В. В. Баев, “О некоторых алгоритмах построения аннигиляторов низкой степени для булевых функций”, Дискрет. матем., 18:3 (2006), 138–151; Discrete Math. Appl., 16:5 (2006), 439–452

Цитирование в формате AMSBIB
\RBibitem{Bae06}
\by В.~В.~Баев
\paper О некоторых алгоритмах построения аннигиляторов низкой степени для булевых функций
\jour Дискрет. матем.
\yr 2006
\vol 18
\issue 3
\pages 138--151
\mathnet{http://mi.mathnet.ru/dm66}
\crossref{https://doi.org/10.4213/dm66}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2289328}
\zmath{https://zbmath.org/?q=an:1121.94015}
\elib{http://elibrary.ru/item.asp?id=9311215}
\transl
\jour Discrete Math. Appl.
\yr 2006
\vol 16
\issue 5
\pages 439--452
\crossref{https://doi.org/10.1515/156939206779238427}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-33846864017}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dm66
  • https://doi.org/10.4213/dm66
  • http://mi.mathnet.ru/rus/dm/v18/i3/p138

    ОТПРАВИТЬ: 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

    Эта публикация цитируется в следующих статьяx:
    1. В. В. Баев, “Усовершенствованный алгоритм поиска аннигиляторов низкой степени для многочлена Жегалкина”, Дискрет. матем., 19:4 (2007), 132–138  mathnet  crossref  mathscinet  zmath  elib; V. V. Baev, “An enhanced algorithm to search for low-degree annihilators for a Zhegalkin polynomial”, Discrete Math. Appl., 17:5 (2007), 533–538  crossref
    2. В. В. Баев, “Некоторые нижние оценки на алгебраическую иммунность функций, заданных своими след-формами”, Пробл. передачи информ., 44:3 (2008), 81–104  mathnet  mathscinet; V. V. Bayev, “Some Lower Bounds on the Algebraic Immunity of Functions Given by Their Trace Forms”, Problems Inform. Transmission, 44:3 (2008), 243–265  crossref  isi
    3. Леонтьев В. К., “Булевы полиномы и линейные преобразования”, Докл. РАН, 425:3 (2009), 320–322  mathnet  mathscinet  zmath  elib; Leont'ev V. K., “Boolean polynomials and linear transformations”, Dokl. Math., 79:2 (2009), 216–218  crossref  mathscinet  zmath  isi  scopus
    4. К. Н. Корягин, “Уровневая структура полиномов Жегалкина, свойства тестовых множеств и алгоритм поиска аннигиляторов”, Ж. вычисл. матем. и матем. физ., 50:7 (2010), 1334–1340  mathnet  mathscinet  adsnasa; K. N. Koryagin, “Level structure of Zhegalkin polynomials, properties of test sets, and an annihilator search algorithm”, Comput. Math. Math. Phys., 50:7 (2010), 1267–1273  crossref  isi
  • Дискретная математика
    Просмотров:
    Эта страница:615
    Полный текст:219
    Литература:50
    Первая стр.:5
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020