On a sufficient condition for impossibility to reduce the period of the high order binary digit position sequences over .pdf В настоящее время наблюдается особый интерес к изучению p-ичных разрядных последовательностей над кольцами вычетов по модулю pn. Это связано с тем, что данные последовательности обладают высокой линейной сложностью и могут быть использованы в датчиках псевдослучайных последовательностей. Со списком работ по данной тематике можно ознакомиться, например, в [1]. Большое внимание уделяется задаче восстановления линейных рекуррентных последовательностей (ЛРП) над примарными кольцами вычетов по их усложнению, особенно в тех случаях, когда ЛРП максимального периода (ЛРП МП) отображается в свою старшую координатную последовательность [2]. Меньше работ посвящено r-ичным разрядным последовательностям, где r = p, которые также могут быть рассмотрены как усложнения линейных рекуррент над простыми полями и кольцами Галуа. Такие последовательности рассматривались А. С. Кузьминым в [3]. Им найдены все двоичные разрядные последовательности ЛРП МП над конечным простым полем нечётной характеристики, в которых наблюдается эффект сокращения периода. В [4] эти результаты обобщены и доказано, что сокращение периода в r-ичных разрядных последовательностях над конечным простым полем, где r > 2, невозможно. Любой знак u(i) некоторой ЛРП МП u над примарным кольцом представим в виде u(i)= Е ua(i)2s, s=0 где k = [log2pn]. Таким образом, последовательность вида us = (us(0), us(1),...), является s-й разрядной последовательностью ЛРП МП u над примарным кольцом. Обозначим T(u), T(u) периоды последовательностей u и щ. В [5] сформулирован результат о том, что при наличии всех элементов на цикле ЛРП МП u существует только один номер z двоичной разрядной последовательности над кольцом Галуа, зависящий от вида числа p и степени n, для которого T(uz)|(T(u)/2). Вопрос о возможности сокращения периода в 2 раза в противном случае остался незатронутым. Лемма 1. Для всех возможных пар элементов a и b кольца Zpn, таких, что выполняется соотношение a + b = 0 (mod pn), справедлива следующая формула для нахождения числа щ пар, у которых совпадают 1-е двоичные разряды: (pn - 1)/2 - 2l +mini щ = 2 mini +min (2minl, ((pn - 1)/2 - 2l + minl) mod 2l) +minl, 2i где minl = min(((pn - 1)/2) mod 2l, 2l - ((pn - 1)/2 + 1) mod 2l) + 1. Замечание 1. Заметим, что так как 1 ^ minl ^ 2l-1 - 1, то верхняя и нижняя оценки числа щ могут быть получены тривиальным образом. Полученное значение щ может быть использовано для доказательства следующих утверждения и теоремы. Утверждение 1. Пусть u - ЛРП МП над кольцом Zpn с характеристическим многочленом f (x), deg f = m, пусть также на цикле последовательности u встречаются 2щ различных элементов из Zpn. Тогда для отсутствия сокращения периода в разрядной последовательности с номером I > z (см. [5]) в 2 раза достаточно выполнения неравенства pn-1(pm - 1) > (2^l)m (1) Замечание 2. Данное утверждение носит скорее теоретический характер, на практике доля номеров двоичных разрядных последовательностей, для которых выполняется неравенство (1) в случае различных p, n, m и /, мала. Теорема 1. Пусть u - ЛРП над примарным кольцом Zpn. Если на цикле последовательности u встречается более 2щ различных элементов, то T(ul) /(T(u)/2).

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