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

Два LCG по модулю 9 показывают, как разные параметры приводят к разной длине цикла. Каждая строка показывает состояние, развивающееся до тех пор, пока оно не повторится. В верхнем ряду показан генератор с m = 9, a = 2, c = 0 и начальным числом 1, который создает цикл длины 6. Вторая строка представляет собой тот же генератор с начальным числом 3, который создает цикл. длины 2. Использование a = 4 и c = 1 (нижняя строка) дает длину цикла 9 с любым начальным числом в [0, 8].

Линейный конгруэнтный генератор ( LCG ) — это алгоритм , который генерирует последовательность псевдослучайных чисел, рассчитанную с помощью разрывного кусочно-линейного уравнения . Метод представляет собой один из старейших и наиболее известных алгоритмов генератора псевдослучайных чисел . Теорию, лежащую в их основе, относительно легко понять, и они легко и быстро реализуются, особенно на компьютерном оборудовании, которое может обеспечить модульную арифметику путем усечения битов памяти.

Генератор определяется рекуррентным соотношением :

$X_{n+1}=\left(aX_{n}+c\right){\bmod {m}}$

где $X$ представляет собой последовательность псевдослучайных значений, а

$m,\,0<m$ — « модуль »

$a,\,0<a<m$ — «множитель»

$c,\,0\leq c<m$ — «прибавка»

$X_{0},\,0\leq X_{0}<m$ — «начальное» или «начальное значение»

— целочисленные константы, определяющие генератор. Если c = 0, генератор часто называют мультипликативным конгруэнтным генератором (MCG) или ГСЧ Лемера . Если c ≠ 0, метод называется смешанным конгруэнтным генератором .

Когда c ≠ 0, математик назвал бы повторение аффинным преобразованием , а не линейным , но это неправильное название хорошо укоренилось в информатике.

История

Генератор Лемера был опубликован в 1951 году. а «Линейный конгруэнтный генератор» был опубликован в 1958 году У. Э. Томсоном и А. Ротенбергом.

Продолжительность периода

Преимущество LCG заключается в том, что правильный выбор параметров приводит к тому, что период становится известным и продолжительным. Хотя это и не единственный критерий, слишком короткий период является фатальным недостатком генератора псевдослучайных чисел.

Хотя LCG способны генерировать псевдослучайные числа , которые могут пройти формальные тесты на случайность , качество вывода чрезвычайно чувствительно к выбору параметров m и a . Например, a = 1 и c = 1 дают простой счетчик по модулю m , который имеет длинный период, но явно неслучайен. Другие значения c , взаимно простые с m, создают последовательность Вейля , которая лучше распределена, но все же явно неслучайна.

Исторически сложилось так , что неправильный выбор приводил к неэффективному внедрению LCG. Особенно наглядным примером этого является RANDU , который широко использовался в начале 1970-х годов и привел ко многим результатам, которые в настоящее время подвергаются сомнению из-за использования этого плохого LCG.

Существует три распространенных семейства параметров выбора:

м простое, c = 0

Основная статья: Генератор случайных чисел Лемера

Это оригинальная конструкция Lehmer RNG. Период равен m −1, если множитель a выбран примитивным элементом целых чисел по модулю m . Начальное состояние должно быть выбрано между 1 и m −1.

Одним из недостатков простого модуля является то, что модульное приведение требует произведения двойной ширины и явного шага приведения. Часто используется простое число, меньшее степени 2 ( простые числа Мерсенна 2 ³¹ −1 и 2 ⁶¹ −1 популярны), так что приведение по модулю m = 2 ^и − d можно вычислить как ( ax mod 2 ^и ) +  d  ⌊ ax /2 ^и ⌋ . За этим должно следовать условное вычитание m, если результат слишком велик, но количество вычитаний ограничено ad / m , которое можно легко ограничить одним, если d мало.

