Обратимость функций из некоторых классов

Установим свойства функций, используемых в криптографических приложениях.

Аффинные функции векторных пространств

Функция ф: Р" —> Р^т векторных пространств над полем Р называется линейной, если для любых х, у е Р^п и любых а_у b е Р

Отсюда при х = у, а = -Ь имеем: ф (0) = 0', где 0 е Р*¹, 0' е Р^пг, т. е. линейная функция ф отображает нуль пространства Р^п в нуль пространства Р^т. У линейной функции ф координатные функции линейны, т. е. представимы линейным многочленом от х_ь …, х_п, где х = (jq,…, х_п).

Утверждение 7.1. Между множеством линейных функций Р^п —" Р^т и множеством матриц размера т х п над Р имеется биекция: ф <-" М_ф, при которой набор коэффициентов линейного многочлена i-и координатной функции есть /-я строка матрицы М_ф, i = 1, …, т. Линейная функция ф сбалансирована rangM_(p = т. t>

Линейное преобразование g пространства Р^п обратимо определитель матрицы M_g порядка п отличен от 0. Множество всех обратимых линейных преобразований пространства Р^п образует группу GL"(P).

Построение матрицы M_g~^l, обратной к матрице M_g преобразования g, требует не более си³ операций сложения и умножения в поле Р, где с — константа.

Поскольку g (0) = 0, то в графе F (g) линейного преобразования имеется петля в вершине 0. Если |Р| = к и rangM_g= г, то в графе F (g) имеется ровно kⁿ — k> концевых вершин, полустепень захода каждой неконцевой вершины равна kⁿ~^r [2].

Функция ф*: Р" —" Р" называется аффинной, если ф *(?*') = ф (х) + ос для любого х е Р" , где ф — линейная функция и, а е Р™. При, а = 0' аффинная функция является линейной. Сбалансированность (биективность) аффинной функции ф* равносильна сбалансированности (биективности) линейной функции ф, так как при любых а, (3 е Р" число прообразов вектора (3 относительно ф* равно числу прообразов вектора (3 — а относительно ф.

Множество всех аффинных подстановок пространства Р" образует группу A GL_n(P).

Функция ф: Р" —> Р^т, отличная от аффинной, называется нелинейной. Если нелинейное преобразование обратимо, то обратное преобразование также нелинейное. Для нелинейного преобразования задачи распознавания биективности (сбалансированности) и построения обратного преобразования являются в общем случае трудоемкими. Вместе с тем для некоторых частных классов нелинейных преобразований известны удобные критерии их обратимости.