Research of differentiable modulo p functions.pdf Генерация последовательностей больших периодов, состоящих из элементов конечного кольца, является важной задачей. Для генерации последовательности может использоваться следующая формула: xi+1 = / (xi), (1) где / - некоторая функция над кольцом Zpn. Возникает проблема выбора такой функции /, чтобы она легко вычислялась и генерировала последовательность максимального периода pn. Над кольцом Zpn известен класс полиномиальных функций. Существуют функции этого класса, соответствующие указанным требованиям, однако их доля среди множества всех функций над Zpn мала. Так появляется задача изучения новых классов функций над Zpn. В данной работе рассматривается класс дифференцируемых по модулю pn функций. Подобный класс был определён в [1]. Для функции / : Z рП -У Zpn будем обозначать / mod pi функцию g из Zpi в Zpi, такую, что g(x) = /(x) mod pi, подразумевая, что g определена корректно. Определение 1. Любая функция / : Zp - Zp является дифференцируемой по модулю p. Функция / : Zp n - Zpn называется дифференцируемой по модулю pn (п > 1), если: 1) / mod pi - дифференцируемая по модулю pi функция, i = 1,... , п - 1; 2) /(x + apn-1) = / (x) + apn-1/'(x) (mod pn) , где /' - некоторая функция из Zpn в Zpn. Функция /' называется производной функции / по модулю pn. Класс дифференцируемых функций обозначается Dn. Класс дифференцируемых функций включает в себя класс полиномиальных функций и замкнут относительно сложения, умножения, операции композиции функций. Каждую функцию / над Zpn можно представить в виде n- 1 /(x)= Е /i(x)pi, i=0 где /i принимают значение в множестве {0,1,... ,p - 1}. Такое представление назовём координатным представлением функции /, а /i - координатными функциями, или координатами функции /. Координатные функции /i дифференцируемой функции / обладают следующим свойством: /i(x) = /i(x + apn-1), i = 0,..., n - 2. Из определения 1 следует, что функция /' тогда и только тогда является производной некоторой функции, когда её первая координата не зависит от последней координаты x, то есть /'(x + apn-1) = /'(x) (mod p) для любого a из Zpn. Определим следующие множества: 1) An = {/ : / G Dn Л /n-1(x) = 0}; 2) Bn = {/ : /(x + apn-1) = /(x) (mod pn) Л /(x) = 0 (mod pn-1)}; 3) Cn = {/ : /(x) = xn-1pn-1 h'(x), h' - производная некоторой функции из Dn}. Из определения множеств An, Bn, Cn следует, что они являются подмножествами Dn. Для функций из данных множеств справедливо следующее утверждение. Утверждение 1. Для любой функции / из Dn существует единственная тройка (/a, /в, fc), где /а G An, /в G Bn, fc G Cn, такая, что f (x) = /a(x) + /в(x) + fc(x). Обратно, для каждой тройки (/a,/в, fc), /а G An, /в G Bn, fc G Cn, существует / из Dn, такая, что /(x) = /a(x) + /в(x) + fc(x). Следствие 1. |Dn| = |An| ■ |Bn| ■ |Cn|. Между An и Dn-1 существует биекция nn, такая, что nn(f) = / mod pn-1, и соответственно |Dn-1| = |An|. Следствие 2. Число дифференцируемых функций равно pp+2p(pn 1-1)/(p-1). Определение 2. Дифференцируемая по модулю pn функция / называется обратимой (или биективной), если существует функция g, такая, что g(f (x)) = x. Функция g называется обратной для функции /. Обратная функция для дифференцируемой биективной функции также является дифференцируемой. Следующее утверждение представляет собой критерий обратимости функции. Утверждение 2. Пусть / G Dn. Тогда / обратима тогда и только тогда, когда / mod p обратима и производные функций / mod рг, где i = 2,... , n, не обращаются в 0 при любом значении x. Следствие 3. Число биективных дифференцируемых функций равно Р !((p - 1)p)p(pn-1-1)/(p-1). В следующем утверждении приведена формула для обратной функции: Утверждение 3. Пусть / - обратимая дифференцируемая функция и g - обратная к /. Тогда справедлива следующая формула: g(x) = g(x) modpn-1 - g'(x)(f(g(x) modpn-1) - /(g(x) modpn-1) modpn-1 - xn-1pn-1). Определение 3. Дифференцируемая по модулю pn функция называется транзитивной, если она индуцирует одноцикловую подстановку на Zpn. Введём следующие обозначения: / [k](x) = / (/(■■■ / (x) ■■■ )), fc раз mp" /A mP [m ^ fc] a(n,m,/A,f/,x)= П f,(/Г ](x)) (modР), fc=1 b(n, m, /а, /в, f/, x) = /в(/Amp"-k](x)) П //(/Amp"-j](x)). fc=1 j=1 Утверждение 4. Пусть / G Dn. Тогда / транзитивна тогда и только тогда, когда / mod pn-1 транзитивна в Dn-1, a(n - 1,1, fA, //, 0) = 1 и b(n - 1,1, fA, /в, //, 0) = 0. Следствие 4. Число транзитивных дифференцируемых функций равно (p - 1) !(p - 1)p(p"-1 - 1)/(p- 1)pp(p"-1 -1) /(p-1) -n+1. Транзитивные дифференцируемые функции составляют долю 1/pn в множестве биективных дифференцируемых функций. По модулю p2 все биективные, а соответственно и транзитивные дифференцируемые функции являются полиномиальными вследствие формул для числа биективных и транзитивных полиномиальных функций, приведённых в [2]. Однако производная дифференцируемой функции зависит от n - 1 первых координат x и при подъёме модуля в общем случае производная по большему модулю не зависит от производных по меньшему модулю, в то время как производная полиномиальной функции зависит только от первой координаты и при подъёме модуля не изменяется. Таким образом, по модулю pn, n > 2, число транзитивных дифференцируемых функций больше, чем число транзитивных полиномиальных функций. Однако ещё не известно представлений для дифференцируемых функций, позволяющих эффективно вычислять их. Таким образом, появляется задача поиска таких представлений для функций класса Dn. Если такие представления будут найдены, то дифференцируемые функции могут быть использованы для генерации последовательностей элементов из Zpn по формуле (1).

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