Если произведение двойной ширины недоступно и множитель выбран тщательно, метод Шраге можно использовать. Для этого множим m = qa + r , т.е. q = ⌊ m / a ⌋ и r = m mod a . Затем вычислите ax mod m знак равно a ( x mod q ) − r ⌊ x / q ⌋ . Поскольку x mod q < q ≤ m / a , первый член строго меньше am / a = m . Если a выбрано так, что r ≤ q (и, следовательно, r / q ≤ 1), то второй член также меньше m : r ⌊ x / q ⌋ ≤ rx / q = x ( r / q ) ≤ x < m . Таким образом, оба произведения могут быть вычислены с помощью произведения одинарной ширины, а разница между ними лежит в диапазоне [1− m , m −1], поэтому может быть уменьшена до [0, m −1] с помощью одного условного сложения. .

Второй недостаток заключается в том, что неудобно преобразовать значение 1 ≤ x < m в однородные случайные биты. Если используется простое число, меньшее степени 2, иногда недостающие значения просто игнорируются.

m степень 2, c = 0

Выбор m в качестве степени двойки , чаще всего m = 2. ³² или м = 2 ⁶⁴ , дает особенно эффективный LCG, поскольку позволяет вычислить операцию модуля путем простого усечения двоичного представления. Фактически, старшие биты обычно вообще не вычисляются. Однако есть и недостатки.

Эта форма имеет максимальный период m /4, достигаемый, если a ≡ ±3 (mod 8) и начальное состояние X ₀ нечетно. Даже в этом лучшем случае три младших бита X чередуются между двумя значениями и, таким образом, вносят в состояние только один бит. X всегда нечетно (младший бит никогда не меняется), и только один из следующих двух битов всегда изменяется. Если a ≡ +3, X чередуется ±1↔±3, а если a ≡ −3, X чередуется ±1↔∓3 (все по модулю 8).

Можно показать, что эта форма эквивалентна генератору с модулем m /4 и c ≠ 0.

Более серьезная проблема с использованием модуля степени двойки заключается в том, что младшие биты имеют более короткий период, чем старшие биты. Его простота реализации обусловлена ​​тем фактом, что старшие биты никогда не влияют на биты, поэтому младшие биты такого генератора образуют по модулю 2. ^б LCG сами по себе, повторяясь с периодом 2 ^{б -2} . Только самый старший бит X достигает полного периода.

m степень 2, c ≠ 0

Когда c ≠ 0, правильно выбранные параметры допускают период, равный m , для всех начальных значений. Это произойдет тогда и только тогда, когда :

1. $m$ и $c$ являются взаимно простыми,
2. $a-1$ делится на все простые множители $m$,
3. $a-1$ делится на 4, если $m$ делится на 4.

Эти три требования называются теоремой Халла – Добелла.

Эту форму можно использовать с любым m , но хорошо работает только для m со многими повторяющимися простыми множителями, например степенью 2; компьютера использование размера слова является наиболее распространенным выбором. Если бы m было целым числом без квадратов , это допускало бы только a ≡ 1 (mod m ), что делает ГПСЧ очень плохим; выбор возможных множителей полного периода доступен только в том случае, если m имеет повторяющиеся простые множители.

Хотя теорема Халла – Добелла обеспечивает максимальный период, этого недостаточно, чтобы гарантировать хороший генератор. Например, желательно, чтобы a - 1 не делилось на простые множители m больше , чем это необходимо. Если m — степень 2, то a − 1 должно делиться на 4, но не делиться на 8, т. е. a ≡ 5 (по модулю 8).

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

Обратите внимание, что модуль степени 2 разделяет проблему, описанную выше для c = 0: младшие k бит образуют генератор с модулем 2. ^к и таким образом повторяем с периодом 2 ^к ; только самый старший бит достигает полного периода. псевдослучайное число меньше r Если требуется , ⌊ rX / m ⌋ является результатом гораздо более высокого качества, чем X mod r . К сожалению, большинство языков программирования значительно упрощают написание последнего ( X % r), поэтому он очень часто используется.

Генератор не чувствителен к выбору c , пока он относительно прост по модулю (например, если m — степень 2, то c значение c должно быть нечетным), поэтому обычно выбирается =1.

Последовательность, полученную при другом выборе c, можно записать как простую функцию последовательности, когда c =1. В частности, если Y — прототипная последовательность, определяемая Y ₀ = 0 и Y _{n +1} = aY _n + 1 mod m, то общая последовательность X _{n +1} = aX _n + c mod m может быть записана как аффинная функция от Ю :

