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

11 2. Зададим j = 1 ( индекс текущего простого числа в массиве M p ) и 1 i = ( текущий найденный сомножитель числа m ), введем m m ′ = ( запомним m для промежуточных вычислений ). 3. 0 i p = и 0 i α = . 4. Если mod [ ] 0 p m M j ′ = , то нашли сомножитель числа m : • сохраняем [ ] i p p M j = и 1 i i α = α + ; • / [ ] p m m M j ′ ′ = ( под знаком «/» понимается целочисленное деление ); • перейти к п . 4. 5. Иначе : • перейти к следующему простому числу из M p : 1 j j = + ; • если 0 i α ≠ ( на шаге 4 был найден сомножитель под номе - ром i ), то 1 i i = + ( начать поиск следующего сомножителя i p для числа m ); • перейти к п . 3. 6. Если 1 i = и 0 i p = , то m – простое число ⇒ ( ) 1 m m ϕ = − ; переход к шагу 9. 7. Если 1, i k ∃ = ( k – число отличных сомножителей числа m ), для которого 0 i α > , то ( )( ) ( ) 1 1 2 2 1 1 1 1 1 2 2 ( ) k k k k m p p p p p p α α − α α − α α − ϕ = − − − … ; переход к шагу 9. 8. Иначе ( )( ) ( ) 1 2 1 1 1 ( ) 1 1 1 k m m p p p ϕ = − − − … . 9. Вывести значение ( ) m ϕ . Выход . Теорема Эйлера [23]. Пусть заданы некоторые натуральные числа a и m , где m – составное . Если числа a и m – взаимно про - стые : ( ) , 1 a m = , то для них справедливо равенство : ( ) mod 1 m a m ϕ ≡ .