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

Серов, Александр Александрович

Оценки распределений расстояний от случайной булевой функции до аффинных и квадратичных функций тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

Серов, Александр Александрович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2011 ГОД ЗАЩИТЫ

01.01.05 КОД ВАК РФ

Диссертация по математике на тему «Оценки распределений расстояний от случайной булевой функции до аффинных и квадратичных функций»

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

Учреждение Российской академии наук Математический институт им. В.А.Стеклова РАН

Серов Александр Александрович

ОЦЕНКИ РАСПРЕДЕЛЕНИЙ РАССТОЯНИЙ ОТ СЛУЧАЙНОЙ БУЛЕВОЙ ФУНКЦИИ ДО АФФИННЫХ И КВАДРАТИЧНЫХ ФУНКЦИЙ

01.01.05 — теория вероятностей и математическая статистика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 2 МАЙ 2011

Москва 2011

4845231

Работа выполнена в Учреждении Российской академии наук Математическом институте им. В. А. Стеклова РАН.

Научный руководитель:

Официальные оппоненты:

доктор физико-математических наук A.M. Зубков

доктор физико-математических наук, профессор Г. И. Ивченко

кандидат физико-математических наук, доцент С. И. Чечёта

Ведущая организация:

Механико-математический факультет Московского государственного университета им. М. В. Ломоносова

Защита диссертации состоится 12 мая 2011 года в 14 часов на заседании диссертационного совета Д 002.022.01 в МИАН но адресу: 119991, г. Москва, ул. Губкина, д. 8.

С диссертацией можно ознакомиться в библиотеке МИАН. Автореферат разослан У апреля 2011 года.

Ученый секретарь диссертационного

совета Д 002.022.01 в МИАН Ср^-'-р'

доктор физико-математических наук В. А. Ватутин

Общая характеристика работы

Актуальность темы

Понятие булевой функции сформировалось во второй половине XIX века в работах одного из основоположников математической логики английского математика Джорджа Буля (G. Boole, 1815-1864). В первой половине XX века булевы функции приобрели фундаментальное значение для оснований математики. Вместе с тем длительное время булевы функции оставались невостребованными в прикладных областях.

Существенные изменения произошли в середине XX века, когда бурное развитие техники связи, приборостроения и вычислительной техники потребовало создания адекватного математического аппарата. В этот период происходит становление таких прикладных отраслей математики, как теория конечных функциональных систем, теория информации, теория кодирования и, наконец, теоретическая криптография.

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

Как известно из практики математических исследований, линейность (в математическом смысле) изучаемого объекта упрощает его исследование. Линейность с успехом используется в алгебре, теории систем, математической кибернетике и других разделах математики. С другой стороны, для построения надёжных криптографических систем важна как раз нелинейность, а существование свойств, близких к свойствам линейных функций, считается слабостью. Наличие таких свойств противоречит фундаментальным принципам построения криптографических систем.

Одной из мер нелинейности булевой функции / является величина JV/, численно равная расстоянию (в метрике Хэмминга) от данной функции до множества аффинных функций А„.

С точки зрения теории кодирования множество аффинных функций представляет собой код Рида-Маллера первого порядка RM(l,n), а значение Nj является верхней границей для радиуса покрытия кода

ДМ(1,п) (см. Ф. Дж. Мак-Вильямс, Н. Дж. Слоэн1). В случае четного п значение в точности совпадает с радиусом покрытия кода ЯМ(1,п). При нечетном п точное значение радиуса покрытия кода ДМ( 1, п) известно лишь для некоторых значений п, а в остальных случаях имеются только его нижние и верхние оценки.

По аналогии с нелинейностью булевой функции / как расстояния до множества аффинных функций можно рассматривать также расстояние от / до множества булевых функций, представимых в виде многочленов второй степени (квадратичных функций).