$X_{n}=(X_{0}(a-1)+c)Y_{n}+X_{0}=(X_{1}-X_{0})Y_{n}+X_{0}{\pmod {m}}.$

В более общем смысле любые две последовательности X и Z с одинаковым множителем и модулем связаны соотношением

${X_{n}-X_{0} \over X_{1}-X_{0}}=Y_{n}={a^{n}-1 \over a-1}={Z_{n}-Z_{0} \over Z_{1}-Z_{0}}{\pmod {m}}.$

В обычном случае, когда m является степенью 2 и a ≡ 5 (mod 8) (желательное свойство по другим причинам), всегда можно найти начальное значение X ₀ так, чтобы знаменатель X ₁ − X ₀ ≡ ± 1 (mod m ), что дает еще более простую зависимость. выборе X ₀ При таком X _n = X ₀ ± Y _n будет оставаться верным для всех n . Знак определяется c ≡ ±1 (mod 4), а константа X ₀ определяется 1 ∓ c ≡ (1 − a ) X ₀ (mod m ).

В качестве простого примера рассмотрим генераторы X _{n +1} = 157 X _n + 3 mod 256 и Y _{n +1} = 157 Y _n + 1 mod 256; т. е. m = 256, a = 157 и c = 3. Поскольку 3 ≡ −1 (mod 4), мы ищем решение для 1 + 3 ≡ (1 − 157) X ₀ (mod 256). Этому удовлетворяет X ₀ ≡ 41 (mod 64), поэтому, если мы начнём с этого, то X _n ≡ X ₀ − Y _n (mod 256) для всех n .

Например, используя X ₀ = 233 = 3×64 + 41:

• Х = 233, 232, 75, 2, 61, 108,...
• Y = 0, 1, 158, 231, 172, 125, ...
• X + Y по модулю 256 = 233, 233, 233, 233, 233, 233, ...

Параметры общего использования

В следующей таблице перечислены широко используемые параметры LCG, включая встроенные функции rand() в библиотеках времени выполнения различных компиляторов . Эта таблица призвана продемонстрировать популярность, а не примеры для подражания; многие из этих параметров плохие. Доступны таблицы хороших параметров.

Источник	модуль м	множитель а	приращение с	выводить начальные биты в rand() или Random(L)
ZX81	2 16 + 1	75	74
Численные рецепты ranqd1, Глава 7.1, §Еще более быстрый генератор, уравнение. 7.1.6 параметры от Кнута и Х.В. Льюиса	2 32	1664525	1013904223
Борланд С/С++	2 31	22695477	1	биты 30..16 в rand() , 30..0 в lrand()
glibc (используется GCC )	2 31	1103515245	12345	биты 30..0
ANSI C : Watcom , Digital Mars , CodeWarrior , IBM VisualAge C/C++. C90 , C99 , C11 : Предложения в ISO/IEC 9899, С17	2 31	1103515245	12345	биты 30..16
Борланд Делфи , Виртуальный Паскаль	2 32	134775813	1	биты 63..32 (начальное число × L)
Турбо Паскаль 4.0 и последующие.	2 32	134775813 (8088405 16 )	1
Microsoft Visual/Quick C/C++	2 31	214013 (343ФД 16 )	2531011 (269EC3 16 )	биты 30..16
Microsoft Visual Basic (6 и более ранние версии)	2 24	16598013 (ФД43ФД 16 )	12820163 (C39EC3 16 )
RtlUniform из Native API	2 31 − 1	−18 (7FFFFED 16 )	−60 (7FFFFFC3 16 )
Apple CarbonLib , C++ 11 minstd_rand0, Унаследованный генератор MATLAB v4 mcg16807	2 31 − 1	16807	0	см . МИНТД
С++ 11 minstd_rand	2 31 − 1	48271	0	см . МИНТД
MMIX Дональда Кнута	2 64	6364136223846793005	1442695040888963407
Ньюлиб	2 63	6364136223846793005	1	биты 62..32 (46..32 для 16-битного целого числа)
мусульманин	2 64	6364136223846793005	1	биты 63..33
VMS MTH $RANDOM , старые версии glibc	2 32	69069 (10DCD 16 )	1
Java java.util.Random, POSIX [ln]rand48, glibc [ln]rand48[_r]	2 48	25214903917 (5DEECE66D 16 )	11	биты 47..16
random0	134456 = 2 3 7 5	8121	28411	${\frac {X_{n}}{134456}}$
ПОСИКС [let]rand48, glibc [let]rand48[_r]	2 48	25214903917 (5DEECE66D 16 )	11	биты 47..0 или биты 47..15, по необходимости
cc65	2 23	65793 (10101 16 )	4282663 (415927 16 )	биты 22..8
cc65	2 32	16843009 (1010101 16 )	826366247 (31415927 16 )	биты 31..16
cc65	2 32	16843009 (1010101 16 )	3014898611 (Б3Б3Б3В3 16 )	предыдущие биты 31..16, текущие биты 31..16 xor биты 14..0
Ранее распространённое название: RANDU .	2 31	65539	0

