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

10 Для составного m Эйлером была установлена закономер - ность – формула для вычисления функции Эйлера , связанная с фор - мулой канонического разложения числа m на сомножители : 1 2 1 2 k k m p p p α α α = ⋅ ⋅ ⋅ … , где i p , 1, i k = , – простые сомножители числа m ; i α – число повто - рений сомножителя i p в разложении числа m . При этом любое со - ставное число раскладывается однозначно . Пусть задано каноническое разложение числа m . Приведем два варианта вычисления функции Эйлера для со - ставных чисел m [23]. Вариант I. Функцию Эйлера ( ) m ϕ можно вычислить по сле - дующему рекуррентному выражению : ( )( ) ( ) 1 2 1 1 1 ( ) 1 1 1 k m m p p p ϕ = − − − … . (1.10) Вариант II. В случае , если имеются кратные сомножители , то используется формула ( )( ) ( ) 1 1 2 2 1 1 1 1 1 2 2 ( ) k k k k m p p p p p p α α − α α − α α − ϕ = − − − … , (1.11) где α i – число повторений сомножителя p i в разложении числа m , 1, i k = ; k – число отличающихся сомножителей . Опишем алгоритм [25] вычисления функции Эйлера . На входе : число H m N ∈ , H N – множество натуральных чисел . На выходе : значение ( ) m ϕ . 1. Пусть задан массив p M простых чисел из l элементов , где наибольшее из простых чисел не превосходит m . Массив про - стых чисел можно получить , например , с помощью алгоритма мо - дифицированного решета Эратосфена или одним из методов фак - торизации натуральных чисел [23, 26].