Пусть R = GR(2
, 4) -кольцо Галуа характеристики 4 из 2
элементов с разрядным множеством P = {в Е R : в
= в}. В частности, если r = 1, то R = Z4 и P = {0,e}. Строится класс нелинейных подстановок пр на векторном пространстве GF(2
)
произвольной размерности m ^ 3, каждая из которых представляется композицией линейного рекуррентного преобразования с характеристическим многочленом F(x) и поэлементного выделения первого разряда элементов кольца R. Такие подстановки называются рекурсивно-порождёнными над кольцом Галуа GR(2
, 4). Интерес представляет изучение многочленов F(x) с указанным свойством, которые называются разрядно-подстановочными (или РП-много-членами). Нелинейность координатных функций рекурсивно-порождённых подстановок обеспечивается применением разрядной функции кольца Галуа. В силу простоты представления подстановок из рассматриваемого класса, они допускают очень эффективную реализацию. Ранее автором были построены два класса РП-многочленов над кольцом R = Z
4. В качестве криптографического приложения рассматривается применение рекурсивно-порождённых подстановок при построении итеративных криптографических примитивов.
Nonlinear permutations of a vector space recursively generated over a galois ring of characteristic 4.pdf Пусть R = GR(4r, 4) - кольцо Галуа характеристики 4 и мощности 4r. Множество P = r(R) = {в Е R : в2Г = в} называется разрядным множеством. Каждый элемент a Е R имеет разложение a = a0 + 2a1, as = Ys(a) E P, s E {0,1}, где Ys : R ^ P, s E {0,1}, - разрядные функции в разрядном множестве P. Алгебра (P, ф, ■) с умножением кольца R и операцией сложения a ф b = Y0(a + b), a,b E P, является полем из 2r элементов. Продолжаются исследования, начатые в работе [1]. Рассматривается задача построения нелинейных подстановок на векторном пространстве Pm большой размерности m с использованием только линейного рекуррентного закона с характеристическим многочленом F(x) = xm - fm-1xm-1 - ... - f1x - /0 E R[x] и операции выделения старшего разряда элементов кольца R. В [1] впервые доказано существование таких подстановок и описаны два нетривиальных класса для случая кольца Z4. В данной работе получен новый класс нетривиальных РП-многочле-нов F(x), индуцирующих нелинейные подстановки на алфавите Pm сколь угодно большой мощности 2rm. Пусть u Е Lr(F) -линейная рекуррентная последовательность (ЛРП) с характеристическим многочленом F(x) Е R[x]. Её знаки удовлетворяют равенству т-1 u(i + m) = Y1 /fc u(i + к). k=0 Каждый знак ЛРП u имеет разложение u(i) = u0(i) + 2u1(i), u0(i),u1(i) Е P, i = 0,1,... Обозначим через u[ i, j ] отрезок (u(i),u(i + 1),... , u(j)) последовательности u Е Е Lr (F) и через LR (F) -множество всех линейных рекуррентных последовательностей u Е Lr(F), таких, что u1 [ 0,m - 1 ] = 0. Рассмотрим отображение nF : Pт ^ Pт, заданное равенством nF(x) = u1[m, 2m - 1 ], где u Е LR(F); u0[0,m - 1 ] = x. Многочлен F(x) Е R[x] степени m, для которого отображение является биекци-ей, будем называть разрядно-подстановочным (или РП-многочленом). Будем говорить, что подстановка nF является рекурсивно-порождённой над кольцом R с законом рекурсии F(x). РП-многочлен назовём нетривиальным, если подстановка п^ нелинейна. Таким образом, каждый РП-многочлен естественным образом задаёт семейство, вообще говоря, нелинейных подстановок на пространстве Pт. Будем использовать следующие обозначения: т- 1 т- 1 F0(x) = xm ф 0 Y0(/i)xi, F1(x) = 0 ШУ. i=0 i=0 Теорема 1. Пусть R = GR(4r, 4), F(x) Е R[x] -многочлен степени m ^ 3. Если F0(x) = xm ф xm-1 ф x ф e, то F(x) является РП-многочленом тогда и только тогда, когда для каждого 5 Е P верно равенство НОД№ ф e) ф e ф Fi(x), F0(x)) = e. Данная теорема обобщает результат работы [1] на случай произвольного кольца Галуа характеристики 4.
| Аборнев Александр Викторович | г. Москва | | abconf.c@gmail.com |
Вы можете добавить статью