В настоящей работе получены двусторонние оценки и асимптотические формулы для количеств булевых функций от п переменных, которые с заданной точностью аппроксимируются линейными, аффинными или квадратичными булевыми функциями. Используя термины теории вероятностей, можно сказать, что эти результаты описывают распределение расстояния от случайной равновероятной булевой функции до линейных, аффинных и квадратичных функций в области вероятностей больших уклонений. Доказана предельная теорема для расстояния Хемминга между случайной равновероятной булевой функцией от п переменных и множеством аффинных булевых функций от тех же переменных, дополняющая аналогичную теорему Б.В. Рязанова для расстояния до множества линейных булевых функций.

Цель работы

Цели работы:

— исследование предельного распределения расстояния Хемминга между случайной равновероятной булевой функцией от п переменных и множеством аффинных булевых функций,

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

1 Мак-Вильямс Ф.Дж., Слоэп Н.Дж.А. Теория кодов исправляющих ошибки. — М.: Снязь, 1979.

Научная новизна

Все полученные результаты являются новыми. Основные результаты работы состоят в следующем.

1. Доказана предельная теорема для расстояния Хемминга от случайной равновероятной булевой функции до множества аффинных булевых функций от п переменных.

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

Методы исследования

В диссертации используются методы теории вероятностей и перечислительной комбинаторики.

Теоретическая и практическая ценность

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

Апробация работы

Результаты диссертации докладывались на семинарах Отдела дискретной математики Математического института им. В. А. Стеклова РАН (г. Москва, 2007-2010 гг.), X Всероссийском Симпозиуме по прикладной и промышленной математике (г. Санкт-Петербург, 2009 г.), X Международном семинаре «Дискретная математика и её приложения» (г. Москва, 2010 г.), 9-й Международной конференции по компьютерному анализу данных и моделированию (г. Минск, 2010 г.).

Публикации

Основные результаты диссертации опубликованы в 5 работах, список которых приведён в конце автореферата [1-5].

Структура диссертации

Диссертация состоит из введения, четырёх глав и списка литературы. Общий объём диссертации составляет 87 страниц. Список литературы включает 18 наименований.

Краткое содержание диссертации

Во введении приведён краткий исторический обзор по тематике работы, изложены цели исследования, а также перечислены основные полученные результаты.

В первой главе диссертации доказывается предельная теорема для расстояния Хемминга между случайной равновероятной булевой функцией от п переменных и множеством аффинных булевых функций от тех же переменных, дополняющая аналогичную теорему Б.В. Рязанова для расстояния до множества линейных булевых функций.

Перейдём к более подробному изложению результатов главы 1. Пусть F2 - поле из двух элементов. Для произвольного натурального числа п будем обозначать через Vn = F2 пространство n-мерных векторов с компонентами из F2. Между множеством F^n = {/: Vn —» F2} всех булевых функций от п переменных и пространством V2n можно установить взаимно однозначное соответствие, отождествляя функцию / € F5j" с вектором

№)l xevn}.

Расстояние Хэмминга р (/, д) между булевыми функциями /, д G F^"

определяется как число значений переменной х € Vn, при которых fix) ^

д[х). Для произвольного множества булевых функций А С F^" и функции

/ 6 FJf" обозначим через p(f,A) = min p{f,g) расстояние Хэмминга от /

дел

до ближайшей к ней функции из множества А.

В множестве ¥2п всех булевых функций естественно выделяются: класс линейных функций

