Алгоритм Блюма, Блюма и Шуба (Blum Blum Shub, bbs)

Предложен в 1986 году Ленор и Мануэлем Блюм и Майклом Шубом.

BBS заключается в применении следующей формулы :

x_n+1 = (x_n)² mod M,

где M=p*q является произведением двух больших простых p и q.

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

Два простых числа, p и q, должны быть оба сравнимы с 3 по модулю 4 и НОД(φ(p-1), φ(q-1)) должен быть мал.

Интересной особенностью этого алгоритма является то, что для получения x_n необязательно вычислять все n - 1 предыдущих чисел, если известно начальное состояние генератора x₀ и числа p и q. n-ное значение может быть вычислено "напрямую" используя формулу :

x_n = x₀ ^{(2 ^ n) mod ((p-1)(q-1))} mod M

Надёжность

Этот генератор подходит для криптографии, но не для моделирования, потому что он недостаточно быстр. Однако, он имеет необычно высокую стойкость, которая обеспечивается качеством генератора исходя из вычислительной сложности задачи факторизации чисел. Когда простые числа выбраны осторожно, и O (loglogM) бит каждого x_n являются выходными данными, тогда предел взятый как M быстро растёт, и вычисление выходных бит будет настолько же трудно, как и факторизация M.

Если факторизация целых чисел так трудна, тогда BBS с большим M будет иметь выход, свободный от любых неслучайных шаблонов, которые могут быть выявлены при достаточном объёме вычислений. Однако, возможно появление быстрого алгоритма для факторизации, и вследствие этого BBS не является гарантированно надёжным.

Критерии случайности Статистические параметры

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

— математическое ожидание;

— дисперсия;

— среднеквадратичное отклонение.

Частотный тест

Частотный тест позволяет выяснить, сколько чисел попало в интервал (m_r – σ_r; m_r + σ_r), то есть (0.5 – 0.2887; 0.5 + 0.2887) или, в конечном итоге, (0.2113; 0.7887). Так как 0.7887 – 0.2113 = 0.5774, заключаем, что в хорошем ГСЧ в этот интервал должно попадать около 57.7% из всех выпавших случайных чисел (см. рис. 1).

Рис. 1. Частотная диаграмма идеального ГСЧ в случае проверки его на частотный тест

Также необходимо учитывать, что количество чисел, попавших в интервал (0; 0.5), должно быть примерно равно количеству чисел, попавших в интервал (0.5; 1).

Проверка по критерию «хи-квадрат»

Критерий «хи-квадрат» (χ²-критерий) — это один из самых известных статистических критериев; он является основным методом, используемым в сочетании с другими критериями. Критерий «хи-квадрат» был предложен в 1900 году Карлом Пирсоном. Его замечательная работа рассматривается как фундамент современной математической статистики.

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

Частотная диаграмма эталонного ГСЧ представлена на рис. 2. Так как закон распределения эталонного ГСЧ равномерный, то (теоретическая) вероятность p_i попадания чисел в i-ый интервал (всего этих интервалов k) равна p_i = 1/k. И, таким образом, в каждый из k интервалов попадет ровно по p_i · N чисел (N — общее количество сгенерированных чисел).

Рис. 2. Частотная диаграмма эталонного ГСЧ

Реальный ГСЧ будет выдавать числа, распределенные (причем, не обязательно равномерно) по k интервалам и в каждый интервал попадет по n_i чисел (в сумме n₁ + n₂ + … + n_k = N). Как же нам определить, насколько испытываемый ГСЧ хорош и близок к эталонному? Вполне логично рассмотреть квадраты разностей между полученным количеством чисел n_i и «эталонным» p_i · N. Сложим их, и в результате получим:

χ²_эксп. = (n₁ – p₁ · N)² + (n₂ – p₂ · N)² + … + (n_k – p_k · N)².

Из этой формулы следует, что чем меньше разность в каждом из слагаемых (а значит, и чем меньше значение χ²_эксп.), тем сильнее закон распределения случайных чисел, генерируемых реальным ГСЧ, тяготеет к равномерному.

В предыдущем выражении каждому из слагаемых приписывается одинаковый вес (равный 1), что на самом деле может не соответствовать действительности; поэтому для статистики «хи-квадрат» необходимо провести нормировку каждого i-го слагаемого, поделив его на p_i · N:

Наконец, запишем полученное выражение более компактно и упростим его:

Мы получили значение критерия «хи-квадрат» для экспериментальных данных.

В табл. 1 приведены теоретические значения «хи-квадрат» (χ²_теор.), где ν = N – 1 — это число степеней свободы, p — это доверительная вероятность, задаваемая пользователем, который указывает, насколько ГСЧ должен удовлетворять требованиям равномерного распределения, или p — это вероятность того, что экспериментальное значение χ²_эксп. будет меньше табулированного (теоретического) χ²_теор. или равно ему.

Некоторые процентные точки χ²-распределения

Таблица 1.

	p = 1%	p = 5%	p = 25%	p = 50%	p = 75%	p = 95%	p = 99%
