Генераторы псевдослучайных чисел и методы их тестирования — страница 6

регистра сдвигаются вправо на одну позицию. Новый крайний слева бит определяется функцией остальных битов регистра. На выходе сдвигового регистра оказывается один, обычно младший, значащий бит. Период сдвигового регистра — длина получаемой последовательности до начала ее повторения. Для LFSR функция обратной связи представляет собой сумму по модулю 2 (xor) некоторых битов регистра (эти биты называются отводной

последовательностью). LFSR может находиться в 2n − 1 внутренних состояниях, где n — длина сдвигового регистра. Если сдвиговый регистр заполнен нулями, то такое состояние будет порождать на выходе только нули (так как в качестве функции обратной связи используется xor), поэтому такое состояние бесполезно. Теоретически LFSR может генерировать последовательность с длиной 2n − 1 бит, так как длина последовательности совпадает с

количеством внутренних состояний. LFSR будет проходить все внутренние состояния (иметь максимальный период) только при определённых отводных последовательностях — если многочлен, образованный из отводной последовательности и константы 1, является примитивным по модулю 2. Степень многочлена — длина сдвигового регистра. Примитивный многочлен степени n — это неприводимый многочлен, который является делителем , но не

является делителем xd + 1 для всех d, делящих 2n − 1. Например, чтобы проверить будет ли LFSR с отводной последовательностью, состоящей из первого и четвертого битов, генерировать последовательность максимальной длины (15 для 4-битного регистра), нужно проверить, будет ли многочлен x4 + x + 1 примитивным. 3.4 Вихрь Мерсенна Вихрь Мерсенна (Mersenne twister) — это генератор псевдослучайных чисел, основываный на свойствах простых чисел Мерсенна и

обеспечивает быструю генерацию высококачественных псевдослучайных чисел. Вихрь Мерсенна лишен многих недостатков присущих другим ГПСЧ таких как малый период, предсказуемость, легко выявляемая статистическая зависимость. Тем не менее этот генератор не является криптостойким, что ограничивает его использование в криптографии. Вихрь Мерсенна является витковым регистром сдвига с обобщённой отдачей (twisted generalised feedback shift register,

TGFSR). «Вихрь» — это преобразование, которое обеспечивает равномерное распределение генерируемых псевдослучайных чисел в 623 измерениях (для линейных конгруэнтных генераторов оно ограничено 5-ю измерениями). Поэтому корреляция между последовательными значениями в выходной последовательности Вихря Мерсенна пренебрежимо мала. Вихрь Мерсенна имеет огромный период, а именно, доказано, что его период равен числу Мерсенна