On approximation of permutations by imprimitive groups.pdf С 70-х годов прошлого века изучаются и строятся классы функций, максимальнодалёких от множества всех аффинных функций. Однако вместо множества всех та-ких функций можно также рассматривать симметрическую группу на конечном мно-жестве X, а вместо множества всех аффинных функций - множество всех подстано-вок, сохраняющих некоторую систему импримитивности W с r блоками мощности w,которая берётся из множества Ww , r всех таких нетривиальных систем и фиксирова-на. Максимальная группа подстановок, сохраняющая данную систему импримитив-ности W G Ww, r, есть группа сплетения IGW = (Sw I Sr ,W) в её импримитивномдействии. Близость межу подстановками g, h G Sn измеряется расстоянием Хеммин-г а x(g, h ).В работе рассматриваются два параметра:- порядок W-примитивности, то есть числоXw( g ) = min { х ^ h ) : h G I G w } ;- порядок (w, г)-примитивности, то есть числоX(w,r) (g) = min { x ( g , h) : h G I G w , W G Ww,r} .Если соответствующие параметры больше нуля, то подстановку g будем называтьW-примитивной, (w, г)-примитивной; в противном случае - W-импримитивной, (w, r)-импримитивной. При рассмотрении W-примитивности каждой подстановке ставитсяв соответствие матрица, характеризующая удалённость данной подстановки от груп-пы IGw. Через коэффициенты данной матрицы получено выражение для Xw (g). Опи-саны классы максимально W-примитивных подстановок, являющихся «бент-подста-новками» относительно системы импримитивности. Приведены оценки числа такихподстановок.Порядок (w, г)-примитивности подстановки g G S(X) определяется только еёцикловой структурой, то есть является функцией на классах сопряжённых элемен-тов в группе S (X). Перечислены цикловые структуры подстановок из множестваIG(w,r) = U IGW. Поскольку множество IG(w,r) является объединением классовW e W ( w , r )сопряжённых элементов группы S(X), то цикловая структура элемента g однознач-но характеризует его принадлежность множеству IG(w,r). В целом задача нахожденияпорядка (w, г)-примитивности оказалась сложнее. Получены порядки (w, ^-примитив-ности при чётном n в крайних случаях w = 2 и r = 2.Исходя из общего подхода, получены порядки (w, г)-примитивности для s-боксовкриптосистем AES, ARIA, Whirlpool, MISTY1, Camellia, FOX .

Скачать электронную версию публикации