About primitiveness of self-decimated generator's mixing matrices.pdf Введение Для генератора ($, т)-самоусечения, относящегося к классу генераторов с неравномерным движением [1, 2], известны результаты, связанные с длиной периода и линейной сложностью вырабатываемой гаммы. Работа посвящена перемешивающим свойствам преобразования состояний генератора ($, т)-самоусечения и его обобщения, построенного на основе нелинейных подстановок векторного пространства над конечным полем. Пусть генератор ($, т)-самоусечения построен на основе регистра сдвига (не обязательно линейного) длины n над конечным полем P. Обозначим через h базовое преобразование (пространства Pn) генератора и через H - квадратную матрицу порядка n, являющуюся перемешивающей матрицей преобразования h. Если x - состояние регистра и знак управляющей гаммы равен 1 (в частности, состояние некоторой ячейки регистра), то выполняется преобразование h6(x). Если знак управляющей гаммы равен 0, то выполняется преобразование hT(x). Следовательно, перемешивающая матрица преобразования состояний регистра равна H6 + HT. Предмет исследования - примитивность матрицы H6+HT и величина exp(H6+HT). Графом 0,1-матрицы называется орграф Г(А), у которого матрица смежности вершин есть A. Теорема 1. 1) Если матрица H примитивная и exp H = t, то матрица H6 + HT также примитивная и exp(H6 + HT) ^ [t/т]. 2) Если матрица H не примитивная и {/1,... , Zm} есть множество всех длин простых контуров орграфа T(H), где (/1,...,/m) = d > 1, то матрица H6 + HT примитивна, если т кратно d и ($, Zj) = 1, i = 1,... m. 3) Пусть в условиях п. 2 число т кратно d, ^ = 1^/(т, Zj), i = 1,... m, и {Л1,... , Ar} есть множество различных чисел среди ...,^m, где r ^ m и Л1 < • • • < Ar. Тогда: a) если Л1 > 1 и r > 2, то exp(H6 + HT) ^ g(A1,..., Ar) + n(r + 1) - £ Aj, j=1 где g(A1,..., Ar) - число Фробениуса от аргументов A1,... , Ar, то есть наибольшее натуральное число, не принадлежащее аддитивной полугруппе, порождённой натуральными числами A1,..., Ar; б) если Al > 1 и r = 2, то exp(H6 + Нт) ^ AiA2 - 2Ai - A2 + 2n; в) если Al = 1 и ^ - наибольшее число, делящее т, среди чисел /l, ... , /m, то exp(H6 + Нт) ^ 2n - 1 - Оценки пп. 3б и 3в получены с использованием оценок соответственно [3, с. 104] и [4, с. 408]. Следствие 1. Если выполнены условия п. 3а теоремы, то exp(H6 + Нт) ^ AiAr - Ai - Ar + n(r + 1) - £ V i=i Следствие вытекает из оценки числа Фробениуса [5, теорема 3.1.1] g(Ai,..., Ar) ^ ^ А:Аг - Al - Ar, r > 1. Данные оценки могут быть уточнены для частных классов перемешивающих матриц Н базового преобразования генератора ($, т)-самоусечения.

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