Ьц = {/ е К" /(х 1) • • ■. хп) = 0-1X1 ® ... ® апхп, аи...,ап 6 Р2} , класс аффинных функций

А„ = {/ € : /(хь ...,хп) = а0 ® 01X1 ® ... ® апхп, аа,..., ап 6 Е2} и класс квадратичных функций

Qn = {/ € : /(хь ..., хп) = (£) Ъцх{х^ ®ф едфа0, сц€¥2},

г=1

где © — сложение в Гг; очевидно, Ъп С А„ С (}п. Мощности этих классов имеют следующий вид:

11^1 = 2", | Ап| = 2'г+1 и =

Предельные теоремы для распределения расстояния между случайной булевой функцией и множеством линейных булевых функций доказаны в работе Б.В. Рязанова2. В частности, было показано, что если /.,.£ ¥2п -случайная булева функция, имеющая равномерное распределение на то

Цш Р / ^'У ~ < Л = 1 - е-1 ух е К, (1)

где

ап = 2 — 2 2 \/гИп2 --= (2)

В совместной работе Б.В. Рязанова и С.И. Чечёты3 доказаны предельные теоремы для распределения расстояния от случайной булевой функции до множества квадратичных булевых форм со свободным членом. В частности, показано, что для любого фиксированного х

2Ryasanov В. V. Probabilistic methods in the theory of approximation of discrete functions. — Probab. Meth. Discr. Math., Proc. 3rd Int. Petrozavodsk Conf., TVP/VSP, Moscow, 1993, pp. 403-412.

3Рязанов Б.В., Чечёта С.И. О приближении случайной булевой функции множеством квадратичных форм. — Дискретная математика., 1995, т. 7, № 3, с. 129-145.

Пш Р

П—»00

У - К

^ х \ = 1 - е"е ,

где

К = 2"

, п-2 ,— Г 1 41п (тт21п 2) — 1п 21 + ----1

(3)

2^ плДп2

(4)

В главе 1 диссертации содержится доказательство теоремы, дополняющей результаты работы Б.В. Рязанова.

Теорема 1. Если / € - случайная булева функция, имеющая

■К

равномерное распределение на РЗГ", то для любого фиксированного х 6

НшР^'^ а" ^х-\п2\ = 1-е-е', (5)

где ап и Ьп определены в (2).

(Нумерация теорем, следствий и утверждений в автореферате отличается от их нумерации в тексте диссертации.)

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

Рассмотрим произвольный линейный код С длины п с минимальным расстоянием (I = ^гшп и п — к проверочными символами. В таком

коде имеется 2к кодовых слов.

Представим, как и в книге Р. Блейхута4, окрестности кодовых слов в виде шаров целочисленного радиуса г. Если при г = а, а 6 Ъ, шары не пересекаются, а при г — а + 1 пересекаются, то а называется радиусом сферической упаковки кода. Минимальное значение Ь радиуса г, при котором каждая точка Уп попадает в 6-окрестность хотя бы одного кодового слова, называется радиусом покрытия кода.

4Блейхут Р. Теория и практика кодов, контролирующих ошибки. — М.: Мир, 1980.

Нахождение количеств векторов v £ Vn, попадающих в г-окрестность кода С, представляет практический интерес, причём при г ^ а и г ^ b справедливы тривиальные формулы, а в общем случае соответствующие точные формулы весьма сложны. В главе 2 для этих величин в случае а < г < b получены двусторонние неравенства в терминах весового спектра кода.

Пространство Vn можно представить в виде объединения слоев Vn(i) = {х € Vn: wt(x) = г}, т. е.

vn = {Jvn(i).

г=О

Введём обозначение

Nj?\i,r) =f |{х G Vn: max{dist (х1,0), dist (х, с)} < г, wt(c) = г}|.

При фиксированном значении г правая часть не зависит от вектора с, wt(c) = г, так как любой вектор веса г можно перевести в любой другой вектор такого же веса перенумерацией координат, которая не изменяет веса векторов и расстояние Хэмминга между ними.

Теорема 2. Если известен весовой спектр кода С, т.е. мощности множеств кодовых слов веса г

Щ = К,(г) ПС, г 6 {0,1,...,п},

то справедливы оценки для чисел элементов множеств г) = {v £ Vn: dist(-u,C) ^ г} при т ^ п

(1 - q(n,r))2k ¿С < |F2(C,г)I < 2С?,

m=0 m=О

где g(n,r) = i £ (г, г)/ £ С™.

г—1 т=0

Оценки теоремы 2 справедливы для более широкого класса кодов: достаточно потребовать, чтобы совокупность расстояний от кодового слова до всех остальных кодовых слов была одной и той же для всех кодовых слов.

Ряд явных двусторонних оценок для А4 (г) = С™ и Д^г (г, г)

т=0

получены в следующих трёх утверждениях.

Утверждение 1. При г ^ п/2 справедливы оценки 2»Ф ^ ¿С™ ^ 2'1Ф

_^_fi ___!__)< Ус-<

гг(п-г)п~г^2ттУ (I - |) V ito "

п11

<-:-, = ,

(г + l)r+!(n - г - I)«-»—1 Л2тгп1/ (l - М)

где Ф(-) — функция стандартного нормального распределения, V(z) = (l-z) ln(l - z) + (1 + z) ln(l + z).

Утверждение 2. Если 0 ^ r ^ [n/2], то

+ где 9 =

?n=0

- < где 0 < k < n.

Утверждение 3. Если 0 < г < [n/2] и 0 < k ^ n, то

< Cf2 ^^ дря Чётном Л,

< при нечётом к,

где qk = n_[fc/2]-r+i < <? = n-r+i •

В третьей и четвёртой главах приводятся основные результаты диссертации: формулы и двусторонние оценки для чисел элементов множеств

¥2(ЬП>Г) = {1 рИ^п)^ г},