ν = 1	0.00016	0.00393	0.1015	0.4549	1.323	3.841	6.635
ν = 2	0.02010	0.1026	0.5754	1.386	2.773	5.991	9.210
ν = 3	0.1148	0.3518	1.213	2.366	4.108	7.815	11.34
ν = 4	0.2971	0.7107	1.923	3.357	5.385	9.488	13.28
ν = 5	0.5543	1.1455	2.675	4.351	6.626	11.07	15.09
ν = 6	0.8721	1.635	3.455	5.348	7.841	12.59	16.81
ν = 7	1.239	2.167	4.255	6.346	9.037	14.07	18.48
ν = 8	1.646	2.733	5.071	7.344	10.22	15.51	20.09
ν = 9	2.088	3.325	5.899	8.343	11.39	16.92	21.67
ν = 10	2.558	3.940	6.737	9.342	12.55	18.31	23.21
ν = 11	3.053	4.575	7.584	10.34	13.70	19.68	24.72
ν = 12	3.571	5.226	8.438	11.34	14.85	21.03	26.22
ν = 15	5.229	7.261	11.04	14.34	18.25	25.00	30.58
ν = 20	8.260	10.85	15.45	19.34	23.83	31.41	37.57
ν = 30	14.95	18.49	24.48	29.34	34.80	43.77	50.89
ν = 50	29.71	34.76	42.94	49.33	56.33	67.50	76.15
ν > 30	ν + sqrt(2ν) · xp + 2/3 · x2p – 2/3 + O(1/sqrt(ν))
xp =	–2.33	–1.64	–0.674	0.00	0.674	1.64	2.33

Приемлемым считают p от 10% до 90%.

Если χ²_эксп. много больше χ²_теор. (то есть p — велико), то генератор не удовлетворяет требованию равномерного распределения, так как наблюдаемые значения n_i слишком далеко уходят от теоретических p_i · N и не могут рассматриваться как случайные. Другими словами, устанавливается такой большой доверительный интервал, что ограничения на числа становятся очень нежесткими, требования к числам — слабыми. При этом будет наблюдаться очень большая абсолютная погрешность.

Еще Д. Кнут в своей книге «Искусство программирования» заметил, что иметь χ²_эксп. маленьким тоже, в общем-то, нехорошо, хотя это и кажется, на первый взгляд, замечательно с точки зрения равномерности. Действительно, возьмите ряд чисел 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, … — они идеальны с точки зрения равномерности, и χ²_эксп. будет практически нулевым, но вряд ли вы их признаете случайными.

Если χ²_эксп. много меньше χ²_теор. (то есть p — мало), то генератор не удовлетворяет требованию случайного равномерного распределения, так как наблюдаемые значения n_i слишком близки к теоретическим p_i · N и не могут рассматриваться как случайные.

А вот если χ²_эксп лежит в некотором диапазоне, между двумя значениями χ²_теор., которые соответствуют, например, p = 25% и p = 50%, то можно считать, что значения случайных чисел, порождаемые датчиком, вполне являются случайными.

При этом дополнительно надо иметь в виду, что все значения p_i · N должны быть достаточно большими, например больше 5 (выяснено эмпирическим путем). Только тогда (при достаточно большой статистической выборке) условия проведения эксперимента можно считать удовлетворительными.

Итак, процедура проверки имеет следующий вид.

1. Диапазон от 0 до 1 разбивается на k равных интервалов.

2. Запускается ГСЧ N раз (N должно быть велико, например, N/k > 5).

3. Определяется количество случайных чисел, попавших в каждый интервал: n_i, i = 1, …, k.

4. Вычисляется экспериментальное значение χ2эксп. по следующей формуле:

где p_i = 1/k — теоретическая вероятность попадания чисел в k-ый интервал.

5. Путем сравнения экспериментально полученного значения χ²_эксп. с теоретическим χ²_теор. (из табл. 1) делается вывод о пригодности генератора для использования. Для этого: а) входим в табл. 1 (строка = количество экспериментов – 1); б) сравниваем вычисленное χ²_эксп с χ²_теор., встречающимися в строке. При этом возможно три случая.

Первый случай: χ²_эксп много больше любого χ²_теор. в строке — гипотеза о случайности равномерного генератора не выполняется (разброс чисел слишком велик, чтобы быть случайным).

Второй случай: χ²_эксп много меньше любого χ²_теор. в строке — гипотеза о случайности равномерного генератора не выполняется (разброс чисел слишком мал, чтобы быть случайным).

Третий случай: χ²_эксп лежит между значениями χ²_теор. двух рядом стоящих столбцов — гипотеза о случайности равномерного генератора выполняется с вероятностью p (то есть в p случаях из 100). Следует заметить, что чем ближе получается p к значению 50%, тем лучше.

Задача

Допустим, что нам нужен список чисел от 1 до N в случайном порядке.

Для этого воспользуемся линейным конгруэнтным методом генерации псевдослучайных чисел (см. Приложение 1) и алгоритмом Блюма, Блюма и Шуба (см. Приложение 2)