авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

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

Учреждение Российской академии наук

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

На правах рукописи

УДК 519.7+519.213 Серов Александр Александрович ОЦЕНКИ РАСПРЕДЕЛЕНИЙ РАССТОЯНИЙ ОТ СЛУЧАЙНОЙ БУЛЕВОЙ ФУНКЦИИ ДО АФФИННЫХ И КВАДРАТИЧНЫХ ФУНКЦИЙ 01.01.05 теория вероятностей и математическая статистика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук Москва 2011

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

Научный консультант: доктор физико-математических наук А. М. Зубков

Официальные оппоненты: доктор физико-математических наук, профессор Г. И. Ивченко кандидат физико-математических наук, доцент С. И. Чечёта

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

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

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

Автореферат разослан апреля 2011 года.

Ученый секретарь диссертационного совета Д 002.022.01 в МИАН доктор физико-математических наук В. А. Ватутин

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

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

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

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

Как известно из практики математических исследований, линейность (в математическом смысле) изучаемого объекта упрощает его исследование.

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

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

С точки зрения теории кодирования множество аффинных функций представляет собой код Рида-Маллера первого порядка RM (1, n), а значение Nf является верхней границей для радиуса покрытия кода RM (1, n) (см. Ф. Дж. Мак-Вильямс, Н. Дж. Слоэн1 ). В случае четного n значение Nf в точности совпадает с радиусом покрытия кода RM (1, n).

При нечётном n точное значение радиуса покрытия кода RM (1, n) известно лишь для некоторых значений n, а в остальных случаях имеются только его нижние и верхние оценки.

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

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

Цель работы Цели работы:

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

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

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

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



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

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

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

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

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

Структура диссертации Диссертация состоит из введения, четырёх глав и списка литературы.

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

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

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

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

Пусть F2 – поле из двух элементов. Для произвольного натурального числа n будем обозначать через Vn = Fn пространство n-мерных векторов с компонентами из F2. Между множеством FVn = {f : Vn F2 } всех булевых функций от n переменных и пространством V2n можно установить взаимно однозначное соответствие, отождествляя функцию f FVn с вектором {f (x)| x Vn }.

Расстояние Хэмминга (f, g) между булевыми функциями f, g FVn определяется как число значений переменной x Vn, при которых f (x) = g(x). Для произвольного множества булевых функций A FVn и функции f FVn обозначим через (f, A) = min (f, g) расстояние Хэмминга от f gA до ближайшей к ней функции из множества A.

В множестве FVn всех булевых функций естественно выделяются: класс линейных функций Ln = {f FVn : f (x1,..., xn ) = a1 x1... an xn, a1,..., an F2 }, класс аффинных функций An = {f FVn : f (x1,..., xn ) = a0 a1 x1... an xn, a0,..., an F2 } и класс квадратичных функций n FVn :

Qn = {f f (x1,..., xn ) = bij xi xj ai xi a0, bij, ai F2 }, 1 ij n i= где сложение в F2 ;

очевидно, Ln An Qn. Мощности этих классов имеют следующий вид:

n | Ln | = 2n, | An | = 2n+1 и | Qn | = 2(2 )+n+1.

Предельные теоремы для распределения расстояния между случайной булевой функцией и множеством линейных булевых функций доказаны в работе Б.В. Рязанова2. В частности, было показано, что если f FVn – случайная булева функция, имеющая равномерное распределение на FVn, то (f, Ln ) an x = 1 ee x R, lim P x (1) bn n где n ln ln 2n + ln 4 n n bn = an = 2 2 n ln 2 1,. (2) 4n ln 2 2 n ln В совместной работе Б.В. Рязанова и С.И. Чечёты3 доказаны предельные теоремы для распределения расстояния от случайной булевой функции до множества квадратичных булевых форм со свободным членом. В частности, показано, что для любого фиксированного x Ryasanov B.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.

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

(f, Qn ) hn x = 1 ee, lim P x (3) sn n где n 4 ln n2 ln 2 ln 1 n n sn = hn = 2 2 n ln 2 1 +,.

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

Теорема 1. Если f FVn – случайная булева функция, имеющая равномерное распределение на FVn, то для любого фиксированного x R (f, An ) an x = 1 ee, lim P x ln 2 (5) bn n где an и bn определены в (2).

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

Рассмотрим произвольный линейный код C длины n с минимальным расстоянием d = min wt(w) и n k проверочными символами. В таком w=0, wC k коде имеется 2 кодовых слов.

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

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

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

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

2n Vn = Vn (i).

i= Введём обозначение def (2) Nn (i, r) = |{x Vn : max{dist(x, 0), dist(x, c)} r, wt(c) = i}|.

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

Теорема 2. Если известен весовой спектр кода C, т.е. мощности множеств кодовых слов веса i Wi = Vn (i) C, i {0, 1,..., n}, то справедливы оценки для чисел элементов множеств F2 (C, r) = {v Vn :

dist(v, C) r} при r n r r k m k m (1 q(n, r))2 Cn |F2 (C, r)| 2 Cn, m=0 m= n r (2) 1 m где q(n, r) = |Wi |Nn (i, r)/ Cn.

m= i= Оценки теоремы 2 справедливы для более широкого класса кодов:

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

r def (1) (2) m Ряд явных двусторонних оценок для Nn (r) = Cn и Nn (i, r) m= получены в следующих трёх утверждениях.

Утверждение 1. При r n/2 справедливы оценки r 2(r+1) n m 2n 2r 2 nV 1 Cn nV 1, n n m= r nn 1 m 1 Cn 2r nV 2r rr (n r)nr 2nV 1 n m= n nn, 2(r+1) (r + 1)r+1 (n r 1)nr1 2nV 1 n где (·) функция стандартного нормального распределения, V (z) = (1 z) ln(1 z) + (1 + z) ln(1 + z).