¥2{Ап,г) = {/е¥^:р(/,Ап)<г}, ¥2((}п,г) = Р(тп) ^г}

всех булевых функций от п переменных, расстояния от которых до множеств линейных аффинных АП) квадратичных (Ц^ функций соответственно меньше или равны г. Известно5, что Р2(А„,г) = Р^", если г ^ 2П_1 - 2"/2-1.

В частности, из результатов работы Б.В. Рязанова2 следует, что если 1^2(1ЬП, г) — множество всех булевых функций, расстояние Хемминга от которых до множества линейных функций (аффинных с нулевым свободным членом) не превосходит г, то при п —> оо

sup

2-2"|F2(LIt,r)|-(l-e-^("'r)) где х(п, г) определяется равенством

О, (6)

г = 2"-1 - ^2'1-1 (п 1п2 - * 1п(4тгп 1п2) + х{п, г)).

Это означает, что для основной массы булевых функций от п переменных расстояние до множества линейных функций при п —> оо имеет вид

Г'1 - ^2»"1 (п 1п 2 — \ 1пга) + О (^2^) .

Сравнение (1) и (5) показывает степень увеличения окрестности множества А„ аффинных функций по сравнению с окрестностью множества 1Ь„ линейных функций.

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

Основным результатом главы 3 является следующее утверждение. Теорема 3. Если п ^ 2, то

г г

(1 - д(п, г))2"+1 £ С2т„ < I Р2(А„, г)| < 2"+1 £

ш=0 т—0

(1 - i Q(n, г)) 2" | F2(Ln, г)| ^ 2" £

771=0 777=0

71-2

где (¿(п, г) = 0 при 0 ^ г < 2

, 1 /2(с2п)3/2

С?(п,г)<—2 ^

при = 2"-1 - сг\/2п~1п 1п 2 ^ 0, сг > 1.

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

Отношения верхних и нижних оценок в теореме 3 стремятся к 1, если п -> оо и г < 2П~1 - с \/2п-1п 1п2, с > /¡75 = 1,2247...

С помощью утверждения 1 показано, что в области «больших уклонений» (где 1 — е~е —> 0) относительная погрешность

приближения величины 2~2П|Р2(Ь,г,г)| величиной 1 — е~е быстро растет с уменьшением г.

Следствие 1. Если с > 1 и п,г —> оо так, что выполняется условие г < 2П~1 — су2п~1п\п2, то при достаточно больших п

|Р2(Ьп,г)| <1107

22" (1 -

Из результатов работы Б.В. Рязанова и С.И. Чечёты0 (см. формулу (3)) следует, что если F2(Qn, г) — множество всех булевых функций, расстояние Хемминга от которых до множества квадратичных функций не превосходит г, то при п —> оо

sup 2-2n|F2(Qn,r)|-(l-e"e""xM) 0, (7)

0<r<2n-J -2"/2"1 Vhi2 4 '

сРязанов Б.В., Чечета С.И. О приближении случайной булевой функции множеством квадратичных форм. — Дискретная математика., 1995, т. 7, К2 3, с. 129-145.

где х(п, г) определяется равенством

г = 2"-1 -22'1 ^п21п2 + п 1п 2 - 21пп - 1п(тг 1п 2) + 1п л/2 + 2х(п, г). (8)

Это означает, что для основной массы булевых функций от п переменных расстояние до множества квадратичных функций при п —> оо имеет вид

2'1-1 - V2'1"2(п21п2 + п1п2-21пп) + О (2п/2/п) .

Основным результатом главы 4 является следующее утверждение. Теорема 4. Если п ^ 3, то

г г

(1 - <3(п, г))2®5+п+1 £ ^ I г)| ^ 2<»+п+1 £ С

т=0 т=0

где (2(п, г) — 0 при 0 ^ г < 2""3,

при п ^ 15 л г = 2П_1 - Сгп\/2"-21п2 > 0, сг > 1.

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

Отношения верхних и нижних оценок в теореме 4 стремятся к 1, если п -> оо и г < 2"-1 - сп\/2"~21п2, с > л/3 = 1,7321...

С помощью утверждения 1 показано, что в области «больших уклонений» (где 1 — е~е 1("'г) —> 0) относительная погрешность приближения величины 2_2"|Р2(<0)11,г)| величиной 1 — е~е хМ быстро растет с уменьшением г.

Следствие 2. Если с > \ а п,г —> оо так, что выполняется условие г < 2"~1 — с у/2п~2(тг2 + п) 1п 2, то при достаточно больших п

|р2(<а„,г)| < 1,5

22" (1 - е-6-""'"') с

Автор выражает глубокую благодарность своему научному руководителю д.ф.-м.н. А. М. Зубкову за постановку интересных задач, постоянное внимание к работе и критические замечания.

Работы автора по теме диссертации

[1] Зубков A.M., Серов А.А. Оценки числа булевых функций, имеющих аффинные приближения заданной точности. — Дискреты. матем., 2010, т. 22, №4, с. 3-19.

[2] Серов А.А. Предельное распределение расстояния между случайной булевой функцией и множеством аффинных функций. — Теория вероятн. и её иримен., 2010, т. 55, №4, с. 791-795.

[3] Зубков A.M., Серов А.А. Оценки числа булевых функций, имеющих аффинные приближения заданной точности. — Обозрение прикладной и промышленной математики, 2009, т. 16, вып. 2, с. 337-339.

[4] Зубков A.M., Серов А.А. Оценки числа булевых функций, имеющих аффинные приближения заданной точности. — Материалы X Международного семинара «Дискретная математика и её приложения» (Москва, МГУ, 1-6 февраля 2010 г.). М.: Изд-во механико-математического факультета МГУ, 2010, с. 230-232.

[5] Serov A.A., Zubkov A.M. On the number of Boolean functions in a given neighbourhood of the affine functions set. — Computer Data Analysis and Modeling: Complex Sthohastic Data and Systems: Proc. of the 9th Intern. Conf., Minsk, Sept. 7-11, 2010. Vol. 2, p. 67-70.

Заказ № 130-А/03/2011 Подписано в печать 18.03.2010 Тираж 100 экз. Усл. пл. 0,6

4:л;-:;-:\ ООО "Цифровичок", тел. (495) 649-83-30

\ }) www.cfr.ru; e-mail:info@cfr.ru

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Серов, Александр Александрович

Введение.

1 Предельное распределение расстояния между случайной булевой функцией и множеством аффинных функций

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

2.1 Оценки окрестностей линейных кодов

2.2 Оценки для сумм с биномиальными коэффициентами.

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

3.1 Неравенства включения-исключения.

3.2 Упрощенные оценки числа булевых функций

3.3 Верхняя оценка

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

4.1 Неравенства включения-исключения.

4.2 Упрощенные оценки числа булевых функций

Введение диссертация по математике, на тему "Оценки распределений расстояний от случайной булевой функции до аффинных и квадратичных функций"

Как известно из практики математических исследований, линейность (в математическом смысле) изучаемого объекта упрощает его исследование. Линейность с успехом используется в алгебре, теории систем, математической кибернетике и других разделах математики. С другой стороны, для построения надёжных криптографических систем валена как раз нелинейность, а существование свойств, близких к свойствам линейных функций, считается слабостью. Наличие таких свойств противоречит фундаментальным принципам построения криптографических систем.

Одной из мер нелинейности булевой функции f является величина ТУ/, численно равная расстоянию (в метрике Хэмминга) от данной функции до множества аффинных функций ап.

С точки зрения теории кодирования множество аффинных функций представляет собой код Рида-Маллера первого порядка ЯМ( 1, п), а значение Nf является верхней границей для радиуса покрытия кода ЯМ(1,п) (см. [9]). В случае четного п значение ./V/ в точности совпадает с радиусом покрытия кода ЯМ( 1, п). При нечётном п точное значение радиуса покрытия кода ЙМ(1,тг) известно лишь для некоторых значений п,ав остальных случаях имеются только его нижние и верхние оценки.

По аналогии с нелинейностью булевой функции / как расстояния до множества аффинных функций можно рассматривать также расстояние от / до множества булевых функций, пред ставимых в виде многочленов второй степени (квадратичных функций).

Перейдём к более подробному изложению результатов диссертации.

Пусть F2 - поле из двух элементов. Для произвольного натурального числа п будем обозначать через Уп = Е2 пространство п-мерных векторов с компонентами из ¥2. Между множеством = {/ : Уп —► ¥2} всех булевых функций от п переменных и пространством У2п можно установить взаимно однозначное соответствие, отождествляя функцию / Е ¥\п с вектором {/(ж)| х Е Уп}

Расстояние Хэмминга р (/, д) между булевыми функциями f1gE определяется как число значений переменной х Е Уп, при которых /(гг) Ф 9(х)- Для произвольного множества булевых функций А С и функции / Е обозначим через р(/, А) = ттр^,д) дел расстояние Хэмминга от / до ближайшей к ней функции из множества А.

В множестве ¥\п всех булевых функций естественно выделяются: класс линейных функций ахх\ ф . 0 апХп, аь ., ап Е F2} , класс аффинных функций а0 0 а\х 1 0 . 0 апхп, а0,., G F2} и класс квадратичных функций п ф bijXiXj 0 (J) 0 а0, bij, ai <Е F2 } , 1 где 0 — сложение в F2; очевидно, Ln С Ап С Qn. Мощности этих классов имеют следующий вид: L„| =2", | An| = 2n+1 и | Q„| = 2(")+n+1.

