Теорема.

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

• 1) параметры Сит являются взаимно простыми (наибольший общий делитель НОД(С, т) = 1);
• 2) число А — 1 должно делиться на все простые числа, из произведения которых состоит модуль т;
• 3) если модуль т делится на 4, то А — 1 тоже должно делиться на 4.

В ЛКГ операция взятия остатка от деления mod является достаточно трудоемкой. Для того чтобы генератор работал быстро, существует прием, позволяющий избежать явного деления по модулю.

Выбираем модуль т как максимально возможное число в компьютерном слове. Например, если в машинном слове 32 бита и 1 бит отводится под знак, то максимально возможный модуль т = 2³¹. Избежать деления по модулю помогает такое явление, как переполнение разрядной сетки. Все биты, которые не влезут в разрядную сетку, будут отброшены, а то, что останется, и будет представлять собой результат остатка от деления.

Рис. 3.1. Остаток от деления по модулю 2³¹

Однако, как было сказано выше, генератор случайных чисел должен не только обладать длинным периодом и хорошим быстродействием, но и хорошими статистическими свойствами. Оказывается, что статистические свойства генераторов с полным периодом не превосходят свойств генераторов с простым модулем, которые более просты и понятны.