L - класс линейных функций.

Определение

Булева функция f(x₁,...,x_n) называется линейной фунцией, если она представима линейным полиномом Жегалкина, т.е. в виде суммы , где .

Например, к этому классу относятся функции , , но не относятся и .

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

Свойство линейности (а точнее, нелинейности) используется в криптографии. Чем выше нелинейность функции, используемой в качестве компоненты шифра, тем выше стойкость шифра к линейному криптоанализу. Одна из степеней нелинейности определяется по числу переменных, входящих в самую длинную конъюнкцию полинома Жегалкина.

Количество различных булевых функций от n переменных, принадлежащих классу L, равно 2ⁿ⁺¹, поскольку линейный полином Жегалкина от n переменных полностью определяется набором своих коэффициентов, а их ровно 2ⁿ⁺¹, так как .