Основными результатами диссертации являются точные формулы и двусторонние оценки для чисел элементов множеств

F2(L„,r) = {/eF[»:p(/,LJ ^ г},

F2(An,r) = {/ е p(J, К) < г}, F2(Qn, г) = {/ € F^» : Q„) s? г} всех булевых функций от п переменных, расстояния от которых до множеств Ln, АП} Qn соответственно меньше или равны г. Известно [9], что F2(An,r) = F^n, если г ^ 2^-12^/2—1

При четном п функции, расстояние от которых до множества аффинных функций равно 2п~1 — 2П/2-1, называются бейт-функциями или максимально-нелинейными функциями. Они, в частности, представляют интерес для построения криптографических алгоритмов, стойких по отношению к методам, основанным на аппроксимации булевых функций линейными (см., например, [2], [8]). Однако даже асимптотика числа бент-функций до сих пор неизвестна.

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

Предельные теоремы для распределения расстояния между случайной булевой функцией и множеством линейных булевых функций доказаны в [5]. В частности, было показано, что если / 6 - случайная булева функция, имеющая равномерное распределение на то lim Р < Л = 1 - ух е К, (1)

П-+СО | Ъп где

П1 —( 1п 1x12п + 1п47г\ а" = 2 - ^ --ШЫ2-) '

Ъп = (2)

В [10] доказаны предельные теоремы для распределения расстояния от случайной булевой функции до множества квадратичных булевых форм со свободным членом. В частности, в [10] показано, что для любого фиксированного х оо вп где п2 — Г 1 41п(тгп21п2)-1п2

Л. = 2 - |1 + --пу1п2

В главе 1 диссертации содержится доказательство теоремы, дополняющей результаты работ [5] и [10].

Теорема 1. Если / 6 - случайная булева функция, имеющая равномерное распределение на , то для любого фиксированного х Е К.

Цтр М,К)~ап<хыЛ= (5)

