Требования к генераторам псевдослучайным числам:
1) Генерируемая последовательность должна быть статически неотличима от абсолютно случайной;
2) Знание какой-либо начальной части последовательности не должно позволять узнать следующий бит этой последовательности.
Регистры сдвига с обратной связью основаны на функции XOR (сложение по модулю 2).
В течение каждого такта регистр сдвига с линейной обратной связью выполняет следующие операции:
· читается бит, расположенный в последней ячейке; этот бит является очередным битом выходной последовательности;
· функции обратной связи вычисляет новое значение для первой ячейки, используя текущие значения ячеек;
· содержимое каждой ячейки перемещается в следующую ячейку;
· в первую ячейку записывается бит, ранее вычисленный функцией обратной связи.
Максимальный период сдвига вычисляется по формуле: , где n-количество ячеек последовательности.