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

14 Таким образом , первообразным элементом является число a , для которого выполняется сравнение : ( ) 1mod m a m ϕ ≡ , (1.16) где ( ) ( ) m m P a ϕ = . Существует следующий переборный вариант поиска перво - образных элементов [23]. В качестве кандидатов в первообразные элементы рассматриваются все числа 2, 1 a m = − , которые удовле - творяют следующим условиям : 1) взаимной простоты чисел a и m : ( ) , 1 a m = ; 2) ( ) 1mod m a m ϕ ≡ или ( ) mod 1 m a m ϕ = ; 3) для 1, ( ) 1 r m ∀ = ϕ − , являющегося делителем числа ( ) m ϕ ( т . е . | ( ) r m ϕ ), выполняется условие 1mod r a m ≡/ . Замечание 1.1. Число 1 в качестве варианта первообразного элемента не рассматривается , так как при любой степени единицы и любом модуле будет выполняться условие ( ) 1 1mod m m ϕ ≡ . Существует частный случай переборного варианта поиска первообразных элементов (« более быстрый ») – когда модуль m яв - ляется простым числом p ( в этом случае первообразные элементы называются примитивными элементами над конечным полем [27]). В качестве вариантов первообразных корней рассматриваются все числа 2, 1 a p = − , удовлетворяющие условиям : 1) взаимной простоты чисел a и m : ( ) , 1 a m = ; 2) так как функция Эйлера , вычисляемая от простого числа , равна ( ) 1 p p ϕ = − , то 1 1mod p a p − ≡ или 1 mod 1 p a p − = ; 3) для 1, 1 r p ∀ = − , являющегося делителем числа ( ) 1 p p ϕ = − , т . е . ( ) | 1 r p − , выполняется условие 1mod r a p ≡/ .