Вопросы к зачету часть3 (1085485), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Стремится к нулю с ростом n.

Для доказательства этой теоремы Шенноном была использована весьма простая идея, состоящая в следующем. Подсчитаем число N(n,k) не эквивалентных двухполюсных контактных схем сложности реализующих функции от переменных и сравним его с числом .

Если окажется что N(n,k)> ,то это будет означать, что не все двоичные функции от n переменных могут быть реализованы контактными схемами сложности , т.е. найдется хотя бы одна функция для которой , а потому и подавно .

Более того эта идея отражена в следующем очевидном утверждении.

Лемма 1. Если для некоторой функции k(n) с ростом n

, (1)

то,начиная с некоторого n,

,

причем доля функций , для которых

,

стремится к нулю.

Теперь мы оценим число N(n, k).

Лемма 2.

,

где с – некоторая константа, не зависящая от n.

Сначала заметим, что сложность контактной схемы – это число контактов в ней, или число ребер в соответствующем ей графе. Кроме того, если в схеме имеется изолированая вершина, отличная от полюса, то, отбросив ее, получим схему, реализующую ту же самую функцию. Поэтому число N(n, k) не превосходит числа неэквивалентных двухполюсных контактных схем, которые имеют не более k ребер, не содержат изолированых вершин,кроме может быть, полюсов, и реализуют двоичные функции от переменных .

Указанные схемы получаются из соответствующих графов с двумя фиксированными полюсами приписыванием к каждому ребру некоторой буквы . Поэтому сначала подсчитаем число неизоморфных графов с h ребрами, двумя фиксированными вершинами-полюсами и без изолированных вершин–не полюсов. Так как каждое ребро содержит две вершины, а изолированными вершинами могут быть лишь полюсы, то число вершин такого графа не превосходит 2h+2. Каждая вершина может соединяться с ребром с любой другой вершиной и с собой. Поэтому число различных пар вершин равно

.

Теперь из всех этих пар вершин нужно выбрать h пар, при этом следует учесть, что одна и та же пара может выбираться много раз, ибо две вершины в нашем графе могут соединяться несколькими различными ребрами. Отсюда не превосходит числа сочетаний с повторениями из r элементов по h, т.е.

.

А так как (это следует из формулы Стирлинга), то

.

Теперь нужно каждому ребру графа приписать один из 2n символов . Это можно сделать ровно способами.

В итоге получим контактных схем сложности h. Теперь осталось просуммировать по h от 0 до k:

.

Теперь для доказательства теоремы Шеннона достаточно показать, что при и выполнено условие (1). Действительно, из (2) следует, что

Отсюда видно, что

а поэтому

этим теорема шеннона доказана.

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

Отметим без доказательства относящийся сюда результат Шеннона:

Для любого , найдется такое , что для

этот результат в 1958 году был улучшен Лупановым О.Б., который создав оригинальные и достаточно тонкие методы синтеза схем, доказал (см. 10), что для любого и

отсюда и из доказанной выше теоремы Шеннона вытекает асимптотическое равенство

(2)

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

в конце 50-х годов О.Б Лупановым были доказаны также асимтотические равенства

(3)

для сложности схем и

(4)

для сложности функциональных схем в базисе

Подробное и доступное изложение доказательств соотношений (2). (3), (4) содержится в работе [10]. Для доказательства каждого из этих соотношений автор находит асимптотические совпадающие нижние и верхние оценки для соответствующих функций. Нижние оценки находятся изложенными в доказательстве теоремы 1 методом Шеннона. Верхние- путем синтеза соответствующих схем. Мы проиллюстрируем его в наиболее простом случае, на отыскании оценки сложности функциональных схем в базисе (см. [10], [5]).

Теорема 2. При имеет место асимптотическое неравенство

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

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

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

Очевидно равенство.

называемое 1-м представлением функции f. Пользуясь представлением (5), построим функциональную схему, реализующую функцию f. Схема будет состоять из 6 блоков (см. рис. 22).

f

Рис. 22

Блок В₁ реализует систему всех конъюнкций вида

и содержит n-k элементов-отрицаний и не более n-k-1 элементов-конъюнкций. Следовательно, его сложность

Блок В₂ реализует систему всех конъюнкций вида

и потому

Блок В₃ реализует все нулевые функции исходя из конъюнкций (6). Очевидно, что при фиксированном i каждая конъюнкция вида (6) используется только в одной из функций Отсюда следует, что

Блок В₄ реализует все функции вида исходя из конъюнкций (7).Так как есть дизъюнкция не более s конъюнкций вида (7) при и двух конъюнкций при то

Блок В₅ реализует произведения

и потому

Блок В6 реализует f как бы дизъюнкцию функций и

В итоге имеем:

Теперь требуется минимизировать полученную оценку как бы функцию от параметров k и s. Мы опустим все рассуждения, связанные с обоснованием их выбора, а сразу положим:

(логарифм двоичный). Тогда имеем:

отсюда и следует,что

А так как полученная оценка верна для любой функции то теорема доказана.

В литературе рядом авторов, в том числе и О.Б. Лупановым, рассматривалась функция Шеннона L(n) и для функциональных схем в произвольном конечном базисе. Оказалось, что для любого конечного базиса существует такая константа C, что

В связи с этим интересно отметить, что для функции Шеннона E(n) вид и -положительная константа, зависящая только от базиса (см.[9]). В этой же работе рассмотрен вопрос об одновременной минимизации функций L(f) и E(f).

Параграф 6. 7. Математические основы синтеза булевых функций с гарантированными криптографическими свойствами.

Введение. При написании данного параграфа использована начальная часть работы В.Н. Сачкова, В.И. Солодовникова, М.В. Федюкина «Дискретные функции, используемые в криптографи», М., 1998 г., любезно предоставленная ими авторам данной книги. Здесь рассматриваются основные свойства матриц Сильвестра-Адамара, с использованием которых вводятся преобразования Уолша-Адамара и Фурье булевых функций. Приводится схема Грина быстрых преобразований Уолша-Адамара и Фурье. Определяются критерии нелинейности булевых функций, инвариантные относительно групп преобразований переменных, являющихся подгруппами группы всех аффинных преобразований. Вводятся понятие линейной структуры булевой функции и понятие расстояние булевой функции до множества функций, имеющих линейные структуры. Определяется порядок нелинейности булевой функции являющейся одним из критериев нелинейности булевой функции. Булева функция, имеющая максимальное расстояние до линейных структур, называется совершенной нелинейной функцией. Оказывается, что эти функции находятся также на максимальном расстоянии и от аффинных функций. Класс совершенно нелинейных функций совпадает с классом так называемых «бент-функций», у которых модуль преобразования Уолша-Адамара, принимает единственное значение.

1. Матрицы Адамара и их свойства.

Определение. Матрица H=(h_ij), i,j{1,2,…,n} такая, что h_ij{1,-1}, называется матрицей Адамара, если имеет место равентво

Характеристики

Список файлов ответов (шпаргалок)