П-* оо I Оп ) где ап и Ъп определены в (2).

В частности, из результатов работы [5] следует, что если Е2(Ьп,г) — множество всех булевых функций, расстояние Хемминга от которых до множества линейных функций (аффинных с нулевым свободным членом) не превосходит г, то при п —> оо эир

0^г<2п—1 —2П/2-1 где х(п,г) определяется равенством г = 2п~1 - ^2п~1 (п Ь 2 - | 1п(4тггг 1п 2) + х(п, г)).

Это означает, что для основной массы булевых функций от п переменных расстояние до множества линейных функций при п —► оо имеет вид

2п~1 - yj2п~1 (rcln2-§ Inn) +0 (v7^?^)

Сравнение (1) и (5) показывает степень увеличения окрестности множества Ап аффинных функций по сравнению с окрестностью множества Ln линейных функций.

Основным результатом главы 3 (объединение части формулировок теорем 8, 9, 10 и утверждений 3, 4) является следующие утверждение.

Теорема 2. Если п ^ 2, то г г

1 - Q(n, r))2n+1 F2(An, r)| < 2™+1C?n,

771=0 771=0

Г Г

1 - \ Q(n, r)) 2" s? | F2(Ln, r)K 2"

772=0 m= 0 где Q(n, r) = О при 0 ^ r < 2n2; 4 1 o-icMV p^n)3/2)

