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

15 Теорема 1.1 [23]. Число a , 2, 1 a p = − , будет первообразным элементом по простому модулю p , если выполняется условие : 1 1mod p p i a p − ≡/ для 0, 1 i k ∀ = − , (1.17) где число 1 p − представлено в виде канонического разложения 1 0 1 i k i i p p − α = − = ∏ на k простых сомножителей ; i α – натуральные числа . Пример 1.2. Проверить с помощью теоремы 1.1, что число a = 10 является первообразным элементом по простому модулю p = 19. Число 1 18 p − = можно разложить в канонический вид : 2 1 18 2 3 p − = = ⋅ ; 1 2 p = ; 2 3 p = ; ( ) 1 1 9 p p − = ; ( ) 2 1 6 p p − = . Проверим , что 1 1mod p p i a p − ≡/ , 1, 2 i = . Запишем промежуточные результаты вычислений : 3 10 mod 19 1000 mod 19 12 = = ; ( ) 2 6 3 10 mod 19 10 mod 19 mod 19 11 = = ; ( )( ) ( ) 9 6 3 10 mod 19 10 mod 19 10 mod 19 mod 19 11 12 mod 19 132mod 19 18 1. = = ⋅ = = = ≠ Таким образом , 9 10 1mod 19 ≡/ и 6 10 1mod 19 ≡/ , т . е . число a = 10 является первообразным элементом по простому модулю p = 19. Общее число первообразных корней задается следующей теоремой . Теорема 1.2 [23]. Число первообразных корней , принадле - жащих диапазону 2, 1 a p = − , равно :