Как показано выше, LCG не всегда используют все биты в создаваемых ими значениях. Обычно они возвращают наиболее значимые биты. Например, реализация Java на каждой итерации оперирует 48-битными значениями, но возвращает только 32 старших бита. Это связано с тем, что биты старшего порядка имеют более длинные периоды, чем биты младшего порядка (см. ниже). LCG, использующие этот метод усечения, дают статистически лучшие значения, чем те, которые этого не делают. Это особенно заметно в скриптах, использующих операцию модификации для уменьшения дальности; изменение мода 2 случайного числа приведет к чередованию 0 и 1 без усечения.

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

Преимущества и недостатки

LCG работают быстро и требуют минимального объема памяти (один модуль , часто 32 или 64 бита) для сохранения состояния. Это делает их ценными для моделирования нескольких независимых потоков. LCG не предназначены и не должны использоваться для криптографических приложений; используйте криптографически безопасный генератор псевдослучайных чисел для таких приложений .

Гиперплоскости линейного конгруэнтного генератора в трех измерениях. Эту структуру и измеряет спектральный тест .

Хотя у LCG есть несколько конкретных недостатков, многие из их недостатков связаны со слишком маленьким государством. Тот факт, что люди в течение стольких лет убаюкивали их использование с такими малыми модулями, можно рассматривать как свидетельство силы этой техники. LCG с достаточно большим состоянием может пройти даже строгие статистические тесты; по модулю-2 ⁶⁴ LCG, который возвращает старшие 32 бита, проходит TestU01 , пакет SmallCrush от а 96-битный LCG проходит самый строгий пакет BigCrush.

В конкретном примере ожидается, что идеальный генератор случайных чисел с 32-битным выходным сигналом (согласно теореме Дня рождения ) начнет дублировать более ранние выходные данные после √ m ≈ 2. ¹⁶ результаты. Любой ГПСЧ, выходные данные которого представляют собой его полное, необрезанное состояние, не будет создавать дубликаты до тех пор, пока не истечет его полный период, что является легко обнаруживаемым статистическим недостатком. По связанным с этим причинам любой ГПСЧ должен иметь период, превышающий квадрат количества требуемых выходных данных. Учитывая скорость современных компьютеров, это означает период 2 ⁶⁴ для всех приложений, кроме наименее требовательных, и дольше для требовательного моделирования.

Один недостаток, характерный для LCG, заключается в том, что, если его использовать для выбора точек в n-мерном пространстве, точки будут лежать не более чем на ^н √ n !⋅ m гиперплоскостей ( теорема Марсальи , развитая Джорджем Марсалья ). Это связано с последовательной корреляцией между последовательными значениями последовательности X _n . Небрежно выбранные множители обычно имеют гораздо меньше широко расположенных плоскостей, что может привести к проблемам. Спектральный тест , который представляет собой простой тест качества LCG, измеряет это расстояние и позволяет выбрать хороший множитель.

Расстояние между плоскостями зависит как от модуля, так и от множителя. Достаточно большой модуль может уменьшить это расстояние ниже разрешения чисел двойной точности. Выбор множителя становится менее важным, когда модуль велик. Спектральный индекс еще нужно вычислить и убедиться, что множитель неплохой, но чисто вероятностно становится крайне маловероятно встретить плохой множитель, когда модуль больше примерно 2. ⁶⁴ .

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

