RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2023, том 35, выпуск 3, страницы 45–59 (Mi dm1771)

Эта публикация цитируется в 2 статьях

Новые границы нелинейности PN-функций и APN-функций над конечными полями

В. Г. Рябов

НП «ГСТ»

Аннотация: Нелинейность векторной функции над конечным полем в статье определяется как расстояние Хэмминга от нее до множества аффинных отображений в пространстве значений всех векторных функций. Для произвольного поля из $q$ элементов получены нижние границы нелинейности PN- и APN-функций от $n$ переменных, равные $q^n - \sqrt { q^n - 3 \cdot 2^{-2}} - 2^{-1}$ и $q^n - \sqrt { 2q^n - 7 \cdot 2^{-2}} - 2^{-1}$ соответственно и улучшающие ранее известные границы для булевого случая. Показано, что в качестве верхней границы нелинейности таких функций может быть использована величина $q^n - n - 1$. При $q = 2,3,4$ получены точные значения нелинейности PN- и APN-функций малой размерности.

Ключевые слова: конечное поле, векторная функция, PN-функция, APN-функция, нелинейность, EA-эквивалентность.

УДК: 519.716.322

Статья поступила: 29.03.2023

DOI: 10.4213/dm1771



© МИАН, 2024