Research of the group of bijective differen-tiable modulo p functions.pdf Генерация последовательностей больших периодов, состоящих из элементов конечного кольца, является важной задачей в криптографии. Для генерации последовательности может использоваться следующая рекуррентная формула: xi+i = / (xi), i = 1, 2,..., где / - некоторая функция над кольцом Zpn. Возникает проблема выбора /, такой, чтобы она легко вычислялась и генерировала последовательность xix2 ... максимального периода pn. Как вариант выбора таких / в [1] предложены и исследованы дифференцируемые по модулю pn функции, в том числе те из них, которые являются биективными и транзитивными. В частности, построены критерии биективности и транзитивности и получена формула для вычисления обратных биективных дифференцируемых по модулю pn функций. В данной работе проведено более глубокое изучение биективных дифференцируемых функций, а также основных задач, в которых данные функции могут быть применимы. Напомним основные определения и утверждения, связанные с дифференцируемыми по модулю функциями. Определение 1. Любая функция f : Zp - Zp является дифференцируемой функцией по модулю p. Функция f : Zp n -У Zpn называется дифференцируемой по модулю pn (n > 1), если: 1) f mod p* - дифференцируемая по модулю p* функция, i = 1,... , n - 1; 2) f (x + ар"-1) = f (x) + ар""-:^'(x) (mod pn), где f' - некоторая функция из Zpn в Zpn. Функция f' называется производной функции f по модулю pn. Класс дифференцируемых функций обозначается Dn. Пусть An = {f : f е Dn Л fn-1 (x) = 0}; Bn = {f : f (x + apn-1) = f (x) (mod pn) Л f (x) = 0 (mod pn-1)}; Cn = {f : f (x) = xn-1pn-1h'(x), где h' - производная некоторой функции из Dn}. Утверждение 1 [1]. Для любой функции f из Dn существует единственная тройка (fA, fB, fc), где fA е An, fB е Bn, fc е Cn, такая, что f (x) = fA(x) + fB(x) + fc(x). Обратно, для каждой тройки (fA,fB, fc), где fA е An, fB е Bn, fc е Cn, существует функция f из Dn, такая, что f (x) = fA(x) + fB(x) + fc(x). Определение 2. Дифференцируемая по модулю pn функция f называется обратимой (или биективной), если существует функция g, такая, что g(f(x)) = x. Функция g называется обратной для функции f. Определение 3. Дифференцируемая по модулю pn функция называется транзитивной, если она индуцирует одноцикловую подстановку на Zpn. Будем обозначать группу биективных дифференцируемых по модулю pn функций с композицией в качестве операции как Bin. Пусть отображение nn : Bin - Bin-1 определяется как nn(f) = f mod pn-1. Очевидно, что это гомоморфизм с ядром Ker nn = {f : f (x) = xo + x1p + ... + xn-2pn-2 + fB(x) + f'(x)xn-1 pn-1, fb е Bn}. Ядро Ker nn является группой относительно композиции функций в нем. В дальнейшем эта группа обозначается 1Bn. Пусть Lp = ({f : Zp - Zp : f (x) = ax + p, а = 0}, о }. Теорема 1. pn-1 Bin ^ Bin-1 * IBn ~ Bin-1 * 0 Lp, *=1 где при композиции функций в Bin компонента f из Bin-1 переставляет функции f в 1Bn по следующему закону: ff)(x) = xo + x1p + ... + xn-2pn 2 + fB(fA(x)) + f'(fA(x))xn-1pn 1 pn-1 а именно: в сумме ф Lp слагаемое ax + b с номером i ставится на место слагаемого *=1 x + bf'A с номером fA(i). pn-1 Здесь и далее если слагаемое ax + b суммы ф Lp имеет номер i и /а е An, то через i=i a/Ax + b/A обозначается слагаемое этой суммы с номером /^(i). Рассмотрим следующее равенство: и = /-i о v о ^ (1) где /, v,u е Bin. Оно фигурирует при рассмотрении следующих задач: - поиск сопрягающего элемента; - генерация транзитивных функций с помощью биективных. Задача поиска сопрягающего элемента - это решение функционального уравнения, которое задаётся равенством (1) при известных и и v и неизвестном /. Искать сопрягающий элемент можно с помощью теоремы 1. Используя равенство pn-1 Bin ^ Bin-i * 0 Lp, i=i можно проводить вычисления во второй части полупрямого произведения, если они уже проведены по первой. В Lp содержатся функции вида ax + b, a = 0. Соответственpn-1 но, при решении уравнения (1) для каждого слагаемого суммы Lp выполняется i=i выражение vix + V2 = (/iuAO/A (u(A (/ix + /2) + u2A ) - (/iuAOfA )-i/2uAO/A , которое упрощается в систему Vi/UAO/A - u/A/i = 0, V2/rO/A - u/A + /2UAO/A - u{A /2 = 0. Объединив эти системы для всех слагаемых, получим систему из 2pn-:L уравнений. Отметим, что она является линейной. Получившуюся систему можно разбить на две части, одна - только из уравнений, в которых отсутствуют /2, вторая - из уравнений, в которых /2 присутствуют, и решать сначала первую, а затем вторую. Матрица получившейся системы представляет собой сумму перестановочных матриц, т. е. содержит большое число нулей, что может способствовать более быстрому её решению. Другой задачей, в которой фигурируют биективные дифференцируемые по модулю pn функции, является генерация транзитивных дифференцируемых по модулю pn функций. Генерировать транзитивные функции с помощью равенства (1) можно, если положить v транзитивной функцией, и тогда u будет также транзитивной. Например, можно выбрать v(x) = x + 1, и тогда достаточно уметь генерировать биективные функции и вычислять значение обратной функции, чтобы вычислять u. Критерии би-ективности и формулу для вычисления обратной функции можно найти в [1]. Верна следующая Теорема 2. Все транзитивные дифференцируемые по модулю pn функции могут быть получены сопряжением функции /(x) = x+1 биективными дифференцируемыми по модулю pn функциями. Таким образом, пробегая по всем биективным функциям, можно предложенным способом получить все транзитивные функции. Итак, для генерации последовательностей больших периодов биективные дифференцируемые по модулю pn функции могут быть использованы как сопрягающие для транзитивных функций. Представляют интерес также статистические свойства таких последовательностей. Поэтому группа дифференцируемых по модулю pn функций заслуживает внимания. Однако пока не описано представление, позволяющее эффективно вычислять данные функции, их реальное использование не практично. Поэтому в дальнейшем стоит задача поиска эффективного представления для функций из класса дифференцируемых по модулю pn функций или из его подклассов. Предполагается, что данное представление можно получить для этих функций по модулю 2n, используя элементарные операции, такие, как AND, XOR, RIGHT_SHIFT.

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