Тем не менее, для некоторых приложений LCG могут быть хорошим вариантом. Например, во встроенной системе объем доступной памяти часто сильно ограничен. Точно так же в такой среде, как игровая консоль, вполне может быть достаточно небольшого количества старших битов LCG. (Младшие биты LCG, когда m является степенью 2, никогда не следует полагаться на какую-либо степень случайности.) Младшие биты проходят через очень короткие циклы. В частности, любой LCG полного цикла, когда m является степенью 2, будет выдавать попеременно нечетные и четные результаты.

LCG следует очень тщательно оценивать на предмет их пригодности для некриптографических приложений, где высокое качество случайности имеет решающее значение. Для моделирования методом Монте-Карло LCG должен использовать модуль, больший и желательно намного больший, чем куб количества необходимых случайных выборок. Это означает, например, что (хороший) 32-битный LCG можно использовать для получения около тысячи случайных чисел; 64-битного LCG хватит примерно на 2 ²¹ случайные выборки (чуть более двух миллионов) и т. д. По этой причине на практике LCG не подходят для крупномасштабного моделирования Монте-Карло.

Пример кода

Код Python

Ниже приведена реализация LCG на Python в виде генератора :

from collections.abc import Generator

def lcg(modulus: int, a: int, c: int, seed: int) -> Generator[int, None, None]:
    """Linear congruential generator."""
    while True:
        seed = (a * seed + c) % modulus
        yield seed

Бесплатный Паскаль

Free Pascal использует Mersenne Twister в качестве генератора псевдослучайных чисел по умолчанию, тогда как Delphi использует LCG. Вот пример, совместимый с Delphi, в Free Pascal, основанный на информации из таблицы выше. Учитывая то же значение RandSeed, он генерирует ту же последовательность случайных чисел, что и Delphi.

unit lcg_random;
{$ifdef fpc}{$mode delphi}{$endif}
interface

function LCGRandom: extended; overload; inline;
function LCGRandom(const range:longint): longint; overload; inline;

implementation
function IM: cardinal; inline;
begin
  RandSeed := RandSeed * 134775813 + 1;
  Result := RandSeed;
end;

function LCGRandom: extended; overload; inline;
begin
  Result := IM * 2.32830643653870e-10;
end;

function LCGRandom(const range: longint): longint; overload; inline;
begin
  Result := IM * range shr 32;
end;

Как и всем генераторам псевдослучайных чисел, LCG необходимо сохранять состояние и изменять его каждый раз, когда генерирует новое число. Несколько потоков могут получить доступ к этому состоянию одновременно, вызывая состояние гонки. Реализации должны использовать разные состояния, каждое из которых имеет уникальную инициализацию для разных потоков, чтобы избежать одинаковых последовательностей случайных чисел при одновременном выполнении потоков.

Производные LCG

Существует несколько генераторов, которые являются линейными конгруэнтными генераторами в другой форме, и поэтому к ним можно применить методы, используемые для анализа LCG.

Одним из методов получения более длительного периода является суммирование выходных данных нескольких LCG разных периодов, имеющих большое наименьшее общее кратное ; генератор Вихмана – Хилла является примером этой формы. (Мы бы предпочли, чтобы они были полностью взаимно простыми , но простой модуль подразумевает четный период, поэтому должен быть как минимум общий делитель, равный 2.) Можно показать, что это эквивалентно одному LCG с модулем, равным произведение компонентных модулей LCG.

Марсальи ГПСЧ «сложение с переносом» и «вычитание с заимствованием» с размером слова b = 2 ^В и лаги r и s ( r > s ) эквивалентны LCG с модулем b ^р ± б ^с  ± 1.

ГПСЧ умножения с переносом с множителем a эквивалентны LCG с большим простым модулем ab. ^р −1 и множитель степени 2 b .

начинается Конгруэнтный генератор с перестановкой с LCG со степенью 2 модуля и применяет выходное преобразование для устранения проблемы короткого периода в младших битах.

Сравнение с другими ГПСЧ

