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

12 Малая теорема Ферма [23] ( частный случай теоремы Эйле - ра ). Пусть заданы некоторые натуральные числа a и m , где m – простое . Для чисел a и m , где | m a / ( a не делится нацело на m ), справедливо равенство : 1 mod 1 m a m − ≡ . (1.12) Простые числа Ферма Простые числа Ферма – множество простых чисел вида 2 1 m p = + , где 2 k m = , 0 4 k ≤ ≤ . Введем следующее подмножество простых чисел Ферма : { } 1 2 3 17, 257, 65537 B p p p Φ Φ Φ Φ = = = = . (1.13) Числа Мерсенна Числами Мерсенна называются числа вида ( ) 2 1 p M p = − с простыми индексами р ( однако если р простое , то ( ) M p необяза - тельно является простым , например число Мерсенна ( ) M p = 11 2 1 2047 = − = – разложимое ). Введем следующее подмножество простых чисел Мерсенна : { } 1 2 3 31, 127, 8191 M M M M B p p p = = = = . (1.14) Алгоритм возведения натуральных чисел по модулю в степень Пусть задано выражение вида [23] mod j y a p = , (1.15) где H a N ∈ – основание степени ; H j N ∈ – степень выражения ; H N – множество натуральных чисел ; p – простое число ; H y N ∈ – результат вычисленного выражения , лежащий в интервале [ ] 1, 1 p − .