Q(n,r)<-2 ^ ^exp|-^-| npun^8,r = 2й-1 - cr\/2n-1nln2 ^ 0, cv > 1.

Замечание 1. Неравенства теоремы 2 позволяют получать оценки для левого хвоста распределения расстояния от случайной булевой функции до множеств аффинных и линейных булевых функций.

Отношения верхних и нижних оценок в теореме 2 стремятся к 1, если га —> оо и г < 2п~1 — су/2п~1п\п2, с > л/ЦЪ = 1,2247. г

Для сумм при г ^ 27г~1 в главе 2 получены т=О явные верхние и нижние оценки. С их помощью, например, показано, что в области «больших уклонений» (где 1 —

7*) е~е ' —> 0) относительная погрешность приближения м 77* к г у* 1 величины 2-"1 |Р2(Ьп,г)| величиной 1 — е~е ' быстро растет с уменьшением г.

Следствие 1. Если с > 1 и п,г —> оо так, что выполняется условие г < 2п~1 — сл/2п~1п1п2, то при достаточно больших га

22П \ — С

Из результатов работы [10] (см. формулу (3)) следует, что если F2(QTг,r) — множество всех булевых функций, расстояние Хемминга от которых до множества квадратичных функций не превосходит г, то при га —► оо вир

0<Г<2п-1-2"/2-1\/Ь2

2"2>2(Отг)| - (1

7) где ж (га, г) определяется равенством г- 2п~1-2?-1х х ^/га21п 2 + га 1п 2 — 21п га — 1п(тг1п2) + Ь <У2 + 2х(п, г). ю

2п~1 - л/2"-2 (п21п 2 + п 1п 2 - 21п п) + О ¡2п/2/п) .

Основным результатом главы 4 (объединение части формулировок теорем 13, 14 и утверждения 5) является следующее утверждение.

Теорема 3. Если п ^ 3; то г г

1 - <Э(п, г))2®+п+1 < I г)I < 2(?)+"+1 Е т=О ш=О где (Э(гг, г) = 0 при О ^ г < 2п~г,

2-^(с2З)/6+п+1 Г (сгП)3 1

ХП>Г)<—^—ехр\7^/ прип^1Ъиг = 2п~1 - СгПл/ 2п~21п 2 > 0, о- > 1.

Замечание 2. Теорема 3 позволяет получать оценки левого хвоста распределения расстояния от случайной булевой функции до множества квадратичных булевых функций.

