Digit-polynomial construction of substitutions over galois ring.pdf Кольцом Галуа называется конечное коммутативное локальное кольцо R = = GR(qm,pm), нильрадикал J(R) которого имеет вид pR, где p = char R и R = = R/J(R) = GF(q) -поле вычетов данного кольца [1]. При этом char R = pm, |R| = qm и m = ind J(R), m E N, - индекс нильпотентности нильрадикала J(R). Подмножество B = {b0 = 0,... , bq-1} С R называется разрядным множеством кольца R, если его элементы образуют полную систему вычетов по нильрадикалу J(R). В таком случае любой элемент a E R однозначно представляется в виде a = a(0) + p ■ a(1) + ••• + pm-1 ■ a(m-1), a(i) E B, г = 0,...,m - 1, называемом разложением элемента a в разрядном множестве B. Функции Kf: R ^-B, определяемые по правилу Kf (a) = a(i), г = 0,... , m - 1, называются разрядными функциями в разрядном множестве B, а элементы a(i) = Kf (a) -разрядами г-го порядка элемента a в разрядном множестве B. Обозначим через PR(n) класс всех полиномиальных функций от n переменных над кольцом Галуа R = GR(qm,pm). Определение 1. Функцию f (x): Rn ^ R, R = GR(qm,pm), m > 1, назовём вариационно-разрядно полиномиальной (ВРП-функцией) в разрядном множестве B, если для любого г E {0,...,m - 1} существует полиномиальная функция p^(x) E E VR(n), такая, что Kf (f (a)) = Kf (p»(a)) при всех a E Rn. При этом многочлен p^(x), г = 0,... , m - 1, будем называть г-м разрядным многочленом функции f (x). Класс всех ВРП-функций от n переменных над кольцом R в разрядном множестве B обозначим через DVR(n). Свойства данного класса над различными кольцами описаны автором в [2-4]. В частности, имеет место следующая Теорема 1. Справедливы утверждения: 1) если R = GR(q2,p2), то Vr(n) = DVR(n); 2) если R = GR(qm,pm), m ^ 3, то Vr(r) С DVR(n). (df df \ df Пусть f (x) E R[x], обозначим gradf (x) = I --(x),... , -- (x) I, где -- (x) - фор- \ dx1 dXn / dxi мальная частная производная многочлена f (x) по переменной Xi, г = 1,... , n. Если ( grad fi(x) \ f1(x),... , ft(x) ф R[x], то матрица J/b...,/t (x) = . называется матрицей \ grad ft(x) / Якоби системы многочленов, а её определитель (при t = n) |J/b...,/„ (x)| -якобианом. Следующая теорема обобщает известный из [5] результат о биективности полиномиальной вектор-функции, а также результат о биективности ВРП-вектор-функции, полученный ранее автором в [6], со случая примарного кольца вычетов и p-ичного разрядного множества на случай произвольного кольца Галуа и его разрядного множества. Теорема 2. Вектор-функция F(x) = (f1(x),... , fn(x)): Rn ^ Rn, где fi ф ф DPR(n), является биекцией тогда и только тогда, когда одновременно выполняются следующие условия: 1) (p01(x(0)),... ,p0n(x(0))) (mod J(R)): Bn ^ Bn является биекцией; 2) для любого j = 1,... ,m - 1 якобиан \JPj1,...,Pjn(x(0))| ф 0 (mod J(R)) при всех x(0) ф Bn, где pj^x) - j-й разрядный многочлен функции fi(x), j = 0,... , m - 1, i = 1,... , n, и x(0) = (xl0),...,xn0)). Получим отсюда следствие - обобщение результата о биективности полиномиальной функции [7]. Следствие 1. ВРП-функция f (x) ф DPR(1) с разрядными многочленами p0(x), ... , pm-1(x) задаёт подстановку кольца R тогда и только тогда, когда одновременно выполняются следующие условия: 1) p0(x(0)) (mod J(R)) задает подстановку на B; dp * 2) для любого j ф {1,... , m - 1} частная производная (x(0)) ф 0 (mod J(R)) dx при всех x(0) ф B. Напомним [8], что пара (Q,f), где f: Qn ^ Q и Q - конечное множество, называется n-квазигруппой (или n-арной квазигруппой), если унарная операция, полученная фиксацией всех аргументов операции f, кроме одного, любыми значениями из Q, является биекцией (такая унарная операция называется элементарной трансляцией). Иногда n-квазигруппой называют саму функцию f. При n =1 n-квазигруппа - это подстановка элементов Q. Если Q - кольцо и функция f является полиномиальной над Q, то такая квазигруппа также называется полиномиальной. Дадим критерий того, что ВРП-функция над кольцом Галуа задаёт n-квазигруппу. Соответственно такую n-квазигруппу будем называть ВРП n-квазигруппой. Теорема 3. Функция f(x) ф DPR(n) с разрядными многочленами p0(x),..., pm-1(x) задаёт n-квазигруппу на кольце R тогда и только тогда, когда одновременно выполняются следующие условия: 1) p0(x) (mod J (R)) задает n-квазигруппу на B; 2) для любого j ф {1,... , m - 1} gradpj(a) (mod J(R)) не содержит нулевых координат при любом a ф Bn. Следствие 2. Свойство ВРП-функции f (x) ф DPR(n) с разрядными многочленами p0(x),... ,pm-1(x) задавать подстановку или n-квазигруппу инвариантно относительно выбора разрядного множества B. Следствие 2 означает, что свойство ВРП-функции задавать подстановку или n-ква-зигруппу зависит лишь от разрядных многочленов, а не от выбора разрядного множества B, относительно которого рассматривается такая функция. Это позволяет строить различные подстановки и ВРП n-квазигруппы, используя одни и те же разрядные многочлены, но разные разрядные множества.

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