Утверждение 2. Если 0 r [n/2], то r 1 r r m r Cn (1 + q) Cn Cn, где q =, 1q nr+ m= [k/2] (1) (2) Ck Nnk (r [k/2]) Nn (k, r), где 0 k n.

Утверждение 3. Если 0 r [n/2] и 0 k n, то 1 + qk k/2 rk/ (2) Nn (k, r) Ck Cnk при чётном k, (1 qk ) [k/2] r[k/2] (2) Nn (k, r) Ck Cnk при нечётном k, (1 qk ) r[k/2] r где qk = q= nr+1.

n[k/2]r+ В третьей и четвёртой главах приводятся основные результаты диссертации: формулы и двусторонние оценки для чисел элементов множеств F2 (Ln, r) = {f FVn : (f, Ln ) r}, F2 (An, r) = {f FVn : (f, An ) r}, F2 (Qn, r) = {f FVn : (f, Qn ) r} всех булевых функций от n переменных, расстояния от которых до множеств линейных Ln, аффинных An, квадратичных Qn функций соответственно меньше или равны r. Известно5, что F2 (An, r) = FVn, если n1 n/ r2 2.

В частности, из результатов работы Б.В. Рязанова2 следует, что если F2 (Ln, r) множество всех булевых функций, расстояние Хемминга от которых до множества линейных функций (аффинных с нулевым свободным членом) не превосходит r, то при n n x(n,r) 22 |F2 (Ln, r)| 1 ee sup 0, (6) 0 r2n1 2n/ где x(n, r) определяется равенством r = 2n1 2n1 n ln 2 ln(4n ln 2) + x(n, r).

Это означает, что для основной массы булевых функций от n переменных расстояние до множества линейных функций при n имеет вид 2n1 2n1 n ln 2 2n /n.

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

Логачев О.А., Сальников А.А., Ященко В.В. Булевы функции в теории кодирования и криптологии.

М.: МЦНМО, 2004.

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

Теорема 3. Если n 2, то r r n+1 m n+1 m (1 Q(n, r))2 C2n | F2 (An, r)| 2 C 2n, m=0 m= r r n m 2n m 1 1 Q(n, r) 2 C2n | F2 (Ln, r)| C 2n, m=0 m= r 2n2, где Q(n, r) = 0 при 2(c2 n)3/ 1 (c2 2 )n r Q(n, r) 2 exp r 2n/ 8, r = 2n1 cr 2n1 n ln 2 0, cr 1.

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

Отношения верхних и нижних оценок в теореме 3 стремятся к 1, если n c 2n1 n ln 2, c 1, 5 = 1, 2247...

nиr С помощью утверждения 1 показано, что в области больших x(n,r) уклонений (где 1 ee 0) относительная погрешность n x(n,r) приближения величины 22 |F2 (Ln, r)| величиной 1 ee быстро растет с уменьшением r.

Следствие 1. Если c 1 и n, r так, что выполняется условие r 2n1 c 2n1 n ln 2, то при достаточно больших n |F2 (Ln, r)| 1,.

c 22n 1 eex(n,r) Из результатов работы Б.В. Рязанова и С.И. Чечёты6 (см. формулу (3)) следует, что если F2 (Qn, r) множество всех булевых функций, расстояние Хемминга от которых до множества квадратичных функций не превосходит r, то при n n x(n,r) 22 |F2 (Qn, r)| 1 ee sup 0, (7) 0 r2n1 2n/21 ln Рязанов Б.В., Чечёта С.И. О приближении случайной булевой функции множеством квадратичных форм. Дискретная математика., 1995, т. 7, № 3, с. 129–145.

где x(n, r) определяется равенством n r = 2n1 2 2 n2 ln 2 + n ln 2 2 ln n ln( ln 2) + ln 2 + 2x(n, r). (8) Это означает, что для основной массы булевых функций от n переменных расстояние до множества квадратичных функций при n имеет вид 2n1 2n2 (n2 ln 2 + n ln 2 2 ln n) + O 2n/2 /n.

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

Теорема 4. Если n 3, то r r (n )+n+1 (n )+n+ m m (1 Q(n, r))2 C2n | F2 (Qn, r)| 2 C 2n, 2 m=0 m= r 2n3, где Q(n, r) = 0 при 2n (cr 3)/6+n+ (cr n) Q(n, r) exp n2 7 · 2n/ 15 и r = 2n1 cr n 2n2 ln 2 0, cr 1.

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

Отношения верхних и нижних оценок в теореме 4 стремятся к 1, если n и r 2n1 c n 2n2 ln 2, c 3 = 1, 7321...

С помощью утверждения 1 показано, что в области больших x(n,r) уклонений (где 1 ee 0) относительная погрешность n x(n,r) приближения величины 22 |F2 (Qn, r)| величиной 1 ee быстро растет с уменьшением r.

Следствие 2. Если c 1 и n, r так, что выполняется условие r 2n1 c 2n2 (n2 + n) ln 2, то при достаточно больших n |F2 (Qn, r)| 1,.

c 2n x(n,r) 2 1 ee Автор выражает глубокую благодарность своему научному руководителю д.ф.-м.н. А. М. Зубкову за постановку интересных задач, постоянное внимание к работе и критические замечания.

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

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

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

[4] Зубков А.М., Серов А.А. Оценки числа булевых функций, имеющих аффинные приближения заданной точности. Материалы Х Международного семинара Дискретная математика и её приложения (Москва, МГУ, 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 ane 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.



 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.