L - класс линейных функций.
Определение
Булева функция f(x1,...,xn) называется линейной фунцией, если она представима линейным полиномом Жегалкина,
т.е. в виде суммы
, где
.
Например, к этому классу относятся функции
,
,
но не относятся
и
.
Для определения принадлежности к классу линейных функций,
необходимо построить полином Жегалкина для проверяемой функции и проверить построенный полином на наличие конъюнкций в нём.
Свойство линейности (а точнее, нелинейности) используется в криптографии.
Чем выше нелинейность функции, используемой в качестве компоненты шифра, тем выше стойкость шифра к линейному криптоанализу.
Одна из степеней нелинейности определяется по числу переменных, входящих в самую длинную конъюнкцию полинома Жегалкина.
Количество различных булевых функций от n переменных, принадлежащих классу L, равно 2n+1,
поскольку линейный полином Жегалкина от n переменных полностью определяется набором своих коэффициентов, а их ровно 2n+1, так как
.