Точное соотношение между нелинейностью и алгебраической иммунностью

Булевы функции нашли широкое применение в криптографии. В связи с появлением “алгебраической” атаки на потоковые шифры, к булевым функциям, используемым в этих шифрах в качестве нелинейных фильтров, стало, наряду с другими, предъявляться требование обладания высокой алгебраической иммунностью. Еще одним из наиболее важных криптографических свойств булевых функций, особенно используемых в потоковых шифрах, является нелинейность. В связи с этим представляет интерес вопрос связи нелинейности булевой функции с ее алгебраической иммунностью.
В настоящей работе мы получим нижнюю оценку нелинейности через значение алгебраической иммунности и построим функции, на которых эта оценка достигается при любых допустимых значениях параметров.