Отношения верхних и нижних оценок в теореме 3 стремятся к 1, если п -> оо и г < 2п~1 — сп\/2п~21п2, с > л/3 = 1,7321.

С помощью верхних и нижних оценок для сумм г при г < 2п~1 показано, что в области «больших т=О уклонений» (где 1 — е~е ' —> 0) относительная погрешность приближения величины 22Гг|Е2(Оп, г)| г) величиной 1 — е~е ' быстро растет с уменьшением г.

Следствие 2. Если с > 1 и п, г —► оо так, что выполняется условие г < 2П1 — с д/2П~2 (п2 + га) 1п 2, то при достаточно больших п

2(0», г) I 1^5

22п

В качестве упрощенных следствий результаты глав 1, 2, 3 и 4 можно записать в следующей форме.

Утверждение 1. Если га достаточно большое и г >

1п (4тгп 1п 2)

2п > 7710 р .РЫК)-** п

С1 е--*Л л х I („ 1п (4тгп1п2)\ \ ) '

1 +

21п2 ^ 2 п ) о , рЦЛп) -ап Р < -Т1- < — 1п 2 > < а

Л е-е-»Л

1 .1 / 1п (47Г711п 2) \ у /'

1 21п2 2п ) 1п (тгп2 1п 2) если г > к 2п2—¿; то р . р{1,о») - к гп2 п

1,5 / гп2' ~

1 . 1 (у 1п (7ГП2 1п 2) Л

1 ^ 1п2 2п2 у где ап, Ьп, Нп, 5П определены в (2) и (4).

1 - е~е у ,

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Серов, Александр Александрович, Москва

1. Alfers D., Dinges H. A normal approximation for Beta and Gamma tail probabilities. — Z. Wahrscheinlichkeitstheorie verw. Gebiete, 1984, no. 65, pp. 399-420.

2. Carlet C. Boolean functions for cryptography and error correcting codes, 2006. http://www-rocq.inria.fr/codes/Claude.Carlet/chap-fcts-Bool.pdf

3. Cusick T.W., Stanica P. Cryptographic Boolean Functions and Applications. — Elsevier, 2009.

4. McDiarmid Colin. Concentration. — Probabilistic Methods for Algorithmic Discrete Mathematics, 1998.

5. Ryasanov В. V. Probabilistic methods in the theory of approximation of discrete functions. — Probab. Meth. Dis-cr. Math., Proc. 3rd Int. Petrozavodsk Conf., TVP/VSP, Moscow, 1993, pp. 403-412.

6. Блейхут P. Теория и практика кодов, контролирующих ошибки. — М.: Мир, 1986.

7. Колчин В.Ф., Севастьянов Б.А., Чистяков В.П. Случайные размещения. — М.: Наука, 1976.

8. Логачев О.А.; Сальников A.A., Ященко В.В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2004.

9. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов исправляющих ошибки. — М.: Связь, 1979.

10. Рязанов Б.В., Чечёта С.И. О приближении случайной булевой функции множеством квадратичных форм. — Дискретная математика., 1995, т. 7, № 3, с. 129-145.

11. Феллер В. Введение в теорию вероятностей и ее приложения, т.1. — М.: Мир, 1984.

12. Феллер В. Введение в теорию вероятностей и ее приложения, т.2. — М.: Мир, 1984.

13. Чечета С.И. О предельном распределении расстояния между случайным вектором и некоторыми двоичными кодами. — Проблемы передачи информации, 1995, т. 31, № 1, с. 90-98.Работы автора по теме диссертации

14. Зубков A.M., Серов A.A. Оценки числа булевых функций, имеющих аффинные приближения заданной точности. — Дискретн. матем., 2010, т. 22, К24, с. 3-19.

15. Серов A.A. Предельное распределение расстояния между случайной булевой функцией и множеством аффинных функций. — Теор. вер. и её прим., 2010, т. 55, №4, с. 791-795.

16. Зубков A.M., Серов A.A. Оценки числа булевых функций, имеющих аффинные приближения заданной точности. — Обозрение прикладной и промышленной математики, 2009, т. 16, вып. 2, с. 337-339.