Constructing transitive polynomials over the ring Z _p2.pdf В работе рассматриваются рекуррентные последовательности вида a mod pn, f (a) mod pn, f (f (a)) mod pn, ..., (1) где f (x) E Z[x], a E Z, n E N. Такие последовательности находят применение в различных областях математики. В частности, в криптографии они используются в качестве псевдослучайных последовательностей. Поэтому возникает проблема построения таких полиномов f (x), для которых указанная последовательность имеет большой период. Определение 1. Полином f (x) E Z[x] будем называть транзитивным по модулю pn, если последовательность (1) имеет период pn, то есть максимальный. Определение 2. Полином f (x) будем называть тождеством по модулю pn, если f (a) mod pn = 0 для любого a E Z. Транзитивные полиномиальные преобразования колец вычетов рассматриваются в [1]. В соответствии с этой работой, если p E {2, 3}, то полином, транзитивный по модулю p2, транзитивен по модулю pn для любого натурального n. Кроме того, транзитивные полиномы по модулю pn могут быть получены из транзитивных по модулю p2 путём добавления тождества. Таким образом, важным является случай n = 2. Рассмотрим задачу получения всех транзитивных полиномов по модулю p2. Известны различные формы представления полиномиальных функций. Любая полиномиальная функция над Zp2, в соответствии с [2], может быть представлена многочленом f (x) = fo(x) + pfi(x) + (xp - x)f2(x), (2) где f0(x), fi (x), f2(x) -полиномы над кольцом Zp степени меньше p. Из формы (2) нетрудно получить другую, которая будет использована далее: f (x) = fo(x) + pfi(x) + (xp - x)(f0(x) - f (x)), (3) где f (x) и f(x) -производные для f (x) и f0 (x) с коэффициентами, приведёнными по модулю p. Обозначим fp(x) = f (f ... (x)...). 4-V-' p раз Метод построения транзитивного по модулю p2 полинома f (x) состоит из следующих шагов: 1) Выбирается полином f0(x) E Zp[x], транзитивный по модулю p. 2) Выбирается такой f (x) E Zp[x], для которого выполняется П f (x) mod p = 1. 3) Выбирается f1(x) E Zp[x] - произвольный полином степени меньше p. 4) Многочлен f (x) строится по формуле (3). 5) Выполняется проверка f (x) на транзитивность: если fp(а) = а для некоторого а Е Z, то искомый полином получен, иначе вернуться на шаг 3 и выбрать в качестве f1(x) другой полином. Корректность проверки на транзитивность в шаге 5 алгоритма следует из необходимого и достаточного условия транзитивности, сформулированного в [1], а также из выбора f/(x) на шаге 2. Условие, выполнение которого требуется в шаге 2, следует из утверждений, сформулированных в [3]. Количество полиномов, удовлетворяющих данному условию, равно (p - 1)p-1. Для того чтобы с помощью этого метода получить все транзитивные по модулю p2 полиномы, на шаге 3 потребуется перебрать все возможные полиномы с коэффициентами из Zp, степень которых меньше p. Их количество равно pp. С учётом того, что количество полиномов, транзитивных по модулю p, равно (p - 1)!, получаем, что метод требует перебора (p - 2)!(p - 1)pp полиномов f (x), из которых в соответствии с [1] транзитивными являются (p - 2)!(p - 1)p+1pp-1. Таким образом, доля нетранзитивных составляет 1 /p. При больших значениях p эта доля очень мала, что обеспечивает хорошую работу метода. При реализации алгоритма в системе компьютерной алгебры Sage все 15360000 транзитивных по модулю 25 полиномов были построены за 32 мин. Эксперименты проводились на компьютере с процессором Intel Core i7-3770 и оперативной памятью 15,4 Гб. Если рассматривать задачу нахождения не всех, а какого-либо одного или нескольких транзитивных полиномов, то возможно улучшение этого метода. Оно заключается в следующем. Пусть выбранный случайным образом полином f 1 (x) не привёл к транзитивному f (x). Тогда выберем такой полином g(x), для которого g(x) = 0 при всех значениях x, кроме одного. Затем подставим в формулу (3) вместо f1 (x) сумму f1(x)+g(x). Такое построение гарантирует получение транзитивного по модулю p2 полинома f(x). Пусть в результате этих действий получили многочлен F(x) = f (x) + pg(x). Тогда Fp(x) имеет следующий вид: Fp(x) = fp(x) + p [g(x) g(f (x)) ... g(fp-1(x))] f' (f (x))f' (f 2(x)) ••• f' (fp-1(x)) f' (f 2(x)) ...f' (fp-1(x)) f' (fp-1(x)) 1 В силу того, что f (x) транзитивен по модулю p, но не транзитивен по модулю p2, имеем fp(x) modp2 = x. Кроме того, g(x),g(f (x)),... ,g(fp-1(x)) -значения полинома g(x) во всех различных точках. Среди них есть только одно ненулевое. Тогда в формуле (4) второе слагаемое не равно нулю по модулю p2, откуда следует, что F(x) тран- 2 зитивен по модулю p2.

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