Анализ псевдослучайных последовательностей по критерию энтропия цепей Маркова

16 ( 1) p ϕ − , если модуль p – простое число ; ( ( )) m ϕ ϕ , если модуль m – составное число . Следующая теорема определяет алгоритм получения всех первообразных элементов , если известен хотя бы один из этих эле - ментов . Теорема 1.3 [23]. Если a – первообразный элемент по про - стому модулю р , то остальные первообразные элементы могут быть найдены как числа mod k a p , (1.19) где k – целое , удовлетворяющее условию ( ) , 1 1 k p − = . Пример 1.3. Пусть задано конечное поле ( ) GF m с порядком m = 17. Вычислим все примитивные элементы поля (17) GF по примитивному элементу 3 в соответствии с теоремой 1.3. По алго - ритму mod k a p элементы GF(17) k , удовлетворяющие условию ( ) , 1 1 k p − = , имеют значения 1, 3, 5, 7, 9, 11, 13, 15. Соответствующие примитивные элементы представлены в табл . 1.1. Таблица 1.1 Примитивные элементы по mod 17 при ( k , p – 1) = 1 по примитивному элементу 3 3 1 mod 17 = 3; 3 5 mod 17 = 5; 3 9 mod 17 = 14; 3 13 mod 17 = 12; 3 3 mod 17 = 10; 3 7 mod 17 = 11; 3 11 mod 17 = 7; 3 15 mod 17 = 6 Отметим следующие свойства алгоритма (1.15), вытекающие из свойств первообразных корней по модулю p [23]. Обозначим рассматриваемые свойства символами С 1, С 2, С 3. Введем множе - ства М 1 = {1, 2, …, p – 1}, М 2 = {0, 1, 2, …, p – 1}. Свойство С 1. Пусть в алгоритме (1.15) переменная j прини - мает значения из множества М 1 = {1, 2, …, p – 1}. Тогда алго - ритм (1.15) выполняет инъективное отображение F 1 : М 1 → М 1 и последовательность значений у j , получаемая по алгоритму (1.15), (1.18)