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

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

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



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






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


Дискрет. матем., 2006, том 18, выпуск 1, страницы 9–29 (Mi dm29)  

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

Приближение булевых функций мономиальными

А. С. Кузьмин, В. Т. Марков, А. А. Нечаев, А. Б. Шишков


Аннотация: Каждая булева функция от $n$ переменных отождествляется с функцией $F\colon Q\to \nobreak P$, где $Q=\mathit{GF}(2^n)$, $P=\mathit{GF}(2)$. Ранее Йоссером и Гонгом для $n=2\lambda$ было установлено существование функций $F$, которые одинаково плохо приближаются не только линейными функциями (функциями $\operatorname{tr}(\mu x)$, где $\mu\in Q^*$ и $\operatorname{tr}\colon Q\to P$ есть функция след), но и собственными мономиальными функциями (функциями $\operatorname{tr}(\mu x^\delta)$, где $(\delta,2^n-1)=1)$). Такие функции $F$ названы гипер-бент-функциями (ГБ-функциями, ГБФ), и описан класс ГБФ со свойством $F(0)=0$, непустой при любом $n=2\lambda$. Это функции вида $F(x)=G(x^{2^\lambda-1})$ такие, что уравнение $F(x)=1$ имеет ровно $(2^\lambda-1)2^{\lambda-1}$ решений в $Q$. В данной работе указаны существенные ограничения на параметры произвольной ГБФ, показывающие, что класс ГБ-функций существенно меньше класса бент-функций. В частности, показано, что любая ГБ-функция есть бент-функция степени нелинейности $\lambda$ и при некоторых $n$ (например, в случае, когда $\lambda>2$, $2^\lambda-1$ – простое число или $\lambda\in\{4,9,25,27\}$) класс ГБ-функций исчерпывается функциями вида $F(x)=G(x^{2^\lambda-1})$, описанными Йоссером и Гонгом. Для $n=4$, кроме 10 ГБ-функций указанного вида, существует еще 18 других ГБ-функций со свойством $F(0)=0$. Вопрос о существовании других гипер-бент-функций при $n>4$ остается открытым.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проекты 05–01–01048 и 05–01–01018, и программой Президента Российской Федерации поддержки ведущих научных школ, гранты НШ 1910.2003.1 и НШ 2358.2003.9.

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

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

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

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

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

Образец цитирования: А. С. Кузьмин, В. Т. Марков, А. А. Нечаев, А. Б. Шишков, “Приближение булевых функций мономиальными”, Дискрет. матем., 18:1 (2006), 9–29; Discrete Math. Appl., 16:1 (2006), 7–28

Цитирование в формате AMSBIB
\RBibitem{KuzMarNec06}
\by А.~С.~Кузьмин, В.~Т.~Марков, А.~А.~Нечаев, А.~Б.~Шишков
\paper Приближение булевых функций мономиальными
\jour Дискрет. матем.
\yr 2006
\vol 18
\issue 1
\pages 9--29
\mathnet{http://mi.mathnet.ru/dm29}
\crossref{https://doi.org/10.4213/dm29}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2254732}
\zmath{https://zbmath.org/?q=an:1103.94035}
\elib{http://elibrary.ru/item.asp?id=9188329}
\transl
\jour Discrete Math. Appl.
\yr 2006
\vol 16
\issue 1
\pages 7--28
\crossref{https://doi.org/10.1515/156939206776241255}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-33744818521}


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

    ОТПРАВИТЬ: 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. Н. Н. Токарева, “Бент-функции с более сильными свойствами нелинейности: $k$-бент-функции”, Дискретн. анализ и исслед. опер., сер. 1, сер. 1, 14:4 (2007), 76–102  mathnet  zmath; J. Appl. Industr. Math., 2:4 (2008), 566–584  crossref
    2. Н. Н. Токарева, “О квадратичных аппроксимациях в блочных шифрах”, Пробл. передачи информ., 44:3 (2008), 105–127  mathnet  mathscinet  zmath; N. N. Tokareva, “On Quadratic Approximations in Block Ciphers”, Problems Inform. Transmission, 44:3 (2008), 266–286  crossref  isi
    3. Charpin P., Gong G., “Hyperbent functions, Kloosterman sums, and Dickson polynomials”, IEEE Trans. Inform. Theory, 54:9 (2008), 4230–4238  crossref  mathscinet  zmath  isi  elib  scopus
    4. А. С. Кузьмин, В. Т. Марков, А. А. Нечаев, В. А. Шишкин, А. Б. Шишков, “Бент-функции и гипербент-функции над полем из $2^l$ элементов”, Пробл. передачи информ., 44:1 (2008), 15–37  mathnet  mathscinet  zmath; A. S. Kuz'min, V. T. Markov, A. A. Nechaev, V. A. Shishkin, A. B. Shishkov, “Bent and Hyper-bent Functions over a Field of $2^l$ Elements”, Problems Inform. Transmission, 44:1 (2008), 12–33  crossref  isi
    5. А. В. Иванов, “Близость к классу мономиальных аппроксимаций приведенного представления булевой функции в зависимости от выбора базиса, в котором оно задано”, ПДМ, 2009, приложение № 1, 7–9  mathnet
    6. Н. Н. Токарева, “Обобщения бент-функций. Обзор работ”, Дискретн. анализ и исслед. опер., 17:1 (2010), 34–64  mathnet  mathscinet  zmath; N. N. Tokareva, “Generalizations of bent functions”, J. Appl. Industr. Math., 5:1 (2011), 110–129  crossref
    7. А. В. Иванов, В. Н. Романов, “Построение классов булевых функций с заданными криптографическими свойствами на основе координатных функций степенных преобразований конечных полей”, ПДМ, 2010, приложение № 3, 10–11  mathnet
    8. А. В. Иванов, “Незамкнутость класса гипер-бент-функций относительно действия полной линейной группы”, Матем. вопр. криптогр., 3:2 (2012), 5–26  mathnet  crossref
    9. А. С. Кузьмин, В. И. Ноздрунов, “Взаимосвязь коэффициентов полинома над полем и веса булевой функции”, ПДМ, 2014, № 4(26), 28–46  mathnet
  • Дискретная математика
    Просмотров:
    Эта страница:824
    Полный текст:305
    Литература:65
    Первая стр.:3

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019