Том 21, номер 2, 2014 г., Стр. 52–58

УДК 519.7
Коломеец Н. А.
Пороговое свойство квадратичных булевых функций

Аннотация:
Пусть f — булева функция от n переменных такая, что для любого аффинного подпространства L размерности én/2ù либо f аффинна на всех сдвигах L, либо не аффинна ни на одном. Доказано, что либо степень f не превосходит 2, либо не существует ни одного аффинного подпространства размерности én/2ù, на котором f аффинна. 
Библиогр. 8.

Ключевые слова: булева функция, квадратичная булева функция, бент-функция.

Коломеец Николай Александрович ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: nkolomeec@gmail.com

Статья поступила 9 июля 2013 г.
Исправленный вариант — 24 декабря 2013 г.

Литература

[1] Коломеец Н. А., Павлов А. В. Свойство бент-функций, находящихся на минимальном расстоянии друг от друга // Прикл. дискрет. математика. - 2009. - №4. - С. 5–20.

[2] Логачев О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии. - М.: МЦНМО, 2004. - 470 с.

[3] Мак-Вильямc Ф. Д., Слоэн Н. А. Теория кодов, исправляющих ошибки. - М.: Радио и связь, 1979. - 744 c.

[4] Токарева Н. Н. Нелинейные булевы функции: бент-функции и их обобщения. - Saarbrucken: LAP LAMBERT Acad. Publ., 2011. - 180 c.

[5] Charpin P. Normal Boolean functions // J. Complexity. - 2004. - Vol. 20. - P. 245–265.

[6] Dobbertin H. Construction of bent functions and balanced Boolean functions with high nonlinearity // Lect. Notes Comput. Sci. - 1994. - Vol. 1008. - P. 61–74.

[7] McFarland R. L. A family of difference sets in non-cyclic groups // J. Combin. Theory. Ser. A. - 1973. - Vol. 15. - P. 1–10.

[8] Rothaus O. On bent functions // J. Combin. Theory. Ser. A. - 1976. - Vol. 20, N3. - P. 300–305.