Получение псевдослучайных чисел на основе сдвигового регистра (полиноминального счетчика)
Метод используется для тестирования аппаратуры. В основе алгоритма лежит операция исключающего ИЛИ (сумма по модулю два). Схемы, представленные на рисунке ниже, являются простейшими полиномиальными счётчиками. Нулевой бит в таких схемах вычисляется на основе функции исключающего ИЛИ, а все остальные биты получаются простым сдвигом. Разряды, с которых сигнал идёт на исключающее ИЛИ называются отводами.
Р
ассмотрим,
как будут изменяться значения в этих
регистрах при начальном значении 001:
Оба регистра начинают работу с одного и того же значения, но потом значения, генерируемые регистрами, начинают быстро расходиться. Но через 6 шагов, оба регистра возвращаются в исходное состояние.
Легко показать, что оба этих регистра сгенерировали максимально длинную последовательность, которая содержит все комбинации, кроме нулевой. Т.е. при разрядности регистра m, можно получить последовательность длинной 2m-1.
Полиномиальный счётчик любой разрядности имеет ряд комбинаций отводов, которые обеспечат последовательность максимальной длины, использование неверных комбинаций приведёт к генерации коротких последовательностей. Отдельная и довольно сложная задача – поиск этих комбинаций отводов.
Стоит заметить, что эти комбинации не всегда уникальны. К примеру, для 10-битного счётчика их существует две: [6;9] и [2;9], для шестиразрядного счётчика таких комбинаций двадцать восемь.
Для того, чтобы найти эти комбинации, необходимо представить счётчик в виде полинома. Счётчики из примера будут иметь следующий вид: x2 XOR 1 и x2 XOR x XOR 1.
Из теории известно, что необходимым и достаточным условием генерации полной последовательности является примитивность характеристического полинома. Это значит, что:
Характеристический полином нельзя представить в виде произведения полиномов более низкой степени;
Характеристический полином является делителем полинома zδ XOR 1, при (δ=2m-1, и не является делителем при любых других значениях δ <2m-1.
Преимуществами полиномиального счётчика является простота, как программной, так и аппаратной реализации, скорость работы и криптографическая стойкость.
Линейный конгруэнтный метод
В большинстве языков программирования именно этот метод используется в стандартной функции получения случайных чисел (random). Впервые этот метод был предложен Лехмером в 1949 году. Выбирается 4 числа:
Модуль m (m>0);
Множитель a (0<=a<m);
Приращение c (0<=c<m);
Начальное значение X0 (0<= X0<m)
Последовательность получается с использование следующей рекуррентной формулы: Xn+1=(a* Xn+c) mod m.
Этот метод даёт действительно хорошие псевдослучайные числа, но, если взять числа m,a,c произвольно, то результат нас скорее всего разочарует. При m=7, X0=1, a=2, c=4 получится следующая последовательность: 1,6,2,1,6,2,1,… Очевидно, что эта последовательность не совсем подходит под определение случайной. Тем не менее, этот провал позволил нам сделать два важных вывода:
Числа m,a,c, X0 не должны быть случайными;
Линейный конгруэнтный метод даёт нам повторяющиеся последовательности.
На самом деле любая функция, отображающая конечное множество X в X, будет давать циклически повторяемый значения. Т.о. наша задача состоит в том, чтобы максимально удлинить уникальную часть последовательности (кстати, очевидно, что длина уникальной части не может быть больше m).
Не вдаваясь в подробности доказательств, скажем, что период последовательности будет равен m только при выполнении следующих трех условий:
Числа c и m взаимно простые;
a-1 кратно p для каждого простого p, являющегося делителем m;
Если m кратно 4, то и a-1 должно быть кратно 4.
В завершении рассказа о линейном конгруэнтном методе надо сказать, что последовательности, получаемые с его помощью, хоть и являются в достаточном смысле случайными, тем не менее не являются криптографически стойкими. Т.к. зная 4 подряд идущих числа, криптоаналитик может составить систему уравнений, из которых можно найти a,c,m.