Читайте также:
|
|
Здесь необходимо заметить, что система булевых функций, определяющих кольцевые операции (поскольку полиномы Жегалкина образуют коммутативное кольцо с единицей), может определяться по-разному в зависимости от нужд практики. Это достаточно тонкий вопрос, поэтому мы рассмотрим только одноразрядные булевы функции. Обычно на практике используется сложение по модулю 2 (DES, LUCIFER, FEAL, IDEA), поэтому в качестве операции сложения можно использовать сложение по модулю 2 или его инверсию, а в качестве умножения - операцию “И”. Покажем, что других функций, определяющих кольцо, нет (булеву функцию от двух аргументов можно рассматривать как оператор). Полная система одноразрядных булевых функций от двух переменных Y = f(X,Z) имеет вид
Таблица 2.1
X | Z | f1 | f2 | f3 | f4 | f5 | f6 | f7 | f8 | f9 | f10 | f11 | f12 | f13 | f14 | f15 | f16 |
Естественно, что операции сложения и умножения не должны быть константами. Результат сложения должен зависеть как от X, так и от Z и удовлетворять неравенствам f(X,1) ¹ f(X,0), f(1,Z) ¹ f(0,Z), так как в противном случае сложение не будет являться групповой операцией. Этим требованиям удовлетворяет только сложение по модулю 2 и его инверсия. Операция умножения определяется однозначно по нулевому элементу. Варианты кольцевых операций приведены в таблице.
Таблица 2.2
Сложение | Умножение | Нуль | Единица | Примечание |
f7 | f2 | Коммут. кольцо | ||
f10 | f8 | Коммут. кольцо |
Очевидно, что эти две системы кольцевых операций определяют изоморфные кольца. Изоморфизм имеет вид (X,Z)® . Поэтому достаточно рассмотреть только полиномы Жегалкина. Полиномы Жегалкина образуют коммутативное кольцо A с единицей 1. Все элементы кольца являются идемпотентными, f2 = f для всех fÎ A. Это кольцо не является целостным, так как из условия f2+f = 0 следует, что f(f+1)=0, то есть каждый отличный от константы элемент кольца является делителем нуля.
Рассмотрим нелинейные свойства взаимно однозначных преобразований n‑разрядных блоков. Определим максимальный порядок нелинейности как максимальное число сомножителей в каком-либо из слагаемых многочлена Жегалкина, представляющих данное преобразование. Например, группа аффинных операторов имеет порядок нелинейности 1 (то есть не имеет нелинейных слагаемых).
Предложение 2.1. Подстановка n-разрядных слов имеет максимальный порядок нелинейности не выше n-1.
Предложение 2.2. При любой поляризации многочленов Жегалкина максимальный порядок нелинейности преобразования не меняется.
Дата добавления: 2015-12-01; просмотров: 33 | Нарушение авторских прав