Построение подстановок с использованием разрядно-подстановочных преобразований модуля над кольцом Галуа характеристики 4 | ПДМ. 2014. № 1(23).

Построение подстановок с использованием разрядно-подстановочных преобразований модуля над кольцом Галуа характеристики 4

Решается задача построения нелинейных подстановок на пространстве большой размерности с использованием только матрицы над кольцом Галуа характеристики 4 и разрядной функции этого кольца. Каждая такая подстановка может быть представлена как вектор-функция, у которой координатными функциями являются многочлены над полем. Ранее был анонсирован результат о построении подстановок из рассматриваемого класса, у которых ровно две координатные функции являются нелинейными. Здесь приводится полное доказательство этого результата.

Permutations induced by digit-permutable transformations of a module over a Galois ring of characteristic 4.pdf Введение Пусть R = GR(q2,p2) - кольцо Галуа мощности q2, характеристикиp2 с полем вычетов R = R/pR = GF(q), q = pr .В частности, при r = 1 имеем R = Zp2. Подмножество P = r(R) = {а Е R : aq = а} называют p-адическим координатным множеством, или координатным множеством Тейхмюллера кольца R. Будем называть его также разрядным множеством. Каждый элемент а Е R однозначно представляется в виде а = а0 + pai, as Е P, s Е {0,1}, называемом p-адическим разложением элемента а. Отображения Ys: R ^ P, ys(а) = as, s Е {0,1}, будем называть разрядными функциями в разрядном множестве P, а элементы а., = = y^) - p-адическими разрядами элемента а. Алгебра (P, ф, ■) с операцией сложения а ф b = Yo (а + b), а,Ь Е P, является полем. Понятия p-адического разложения и значения функции Ys естественным образом (поэлементно) распространяются на матрицы A Е Rmxm. При этом мы используем обозначение As = ys(A) = (ац(^)). Таким же естественным образом операции ф, ■ распространяются на матрицы над полем P, при этом операцию умножения матриц над полем обозначим через ©. Каждая матрица A Е Rm,m определяет отображение па : Pm ^ Pm па(у) = Yi(yAT) = Yi(yAT) Ф (У © AT) = (Му),..., Ыу)), y Е Pm (1) где ф]_,... - координатные функции и T - оператор транспонирования. Будем говорить, что па - нелинейное отображение, если оно не является гомоморфизмом группы (Pm, Ф). В работе [1] было впервые показано, что для любого m > 1 существует обратимая матрица A, такая, что па является нелинейной подстановкой на пространстве Pm. Если па -подстановка, то система функций -01,...,-0m в (1) называется ортогональной [2], матрица A при этом называется разрядно-подстановочной (или РП-мат-рицей). Координатные функции ф1,... , фш_ в (1) суть многочлены над полем P от переменных y =(yi,...,ym) Е Pm вида ^j(y) = Yi(«o(i1)yi + ... + ao(im)ym) Ф k(y), i =1,...,m, (2) где h(y) = ai(i1)yi Ф ... Ф ai(im)ym - линейные функции; Yi -однородный многочлен степени q над P. Для p = 2 имеем Yi(ao(i1)yi + ... + ao(im)ym) = ^(ao(il)yi,..., ao(im)ym)h, (3) где h = 2r-1, a2(xi,... , xm) = Yl Фх]xk - элементарная симметрическая функция порядка 2 [3]. Вообще говоря, координатная функция y) не является линейной тогда и только тогда, когда i-я строка матрицы A содержит более чем один обратимый элемент. Всюду далее R = GR(q2, 4). Пусть q = 2r, A = Ao + 2Ai, As = (as(ij)) Е Pm,m, s = 0,1. Сделаем невырожденную замену переменных x2 = yj, j = 1,...,m, в (2). Пользуясь (3), получаем, что ортогональность исходной системы (1) эквивалентна ортогональности следующей системы квадратичных функций от переменных x = (xi, . . . , xm) • gi(x) = a2(a'h(i1)xi,... ,a'h(im)xm) Ф di(x), i =1 ,...,m, (4) m где di (x) = Yl Фa1(ij )xj, i = 1, ...,m, - диагональные квадратичные функции. Оче-j=i видно, любая ортогональная система (4) соответствует некоторой РП-матрице. Таким образом, задача построения РП-матриц в рассматриваемом случае эквивалентна задаче построения ортогональных систем (4). В общем случае задача построения ортогональных систем многочленов не решена. Однако известны системы многочленов Диксона [2] и регулярные системы вида g(x), g(xS), ..., g(xSm-1), где g - квадратичная функция, существенно зависящая от переменных x1, x2, x3; S - сопровождающая матрица некоторого многочлена степени m над P [4]. Основные результаты Сначала опишем линейные преобразования, которые сохраняют свойство матрицы быть разрядно-подстановочной. Рассмотрим множество nm всех разрядно-подстановочных матриц над кольцом R размера m х m. Преобразование р: Rm,m ^ Rm,m будем называть П-стабильным, если выполнено условие (A Е nm) ^ (p(A) Е nm) . Утверждение 1. Множество линейных П-стабильных преобразований содержит следующие элементарные преобразования: 1) перестановка строк (столбцов) матрицы; 2) умножение строки (столбца) матрицы на элемент из Г(Я)*. Доказательство. Для доказательства достаточно заметить, что матрица является разрядно-подстановочной тогда и только тогда, когда система координатных функций соответствующей подстановки ортогональна. Действительно, указанные преобразования строк матрицы A равносильны соответствующим преобразованиям многочленов в системе (2). Перестановка столбцов эквивалентна перестановке переменных x1i ... 1 xm. Пусть теперь ip - умножение k-го столбца матрицы A на c Е Г(Я)*. Положим AA = 2 описаны системы из двух квадратичных функций gi(xi, ...,xm) = ^2(xi,... ,xk) ф diixi ф ... ф dimx2m, (11) g2(xi, . . . ,xm) = О 2 (xs, ... ,xt) ф d2ix2 ф ... ф d2m x\ которые дополняются некоторыми диагональными квадратичными функциями d3, . . . , dm до ортогональной системы gi = О 2 (x i, . . . , xk) ф diixi ф ... ф dimxm, g2 = О 2 (xs, ... ,xt) ф d2ixi ф ... ф d2mx2m, d3 = d3ixi ф ... ф d3mxm, (12) dm dmix2 ф ... ф dmmxm. Такая система определяет РП-матрицу A = A0 + 2A1 G Rm,m, где A1 = (dj), A0 - обратимая матрица вида ( 0...........0 \ Ao = s-1 t-s+1 ... и каждая из строк A0 с номерами i G {3,..., m} содержит ровно по одному ненулевому элементу. Обозначим через /ш(х, у), 1 ^ n < l ^ m, билинейную функцию, ассоциированную с o2(xn,... , xl) в Pm. Для чисел s, k, t из (11) определим ядро: V01 = V/ П V>L. f 1 ,k f s,t Теорема 2. Для системы (11) тогда и только тогда существует система функций (12), такая, что П = (gi,g2,ds,...,dm): Pm ^ Pm (13) является биекцией, когда существует пара векторов u, v G Pm, удовлетворяющая одному из следующих условий 1-6: 1. а) u, v G V01, б) система векторов {(g1(u), g2(u)), (g1(v), g2(v))} линейно независима над P; 2. а) u G V1, v G Vc1 f_ec2 f_ \ V01 для некоторых cb C2 G P, б) (g1(u),g2(u)) = (0, 0), (C1g1 0 C2g2)(u) = 0, (C1g1 0 C2g2)(v) = 0; 3. а) s - 1 = t - k = k - s + 1 = 1 (mod 2) и u = (0,..., 0, 0,..., 0, e,..., e, *,..., *), v = (e,..., e, 0,..., 0, 0,..., 0, *,..., *), s-1 k-s+1 t-k+1 б) многочлен D1(x) = g1(u) 0xg2(u) 0x2g1(v) 0x3g2(v) не имеет корней в P, g2(v) = 0; 4. а) s - 1 = t - k = 1 (mod 2), k - s + 1 = 0 (mod 2) и u = (e, ... , e, e,..., e, ..., *,..., *), v = (62,..., £2, e,..., 0, e,..., e, *,..., *), s-1 k-s+1 t-k+1 где £1 = e, £2 = e, £2 0 e , ч _ 2 , . 3 £2 0 e б) многочлен D2(x) = g1(u) 0 x--g2(u) 0 x2g1(v) 0 x --g2(v) не имеет £1 0 e £1 0 e корней в P, g2(v) = 0; 5. а) s - 1 = 1 (mod 2), t - k = k - s + 1 = 0 (mod 2) и u =(e,...,e,e,...,e, 0,..., 0, *,..., *), v = (e,...,0, 0,..., 0,0,..., 0,*,..., *), s-1 k-s+1 t-k+1 б) многочлен D3(x) = g1(u) 0xg2(u) 0x2g1(v) 0x3g2(v) не имеет корней в P, g2(v) = 0; k 0 ... 0 e......e 0.......0 6. а) s - 1 = 0 (mod 2), t - к = 1 (mod 2), к - s + 1 = 0 (mod 2) и u = (0,..., 0, 0,..., 0, e,...,e, *,..., *), s-1 k-s+1 t-k+1 v =(0,..., 0,e,...,e,e,...,e, *,..., *), б) многочлен D4(x) = g1(u) фxg2(u) фx1g1(v) фx3g2(v) не имеет корней в P, g2(v) = 0. Доказательство. По теореме 1, пара квадратичных функций g1, g2 дополняется некоторыми диагональными квадратичными функциями d3,...,dm до биекции (13) тогда и только тогда, когда существует подпространство K < Pm, такое, что K С L(g1,g2), dim K = 2. (14) Заметим, что L(g1,g2) состоит из 0 и всех векторов b G Pm, удовлетворяющих условию 3(С1,С2) g P2 \{0} (b g Vc^ef, (C1g1 ф Ck gk )(b) = 0) . (15) Достаточность. Для каждого пункта 1-6 теоремы покажем, что если выполнено условие подпункта а и K = (u, v), то (14) равносильно условию подпункта б. Тогда достаточность условий теоремы будет доказана. 1. Пусть u, v G V)"1 и : P ^ P - автоморфизм Фробениуса:

Ключевые слова

разрядно-подстановочная матрица, подстановка, кольцо Галуа, digit-permutable matrix, DP-matrix, permutation, Galois ring

Авторы

ФИООрганизацияДополнительноE-mail
Аборнев Александр ВикторовичООО «Центр сертификационных исследований» (г. Москва)abconf.c@gmail.com
Всего: 1

Ссылки

Nechaev A. A. and Abornev A. V. Nonlinear permutations on a space over a finite field induced by linear transformations of a module over a Galois ring // Математические вопросы криптографии. 2013. Т. 4. Вып. 2. С. 81-100.
Лидл Р., Нидеррайтер Г. Конечные поля. Т. 1. М.: Мир, 1988.
Кузьмин А. С., Нечаев А. А. Линейные рекуррентные последовательности над кольцами Галуа // Алгебра и Логика. 1995. Т. 34. №2. С. 169-189.
Никонов В. Г., Саранцев А. В. О сложности реализации в базисе ДНФ регулярных систем булевых функций // Математические вопросы криптографии. 2010. Т. 1. Вып. 3. С. 45-65.
Diedonne J. -A. La Geometrie des Groupes Classiques. Ergebnisse der Mathematik und ihrer Grenzgebiete. B.5. Springer, 1971.
KuzminA.S. and Nechaev A. A. Trace-function on a Galois ring in coding theory // LNCS. 1997. V. 1255. P. 277-290.
 Построение подстановок с использованием разрядно-подстановочных преобразований модуля над кольцом Галуа характеристики 4 | ПДМ. 2014. № 1(23).

Построение подстановок с использованием разрядно-подстановочных преобразований модуля над кольцом Галуа характеристики 4 | ПДМ. 2014. № 1(23).

Полнотекстовая версия