Линейные конгруэнтные генераторы

Линейными конгруэнтными генераторамиявляются генераторы следующей формы

в которых- это n-ый член последовательности, а- предыдущий член последовательности. Переменные а, b и т - постоянные: а - множитель, b - инкремент, и т - модуль. Ключом, или затравкой, служит значение X0.
Период такого генератора не больше, чем т. Если а, b и т выбраны правильно, то генератор будет генератором с максимальным периодом (иногда называемым максимальной длиной), и его период будет равен т. (Например, b должно быть взаимно простым с т). 
В 15-й,  перечисляются хорошие константы линейных конгруэнтных генераторов . Все они обеспечивают генераторы с максимальным периодом и, что даже более важно, удовлетворяют спектральному тесту на случайность для размерностей 2, 3,4, 5 и 6. Таблица организована по максимальному произведению, которое не вызывает переполнения в слове указанной длины .
Преимуществом линейных конгруэнтных генераторов является их быстрота за счет малого количества операций на бит.
К несчастью линейные конгруэнтные генераторы нельзя использовать в криптографии, так как они предсказуемы. Впервые линейные конгруэнтные генераторы были взломаны Джимом Ридсом (Jim Reeds), а затем Джоан Бояр (Joan Boyar) [1251]. Ей удалось также вскрыть квадратичные генераторы:

и кубические генераторы:
Другие исследователи расширили идеи Бояр, разработав способы вскрытия любого полиномиального генератора. Были взломаны и усеченные линейные конгруэнтные генераторы, и усеченные линейные конгруэнтные генераторы с неизвестными параметрами. Таким образом была доказана бесполезность конгруэнтных генераторов для криптографии.
Табл. 16-1. Константы для линейных конгруэнтных генераторов

Однако, линейные конгруэнтные генераторы сохраняют свою полезность для некриптографических приложений, например, для моделирования. Они эффективны и в большинстве используемых эмпирических тестах демонстрируют хорошие статистические характеристики.
Объединение линейных конгруэнтных генераторов
Был предпринят ряд попыток объединения линейных конгруэнтных генераторов. Криптографическая безопасность полученных результатов не повышается, но они обладают более длинными периодами и лучшими характеристиками в некоторых статистических тестах . Для 32-битовых компьютеров можно использовать следующий генератор:

Этот генератор работает при условии, что компьютер может представить все целые числа между -231+85 и 231-249. Переменные s1 и s2 глобальны и содержат текущее состояние генератора. Перед первым вызовом их необходимо проинициализировать. Для переменной s1 начальное значение должно лежать в диапазоне между 1 и 2147483562, для переменной s2 - между 1 и 2147483398. Период генератора близок к 1018. На 16-битовом компьютере используйте другой генератор:

Этот генератор работает при условии, что компьютер может представить все целые числа между -32363 и 32363. Переменные s1, s2 и ,s3 глобальны и содержат текущее состояние генератора. Перед первым вызовом их необходимо проинициализировать. Для переменной s1 начальное значение должно лежать в диапазоне между 1 и 32362, для переменной s2 - между 1 и 31726, для переменной ,s3 - между 1 и 31656. Период генератора равен 1.6*1013. Для обоих генераторов константа b равна 0.