Другим широко используемым примитивом для получения псевдослучайных последовательностей с большим периодом является конструкция регистра сдвига с линейной обратной связью , которая основана на арифметике в GF(2)[ x ], кольце полиномов над GF(2) . Вместо сложения и умножения целых чисел основными операциями являются умножение с исключающим или и без переноса , которое обычно реализуется как последовательность логических сдвигов . Их преимущество состоит в том, что все их биты имеют полный период; они не страдают от слабости младших битов, от которой страдает арифметика по модулю 2. ^к .

Примеры этого семейства включают генераторы xorshift и твистер Мерсенна . Последний обеспечивает очень длительный период (2 ¹⁹⁹³⁷ −1) и варьирует однородность, но не проходит некоторые статистические тесты. Генераторы Фибоначчи с запаздыванием также попадают в эту категорию; хотя они используют арифметическое сложение, их период обеспечивается LFSR среди младших битов.

Структуру регистра сдвига с линейной обратной связью легко обнаружить с помощью соответствующих тестов. например, тест линейной сложности, реализованный в пакете TestU01 ; булева циркулянтная матрица, инициализированная последовательными битами LFSR, никогда не будет иметь ранг выше степени полинома. Добавление функции нелинейного выходного микширования (как в конструкции xoshiro256** и перестановочных конгруэнтных генераторов ) может значительно улучшить производительность статистических тестов.

Другая структура ГПСЧ — это очень простая функция повторения в сочетании с мощной функцией выходного микширования. Сюда входят блочные шифры в режиме счетчика и некриптографические генераторы, такие как SplitMix64 .

Структура, аналогичная LCG, но не эквивалентная ей, представляет собой многорекурсивный генератор: X _n = ( a ₁ X _{n −1} + a ₂ X _{n −2} + ··· + a _k X _{n − k} ) mod m for k ≥ 2. При простом модуле это может генерировать периоды до m. ^к −1, а также полезное расширение структуры LCG на более крупные периоды.

Мощный метод генерации высококачественных псевдослучайных чисел — объединение двух или более ГПСЧ различной структуры; сумма LFSR и LCG (как в конструкциях KISS или xorwow ) может работать очень хорошо при некоторой стоимости скорости.

См. также

• Список генераторов случайных чисел - другие ГПСЧ, в том числе с лучшими статистическими качествами.
• Генератор ACORN - не путать с ACG, этот термин, по-видимому, использовался для вариантов генераторов LCG и LFSR.
• Перестановочный конгруэнтный генератор
• Полный цикл
• Инверсивный конгруэнтный генератор
• Умножение с переносом
• ГСЧ Лемера (иногда называемый ГСЧ Парка – Миллера)
• Комбинированный линейный конгруэнтный генератор

Ссылки

• Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007), «Раздел 7.1.1. Немного истории» , Числовые рецепты: искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN  978-0-521-88068-8 , заархивировано из оригинала 11 августа 2011 г. , получено 10 августа 2011 г.
• Нежный, Джеймс Э. (2003). Генерация случайных чисел и методы Монте-Карло , 2-е издание, Springer, ISBN   0-387-00178-6 .
• Джоан Бояр (1989). «Вывод последовательностей, созданных генераторами псевдослучайных чисел» (PDF) . Журнал АКМ . 36 (1): 129–141. дои : 10.1145/58562.59305 . S2CID   3565772 . (в этой статье приведены эффективные алгоритмы вывода последовательностей, созданных некоторыми генераторами псевдослучайных чисел).

Внешние ссылки

• моделирования Линейный конгруэнтный генератор визуализирует корреляции между псевдослучайными числами при манипулировании параметрами.
• Безопасность генерации случайных чисел: аннотированная библиография
• Сообщение о линейных конгруэнтных генераторах на sci.math
• Проект компьютерного искусства «Смерть искусства» компании Goldstein Technologies LLC использует LCG для создания 33 554 432 изображений.
• П. Л'Экуайер и Р. Симард, «TestU01: Библиотека AC для эмпирического тестирования генераторов случайных чисел» , май 2006 г., исправлено в ноябре 2006 г., Транзакции ACM в математическом программном обеспечении , 33, 4, статья 22, август 2007 г.
• Статья о другом способе взлома LCG