Треугольные преобразования. 
Криптографические методы защиты информации. 
Часть 1. Математические аспекты

Обозначим S (f) множество номеров существенных переменных функции /(.г,х_п) X" —> X Преобразование g" множества X" называется треугольным, если g_n = г, х₂), …,/_л(х, …, х")}, иначе S (J]) с {1,…, i)

для г = 1,п.

Теорема 7.6. Треугольное преобразованиеg_n множествах" биективно функция …, Xj) биективна по переменной x-_r i = 1,п.

Л (индукция по п). Для п = 1 теорема верна, так как преобразование g, множества X задано единственной функцией / от х₍, и биективность преобразования g’j есть биективность функции /. Полагая, что теорема верна для п — 1, докажем ее для п.

Пусть преобразование g_n небиективно. Тогда в X" найдутся различные наборы: р = (р_1;…, р") и v = (vj,…, v") такие, 4TOg"(p) = g"(^v) — Тогда верны покоординатные равенства:

Неравенство р Ф v означает, что (р, …, р,.^ Ф (v, …, v,^) или (р, …, B"-i) = (vi,… v_n_j) и р" Ф v".

В первом случае из первых п — 1 равенств системы (7.10) имеем, что треугольное преобразование g,^ множества X" ^-1 не является биективным. Тогда по предположению индукции среди функций/Дх,), …, /_п_(х_ь …, х"_,) есть не биективная по переменной со старшим номером.

Во втором случае из последнего равенства системы (7.10) функция /"(Xj, …, х") не биективна по переменной х_п. Следовательно, в обоих случаях некоторые из координатных функций преобразования g" небиективны, но переменной с наибольшим номером.

Обратно, пусть преобразованиеg_n множества X" биективно, тогда g"(p) Ф Фg_n(v) при любых двух различных р, v е X", в частности при ц = (p_t,…, р,_м, р"), v = (|х,…, р"_, v"), где р" Ф v". При произвольных р,…, р"_, р" последнее означает, что /"(х,…, х") биективна по х".

Покажем биективность треугольного преобразования g_n__x множества X"^-1, отсюда последует по предположению индукции, что каждая функция преобразования g"__t биективна по переменной с наибольшим номером.

Если g_n__x небиективно, то в Х^п~^х имеются разные наборы (щ,)и_Л1__t).

и (Vj, v,₇_j) такие, что выполнены первые п — 1 равенств системы (7.10). В силу биективности функции f_n(x_{,…, х_п) по х_п подфункции /_w(p_1?…, х_п__Ху х) и /_п(У,…, v"_!, х) суть подстановки на Х> поэтому найдутся а, ЬеХ такие, что/_и(р 1,…, х_п__х, а) = /_п(У,v"_j, ft). Это равенство вкупе с первыми п — 1 равенствами (7.10) означает небиективность что противоречит предположению. ?

Следствие. Треугольное преобразование g_n множества V_n биективно все его координатные функции линейны по переменной с наибольшим номером. D>

Множество треугольных преобразований множества Х^п образует подмоноид моноида П (Х"), множество треугольных подстановок Х^п есть максимальная подгруппа нодмоноида.

Заметим, что треугольные преобразования Х^п допускают двойственное определение:

т.е. S (fj) с {г, …, п} при i = 1, …, п. Множество двойственных треугольных преобразований множества Х^п также образует подмоноид моноида П (Х").