Почему функции rand и lrand48 из glibc годятся только для Тетриса: о случайных числах всерьёз / Хабр

Функцию rand из стандартной библиотеки языка Си для генерации псевдослучайных чисел, наверное, не ругал только ленивый. В довольно известном докладе Rand considered harmful рассказывалось о проблемах с переносимостью, ограниченным диапазоном, многопоточностью, качеством и т.п. Иногда в учебниках упоминают о том, что алгоритм в rand может быть не очень качественным, иметь проблемы с младшими битами, периодом, прохождением статистических тестов. Но крайне редко можно увидеть разбор конкретных критериев, выявляющих дефекты генераторов. В этой статье я постараюсь наглядно показать не просто отдельные недостатки rand, lrand48 и random из glibc, но их полную непригодность для каких-либо вычислений в принципе. Также вы увидите превосходство поточных шифров над minstd, линейным конгруэнтным генератором из 1980-х, не только в качестве, но и в производительности.

Введение
Алгоритмы glibc
Статистические тесты
О документации и учебниках
Хорошие учебные генераторы
Возможные пути улучшения ситуации и шифры
Рекомендации по выбору генератора

Введение

Начнём с того, что все три рассматриваемые функции генерируют не истинно случайные, а псевдослучайные числа. Т.е. в них реализованы генераторы псевдослучайных чисел (ГПСЧ) — алгоритмы, выдающие полностью детерминированные последовательности, которые лишь внешне похожи на случайные числа, подчиняющиеся равномерному распределению. Одно и то же начальное состояние (seed, затравка, «зерно» и т.п.) приводят к одной и той же последовательности. Само по себе это не так уж и плохо: возможность воспроизвести весь расчёт по начальным условиям - это скорее достоинство. И в т.ч. поэтому ГПСЧ широко используются в научных и инженерных расчётах: методе Монте-Карло, нелиненой оптимизации, машинном обучении. Проблема с некриптографическими генераторами glibc лишь одна — их крайне низкое качество.

Перед использов��нием какого-либо ГПСЧ нужно убедиться в том, что выдаваемая им последовательность подчиняется равномерному распределению. Обычно в учебниках по теории вероятности и статистике описываются критерии Пирсона (хи-квадрат), Колмогорова-Смирнова, Андерсона-Дарлинга. Но их совершенно недостаточно для контроля качества ГПСЧ, т.к. нужно искать не просто неравномерность распределения, а скрытые регулярности, вносимые алгоритмами: решетчатые структуры, зависимости между битами и т.п. Поэтому для контроля качества ГПСЧ существуют специализированные батареи статистических тестов, среди которых наиболее значимы TestU01 и PractRand. Типичная проверка генератора требует выборки размером несколько десятков терабайт и 2-3 дня расчётов на обычном ПК. TestU01 уже даже есть в пакетах Ubuntu. Разумеется, ни rand, ни lrand48 из glibc этих батарей не пройдут и провалят их за секунды. Хотя они представляют собой скорее базовые проверки на равномерность распределения, чем углубленный поиск тонких дефектов, последним занимаются криптоаналитики. Можно было бы просто проверить функции из glibc с помощью TestU01, ужаснуться и сделать соответствующие выводы. Но использование готовых тестов как «чёрного ящика» не даёт понимания природы проблемы и того, почему эти генераторы нельзя
применять для расчётов. Поэтому мы напишем простейшие статистические тесты сами.

Мой интерес к теме генераторов псевдослучайных чисел начался с подготовки дополнительных материалов для университетского курса по статистической обработке эксперимента для естественных факультетов МГУ. ГПСЧ нередко бывают на нём нужны для генерации учебных выборок, оценки погрешности косвенного измерения, интегрирования и оценки квантилей распределений по Монте-Карло, задач глобальной оптимизации. Изначально я их воспринимал как загадочные «чёрные ящики» с не менее загадочными критериями качества. Когда я начинал изучать ГПСЧ, то не подозревал, насколько глубока «кроличья нора», и сколько в этой сфере бардака. В итоге примеры кода постепенно превратились в SmokeRand — фреймворк для тестирования ГПСЧ с обширной коллекцией генераторов. Конечно, при работе в Python или MATLAB мы большей частью защищены от бардака создателями стандартной библиотеки языка, но мне как химику-вычислителю нередко приходится иметь дело с C и С++, в которых уже нужно точно знать, что именно используешь. Исходный код как SmokeRand, так и примеров из статьи можно найти по ссылкам:

Алгоритмы glibc

Прежде чем переходить к тестам, ознакомимся с тем, качество чего нам предстоит испытывать. В функциях glibc rand и random по умолчанию используется аддитивный генератор Фибоначчи с запаздыванием (англ. additive lagged Fibonacci generator):

$x_{n} = x_{n-31} + x_{n-3} \mod 2^{32}$

Функции возвращают старшие 31 бит $x_{n}$ . Первые 31 значение инициализируются линейным конгруэнтным генератором minstd на основе переданной через srand «затравки» (seed). Данный алгоритм пришёл в glibc из какой-то версии BSD середины 80-х годов XX века. Да, согласно стандарту языка C значение RAND_MAX для функции rand может зависеть от платформы, но мы пишем тесты для конкретной стандартной библиотеки и конкретной операционной системы. При желании примеры из статьи можно адаптировать и к другим значениям RAND_MAX.

В lrand48 используется линейный конгруэнтный генератор с 48-битным состоянием:

$x_{n} = \mathrm{5DEECE66D}_{16}\cdot x_{n-1} + \mathrm{B}_{16} \mod 2^{48}$

Функция возвращает старшие 31 бит $x_{n}$ .Также добавим в нашу выборку 64-битный линейный конгруэнтный генератор с возвратом старших 31 бит:

$x_{n} = 6906969069 x_{n-1} + 123456789 \mod 2^{64}$

И в этом случае тоже будем анализировать старшие 31 бит. Хорошо запоминающийся множитель взят из рекомендаций Дж. Марсальи, всемирно известного специалиста по генераторам псевдослучайных чисел. Этот генератор интересен своим сходством с ГПСЧ, используемыми в musl (аналогичный размер состояния, но другие константы) и в msvcrt (LCG, изначально разработанный для GW-BASIC, и с очень коротким 24-битным состоянием).

В качестве эталона мы будем использовать системный криптогенератор (CSPRNG), доступный через функции getrandom, arc4random, а также через устройство /dev/urandom. Также чтобы показать, что наши тесты — это не заоблачные требования «для криптографии», а базовые проверки на равномерность распределения, испытаем качество такого генератора:

$u_{n} = 29386\left(x_{n-3} + x_{n-2}\right) + c_{n-1}$ $x_{n} = u_{n} \mod 2^{32};~ c_{n} = \lfloor\dfrac{u_n}{2^{32}}\rfloor$

Начальные три «икса» — любые, начальное установить в 12345. Он был сделан мной на основе 32-битной Mother-of-All и RWC Дж. Марсальи как учебный ГПСЧ для реализации прямо в ячейках MS Excel или LibreOffice Calc. Не знаю, насколько на самом деле он качественный, но BigCrush и 32 ТиБ, PractRand 0.94 и батарею full моего SmokeRand он выдержал, период — около $2^{109}$ , «плохих бит» с малым периодом и/или низкой линейной сложностью у него быть не должно.

Статистические тесты

В Википедии и учебниках любят показывать картинку с точками на нескольких плоскостях, полученную для RANDU. Иногда можно увидеть испорченные рандомграммы для MWC1616, ГПСЧ из старых версий JavaScript. Но во многих случаях такого наглядного изображения продемонстрировать не получится (например, если дефект виден только на больших выборках, в многомерных пространствах и т.п.) И нужны объективные статистические тесты. Для их реализации нам понадобится GNU/Linux (можно в виртуальной машине или даже WSL), компилятор C99, а также Python 3.x с numpy, sympy и matplotlib.

Далее мы рассмотрим два теста: критерий интервалов (англ. gap test) и критерий промежутков между днями рождения (англ. birthday spacings test). Начнём с критерия интервалов, т.к. в нём проблема с генератором из glibc видна чисто визуально, без «навороченных» формул. А затем перейдём к более сложному критерию промежутков между днями рождения.

Критерий интервалов (gap test)

По-видимому, впервые критерий интервалов был впервые предложен в работе Kendall и Smith в 1938 г., а затем популяризован для испытаний ГПСЧ в «Искусстве программирования» Кнута. Классический критерий интервалов работает так:

Задаётся какой-то отрезок, покрывающий часть диапазона генерируемых чисел.
Попадающие в отрезок члены последовательности заменяются на 1, не попадающие — 0.
Ведётся таблица частот интервалов различной длины между единицами. Например, в последовательности есть интервалы длиной 2, 0, 2 и 1.
Полученное распределение сравнивается с теоретическим по критерию Пирсона (хи-квадрат).

Мы применим тест к функции rand и к системному криптографическому генератору. Критерием попадания внутрь отрезка будем считать равенство 0 старших 10 бит числа. Если бы наш генератор выдавал бы числа с плавающей запятой в интервале , то условие было бы эквивалентно попаданию в интервал $[0;2^{-10}]$ . Исходный код программы на C (gap_test.c):

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <time.h>
#include <sys/random.h>

int main()
{
  const size_t gap_len_max = 1000;
  long long prev_gap = -1;
  long long *freq = calloc(gap_len_max + 1, sizeof(long long));
  srand(arc4random());
  for (long long i = 0; i < 1LL << 31; i++) {
    const uint32_t u = (uint32_t)rand();
    if (u >> 21 == 0) {
      if (prev_gap != -1) {
        long long gap_len = i - prev_gap - 1;
        if (gap_len <= (long long) gap_len_max) {
          freq[gap_len]++;
        }
      }
      prev_gap = i;      
    }
  }
  FILE *fp = fopen("out.csv", "wt");
  if (fp == NULL) {
    fprintf(stderr, "Cannot open the output file. Using stdout\n");
    fp = stdout;
  }
  for (size_t i = 0; i <= gap_len_max; i++) {
    fprintf(fp, "%ld,%ld\n", (unsigned long) i, (unsigned long) freq[i]);
  }
  if (fp != stdout) { fclose(fp); }
  free(freq);
  return 0;
}

Построим график по полученной таблице частот с помощью такой программы на Python:

import numpy as np
import matplotlib.pyplot as plt
data = np.loadtxt('out.csv', delimiter=',')
n, Oi = data[:,0], data[:,1]
print(data[25:35,:])
plt.plot(n, Oi, 'k-')
plt.show()
plt.plot(n[n < 100], Oi[n < 100], 'k-')
plt.show()

Помимо визуализации программа выводит в консоль фрагмент таблицы частот, в котором виден провал для .

[[  25. 1915.]
 [  26. 1973.]
 [  27. 2016.]
 [  28. 1963.]
 [  29. 1982.]
 [  30.  952.]
 [  31. 1938.]
 [  32. 1944.]
 [  33. 2045.]
 [  34. 1986.]]

Этот же провал виден как резкий пик на графике. И пик на графике, и провал в таблице соответствуют одному из запаздываний исследуемого генератора Фибоначчи длиной 31.

Распределение частотинтервалов длиныв результате применения критерия интервалов к аддитивному генератору Фибоначчи. Виден характерный пик для.

Если заменить его на системный криптографический генератор (arc4random), то артефакт пропадает:

Распределение частотинтервалов длиныв результате применения критерия интервалов к системному криптографическому генератору. Пик-артефакт исчез.

Мы не будем рассчитывать теоретические частоты, применять критерий Пирсона и вычислять p-значения: желающие могут проделать это самостоятельно, обратившись ко второму тому «Искусства программирования». Существуют модификации критерия интервалов, выявляющие дефекты аддитивных и субтрактивных генераторов Фибоначчи даже при очень больших запаздываниях/лагах порядка десятков тысяч. Они включены в gjrand (тест rda16) и SmokeRand (тест gap16_count0). Для борьбы с этим явлением нужно либо увеличивать число слагаемых в сумме хотя бы до трёх, либо добавлять выходную функцию-скремблер. А ещё лучше вообще перейти к мультипликативным генераторам Фибоначчи, но работающими с 64-битными целыми и выдающими только старшие 32 бита.

Использование критерия интервалов для поиска подобных дефектов ГПСЧ — это не просто милая академическая забава: в статье Ferrenberg, Landau и Wong «Monte Carlo simulations: Hidden errors from „good“ random number generators» описано, как такие артефакты генераторов приводили к ошибкам в теоретико-физических вычислениях методом Монте-Карло, а именно в расчёте внутренней энергии и теплоемкости в двухмерной модели Изинга. Мне удалось воспроизвести большинство результатов из этой работы, см. специализированную батарею тестов ising из SmokeRand. Хотя модель Изинга может показаться чем-то узкоспециализированным и оторванным от жизни, похожий паттерн использования ГПСЧ довольно часто встречается в методе имитации отжига, алгоритме Метрополиса-Гастингса и т.п. Не исключено даже влияние на такую простейшую задачу, как оценку погрешности косвенного измерения. Т.е. в функциях rand и random мы имеем дело не просто с посредственным алгоритмом, а с чем-то совершенно непригодным для любых научных и инженерных расчётов.

В начале 1990-х гг. искажённые результаты симуляции модели Изинга методом Монте-Карло произвели на физиков-теоретиков из CERN настолько неизгладимое впечатление, что Мартином Люшером был предложен RANLUX — линейный конгруэнтный генератор с размером состояния 576 бит, простым делителем и высококачественным множителем. Это — один из первых ГПСЧ, проходящий современные статистические тесты, из более ранних генераторов со сколь-либо приемлемой производительностью подобным могут похвастаться разве что DES-CBC и Магма-CBC. Даже сейчас RANLUX может быть в 10 и более раз медленнее аппаратно ускоренных AES и ChaCha, но вычислители были готовы платить такую цену за качественные псевдослучайные последовательности.

Интересно то, что lrand48 критерию интервалов обычно удовлетворяет (проверьте это самостоятельно), и может появиться вредная иллюзия о его приемлемом качестве. Но мы сейчас её развеем другим простым статистическим тестом, который ни rand, ни lrand48 «не переживут».

Критерий промежутков между днями рождения (birthday spacings test)

Мы уже говорили о том, что в случае RANDU плоскости из точек видны сразу. Но уже для rand и lrand48 их невооруженным глазом не разглядеть. Искать подобные аномалии автоматически нам поможет критерий промежутков между днями рождения. Он предложен Дж. Марсальей в середине 1980-х гг., наиболее удачное и наглядное описание было им дано в статье 2003 г. Some Difficult-to-pass Tests of Randomness. Для его использования нужно выполнить следующие шаги:

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

Число найденных дубликатов приближенно подчиняется распределению Пуассона со следующим математическим ожиданием:

$\lambda = \frac{m^3}{4n}$

где - это размер выборки, а — число всех возможных значений члена последовательности (для числа из бит ). В статье Марсальи и называются соответственно «числом дней рождения» и «числом дней в году». Для повышения чувствительности тест повторяют раз и складывают полученное число дубликатов. Сумма также подчиняется распределению Пуассона. Запустим тест в трёх режимах:

Одномерный: для 31-битных значений от ГПСЧ.
Двухмерный: для 62-битных значений, полученных «склейкой» пары членов последовательности.
Восьмимерный: 64-битное значение, полученное «склейкой» 8 младших байт 8 членов последовательности.

Размер выборки будем задавать исходя из условий $\lambda=8$ и $n=2^{31}$ . Чтобы не реализовывать интегральную функцию распределения Пуассона, заменим её на интегральную функцию нормального распределения. Такое приближение можно обосновать центральной предельной теоремой. Возможно, с точки зрения математиков это и неправильно, но нас интересует лишь грубая прикидка p-значения для обнаружения его выпадения из интервала $\left[10^{-10};1-10^{-10}\right]$ . Использовать более привычные мягкие пороги вроде 0.05 здесь бессмысленно, т.к. будут ложные провалы теста в 1 из 20 случаев, и проще увеличить размер выборки, а не заниматься трюкачеством и подгонкой (p-hacking). При желании более точные функции для расчёта p-значений можно взять из GSL или даже из исходного кода SmokeRand.

Перед переходом к реальным испытаниям генераторов попробуем через простой пример понять интуитивно, на что реагирует критерий промежутков между днями рождения. Для этого применим его к прогрессии вида $x_{n+1} = x_n + 137 \mod 256$ (модель низкокачественного линейного конгруэнтного генератора) в следующем скрипте на Python:

import numpy as np
import random
m = 10
x, state = np.zeros(m, dtype=np.int32), 19
for i in range(m):
    state = (state + 137) % 256
    #state = random.randint(0, 255)
    x[i] = state
xsorted = np.sort(x)
print("x:        ", x)
print("xsorted:  ", xsorted)
delta = xsorted[1:] - xsorted[:-1]
delta_sorted = np.sort(delta)
print("d:        ", delta)
print("d_sorted: ", delta_sorted)

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

x:         [115 252 133  14 151  32 169  50 187  68]
xsorted:   [ 14  32  50  68 115 133 151 169 187 252]
d:         [18 18 18 47 18 18 18 18 65]
d_sorted:  [18 18 18 18 18 18 18 47 65]

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

Результаты применения критерия промежутков между днями рождения к последовательности $x_{i+1}=x_i + 137 \mod 256$

Результаты применения критерия промежутков между днями рождения к последовательности $x_{i+1}=x_i + 137 \mod 256$

Если раскомментировать строчку с вызовом ГПСЧ из стандартной библиотеки Python, то результаты будут совсем другими, с куда меньшим числом одинаковых интервалов:

x:         [200  85  71  67   7 210 237 122 195 194]
xsorted:   [  7  67  71  85 122 194 195 200 210 237]
d:         [60  4 14 37 72  1  5 10 27]
d_sorted:  [ 1  4  5 10 14 27 37 60 72]

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

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

Теперь перейдём к испытаниям настоящих генераторов псевдослучайных чисел. Исходный код теста (bspace_test.c):

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>
#include <time.h>
#include <sys/random.h>

typedef uint32_t(*randfunc_t)();
typedef void(*arrayfunc_t)(uint64_t *, size_t, randfunc_t);

uint32_t rand_env()     { return (uint32_t) rand(); }
uint32_t lrand48_env()  { return (uint32_t) lrand48(); }

uint32_t csprng_env()
{
  static uint32_t x[64], pos = 64;
  if (pos == 64) {
    pos = 0;
    if (getrandom(x, 256, 0) == -1) {
      fprintf(stderr, "getrandom failure\n");
      exit(1);
    }
  }
  return x[pos++] >> 1;
}

uint32_t rwc_env()
{
  static uint32_t x = 0, y = 0, z = 0, c = 12345;
  const uint64_t prod = 29386U * ((uint64_t)y + z) + c;
  z = y; y = x;
  x = (uint32_t) prod; c = (uint32_t) (prod >> 32);
  return x >> 1;
}

uint32_t lcg64_env()
{
    static uint64_t x = 0;
    x = 6906969069U * x + 123456789U;
    return (uint32_t) (x >> 33);
}

int cmp_u64(const void *aptr, const void *bptr)
{
  const uint64_t a = *((const uint64_t *)aptr);
  const uint64_t b = *((const uint64_t *)bptr);
  if (a > b)       { return 1; }
  else if (a == b) { return 0; }
  else             { return -1; }
}

size_t calc_npoints(double lambda, double nvariants)
{
  return (size_t) pow(nvariants * 4.0 * lambda, 1.0 / 3.0);
}

void fill_array_1d(uint64_t *x, size_t len, randfunc_t rand_func)
{
  for (size_t i = 0; i < len; i++) { x[i] = rand_func(); }
}

void fill_array_2d(uint64_t *x, size_t len, randfunc_t rand_func)
{
  for (size_t i = 0; i < len; i++) {
    x[i] = rand_func(); x[i] <<= 31;
    x[i] |= rand_func();
  }
}

void fill_array_8d(uint64_t *x, size_t len, randfunc_t rand_func)
{
  for (size_t i = 0; i < len; i++) {
    x[i] = 0;
    for (size_t j = 0; j < 8; j++) {
      x[i] <<= 8; x[i] |= rand_func() & 0xFF;
    }
  }
}

unsigned long calc_bspace_ndups(uint64_t *x, size_t len)
{
  qsort(x, len, sizeof(uint64_t), cmp_u64);
  for (size_t i = 0; i < len - 1; i++) { x[i] -= x[i + 1] }
  unsigned long ndups = 0;
  qsort(x, len - 1, sizeof(uint64_t), cmp_u64);
  for (size_t i = 0; i < len - 2; i++) {
    if (x[i] == x[i + 1]) { ndups++; }
  }
  return ndups;
}

double normcdf(double x)
{
  return 0.5 * (1.0 + erf(x / sqrt(2.0)));
}

double calc_probability(unsigned long ndups, unsigned int nsamples, double lambda)
{
  const double mean = lambda * (double)nsamples;
  const double std = sqrt(mean);
  return normcdf(((double)ndups - mean) / std);
}

void run_bspace(double lambda, unsigned int nsamples, double nvariants,
  arrayfunc_t fill_array_func, randfunc_t rand_func)
{
  const size_t npoints = calc_npoints(lambda, nvariants);
  unsigned long ndups = 0;
  uint64_t *x = calloc(npoints, sizeof(uint64_t));
  for (unsigned int i = 0; i < nsamples; i++) {
    fill_array_func(x, npoints, rand_func);
    ndups += calc_bspace_ndups(x, npoints);
  }
  const double p = calc_probability(ndups, nsamples, lambda);
  printf("ndups: %lu; p = %g; 1 - p = %g\n", ndups, p, 1.0 - p);
  free(x);
}

typedef struct {
  const char *name;
  randfunc_t func;
} gen_descr_t;

int main()
{
  const double lambda = 8.0;
  const gen_descr_t gens[] = {
    {"rand", rand_env}, {"lrand48", lrand48_env}, {"lcg64", lcg64_env},
    {"rwc", rwc_env},   {"csprng", csprng_env},   {NULL, NULL}
  };
  srand(arc4random());
  srand48(arc4random());
  for (int i = 0; gens[i].name != NULL; i++) {
    printf("Generator %s:\n", gens[i].name);
    printf("  bspace_1d: ");
    run_bspace(lambda, 300, pow(2.0, 31.0), fill_array_1d, gens[i].func);
    printf("  bspace_2d: ");
    run_bspace(lambda, 3,   pow(2.0, 62.0), fill_array_2d, gens[i].func);
    printf("  bspace_8d: ");
    run_bspace(lambda, 3,   pow(2.0, 64.0), fill_array_8d, gens[i].func);
  }
  return 0;
}

Результаты тестов сведены в таблицу, провалы выделены жирным шрифтом:

ГПСЧ	Тест	Число дубликатов	p	1-p
rand	bspace_1d	2936	1	0
	bspace_2d	27	0.730	0.270
	bspace_8d	19	0.154	0.846
lrand48	bspace_1d	2310	0.0331	0.967
	bspace_2d	256958	1	0
	bspace_8d	25145703	1	0
lcg64	bspace_1d	2396	0.467	0.533
	bspace_2d	22	0.342	0.658
	bspace_8d	6921138	1	0
rwc	bspace_1d	2438	0.781	0.219
	bspace_2d	17	0.0765	0.923
	bspace_8d	32	0.949	0.0512
csprng	bspace_1d	2354	0.174	0.826
	bspace_2d	25	0.581	0.419
	bspace_8d	33	0.967	0.0331

Мы видим, что rand, lrand48 и даже 64-битный LCG тест провалили, хотя среди них нет генератора, провалившего его во всех размерностях. Именно поэтому батареи TestU01 включают много модификаций birthday spacings test с разными настройками. Успешно выдержали испытание системный криптографический генератор и мой самодельный RWC. Если Вы пишете на современном С++ (C++11 и выше), то можете проверить вихрь Мерсенна из стандартной библиотеки, он тоже должен пройти тесты из этой статьи. Разумеется, на него тоже «есть управа» в виде алгоритма Берлекэмпа-Мэсси, модификаций критерия интервалов на выборках в десятки петабайт и особо хитрых настройках критерия промежутков между днями рождения (см. статью Schumacher, Nishimura и Matsumoto). Но это уже — довольно тонкие артефакты, обычно не мешающие работе. Мы же в этой статье ищем лишь наиболее очевидные и грубые дефекты, делающие алгоритм непригодным для использования.

Конечно, многие могут возразить на всё это: «мне не нужно прохождение теста birthday spacings, это всё заумь какая-то». Но на самом деле его провал означает одно: генератор рисует какие-то решётки или узоры, и их влияние на симуляцию непредсказуемо. А т.к. добиться прохождения этих тестов довольно просто, то при их систематическом провале проще сразу сказать «генератор непригоден для использования» и «выкрасить и выбросить», а не думать, важно это или нет. Хотя, возможно, игра в Тетрис станет от этого только интереснее, и заголовок статьи вполне себя оправдывает.

О документации и учебниках

В сложных и спорных ситуациях нередко можно услышать рекомендацию читать документацию и учебники. В целом это правильный подход, но информация про ГПСЧ в них зачастую устаревшая, скудная или неполная. И недостаточно внимательное и систематичное изучение литературы и man-страниц серьёзно повышает риск нарваться на плохой генератор.

Попустительство в документации

man-страницы

После проведенных тестов становится очевидным, что ГПСЧ из функций rand и lrand48 содержат грубейшие статистические дефекты, и использование их для каких-либо количественных оценок недопустимо. Тем не менее в man-страницах GNU/Linux их качество описано излишне оптимистично-наплевательски. Примеры из man-страницы, выводимой по команде man 3 rand:

The value pointed to by the seedp argument of rand_r() provides only a very small amount of state, so this function will be a weak pseudo-random generator. Try drand48_r(3) instead.

Т.е. нам хотят сказать, что rand_r c 32-битным состоянием плохой, а drand48_r с 48-битным - хороший, хотя оба генератора очень плохие. Ещё выдержка из этой же man-страницы:

The versions of rand() and srand() in the Linux C Library use the same random number generator as random(3) and srandom(3), so the lower-order bits should be as random as the higher-order bits. However, on older rand() implementations, and on current implementations on different systems, the lower-order bits are much less random than the higher-order bits. Do not use this function in applications intended to be portable when good randomness is needed. (Use random(3) instead.)

Здесь пишут о том, что аддитивный генератор Фибоначчи из random хороший, даже рассуждают про типичную проблему линейных конгруэнтных генераторов с младшими битами (что, кстати, правда). Хотя его качество опять же крайне низкое, и для научных и инженерных расчётов он совершенно непригоден. Если оставлять эти функции без изменений, то в man-страницы следовало бы добавить такое предупреждение (можно в секцию CAVEATS):

Warning! This generator uses a deeply flawed algorithm that doesn't obey a uniform distribution. It is left only for compatibility reasons! All computations made by means of this function must be considered as invalid by default!

Есть ещё два варианта решения со сменой алгоритма:

Добавить выходную функцию-скремблер, маскирующую дефекты.
Выкинуть всю эту хламину с разными режимами работы (см. man 3 setstate) и поставить ChaCha или какой-то другой ARX-шифр.

Документация glibc

Надо отдать должное составителям документации glibc: они называют высококачественным только API для доступа к системному криптографическому генератору. В случае rand, random и lrand48, увы, нет чёткого предупреждения о категорической недопустимости их использования для научных и инженерных расчётов. В общем, дребезделки опять не назвали честно дребезделками.

Документация golang

Аналогичное попустительство мы видим и в golang. Вот документация их пакета rand и выдержка из неё:

Package rand implements pseudo-random number generators suitable for tasks such as simulation, but it should not be used for security-sensitive work.

Замечание про неприменимость в криптографии совершенно справедливо, но внутри всё тот же аддитивный генератор Фибоначчи, и «suitable for tasks as simulation» — вредный совет, которому не место в документации стандартной библиотеки популярного языка программирования. Да, в новых версиях golang разработчики реализовали качественный ГПСЧ ChaCha8, но предупреждение в старый, увы, не добавили.

Документация Java

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

Бардак в учебниках

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

Д.Кнут «Искусство программирования»

Второй том «Искусства программирования» про получисленные методы с главой про ГПСЧ очень ценен для понимания теоретических основ как построения генераторов, так и статистических тестов. В третьем издании 1998 года уже добавлена информация про провалы критерия промежутков между днями рождения, высококачественные генераторы RANLUX и генератор Фибоначчи с децимацией (разработанный самим Кнутом), криптографический генератор Блюм-Блюма-Шуба. Но рекомендации по выбору ГПСЧ для симуляций из-за возраста книги и строго академической стилистики изложения страдают излишней мягкостью (нет того самого «это непригодно для использования» для устаревших генераторов). И если её прочитает будущий разработчик стандартной библиотеки без чтения дополнительной литературы и вдумчивого подхода к проблеме, то велик риск появления новых плохих реализаций ГПСЧ.

Numerical Recipes

Numerical Recipes — очень известная книга по практической реализации численных методов. Качество генераторов в третьем издании 2007 года было заметно улучшено. В ней довольно много комбинированных KISS-подобных генераторов, некоторые из них (например, ran) даже успешно пережили мои попытки их потестировать. В книге есть криптографический генератор RC4, о котором сказано:

If you find any nonrandomness at all in Ranbyte, don’t tell us. But there are several national cryptological agencies that might, or might not, want to talk to you!

Увы, но RC4 проваливает как PractRand, так и простейший частотный тест для 16-битных слов всего на 1 ТиБ. Но 20 лет назад о его статистических дефектах ещё не было широко известно. Конечно, они не столь катастрофичны, как у rand или lrand48, но есть алгоритмы получше и побыстрее. В целом практические рекомендации по конструированию ГПСЧ из Numerical Recipes весьма неплохи. Да, они уже успели несколько устареть, а используемый диалект C++ выглядит немного архаично. Также в книгу не успели попасть TestU01 и PractRand, но в целом всё не так уж плохо и их «топовый» 64-битный алгоритм ran из третьего издания актуален до сих пор.

С. Скиена. Алгоритмы: руководство по разработке. 2022.

В третьем издании этой книги даются в целом корректные рекомендации: предупреждают об опасности систематических ошибок из-за плохих генераторов, прелагают относительно разумные алгоритмы для длительных симуляций (вихрь Мерсенна, ряд комбинированных генераторов и т.п.) Хотя книгу переиздавали в 2020 году, в ней не упоминается ряд современных и быстрых ГПСЧ и батареи TestU01 и PractRand. Также Скиена допускает использование функции rand из стандартной библиотеки языка Си и 32-битных LCG для простейших симуляций. Возможно, в некоторых случаях это и сработает, но проще не тратить время на размышления «можно или нет», сказать: «этот генератор непригоден для использования», и сразу работать с качественными ГПСЧ.

Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. Численные методы. 8-е издание. 2015.

В Главе 5 обсуждается возможное влияние дефектов ГПСЧ на метод Монте-Карло, но не даётся ни конкретных примеров алгоритмов, ни ссылок на батареи статистических тестов, что снижает практическую ценность материала. Но при этом сильной стороной книги является акцент на возможные дефекты при генерации псевдослучайных векторов в многомерных пространствах. Также в ней не рекомендовано ни одного конкретного ГПСЧ, что, возможно, и к лучшему: отсутствие советов лучше устаревших и тем более вредных советов.

Н.Н. Калиткин, Е.А. Альшина. «Численные методы. Книга 1. Численный анализ». 2013.

В книге рекомендуется использовать линейный конгруэнтный генератор с указанием необходимости тщательного подбора множителей, но без конкретики. Также рекомендован устаревший комбинированный генератор Wichmann-Hill-1982, проваливающий ряд модификаций критерия промежутков между днями рождения и обладающий очень малым периодом около $2^{43}$ ( $7\cdot 10^{12}$ ). Ситуацию смягчает то, что указано, что его качество проверено только на очень малых выборках порядка $10^{7}$ , но опять же проще сказать «выкрасить и выбросить» и взять вместо него хороший генератор.

Примечание: в 2006 году Wichmann и Hill выпустили обновлённую версию своего комбинированного генератора, предназначенную для 32- и 64-разрядных процессоров, и она уже проходит современные статистические тесты. К сожалению, новый алгоритм примерно в 10-15 раз медленнее быстрых и качественных некриптографических генераторов, и главное — в 3-5 раз медленнее аппаратно ускоренных AES и ChaCha. Т.е. он представляет собой скорее теоретико-числовой эксперимент, чем удобный и практичный ГПСЧ.

М.Б. Лагутин. «Наглядная математическая статистика». 2023.

Ситуация в Главе 2 «Датчики случайных чисел» (девятое издание) сходна с предыдущей книгой, упоминаются LCG с 32-битным состоянием, minstd, старый генератор Wichmann-Hill. Есть довольно объёмные рассуждения про качество ГПСЧ и даже философские аспекты этой проблемы, но не упоминаются современные батареи тестов, а также криптографический критерий «тест на следующий бит». Мне удалось связаться с автором, и, возможно, в последующие издания будут внесены исправления.

Обновление: в ходе подготовки поста обнаружил, что в 11 издании 2026 года набор датчиков был изменён: добавлен вихрь Мерсенна как широко распространённый рабочий инструмент (с указанием на его некриптостойкость), упомянуты AES и ChaCha20 как быстрые и высококачественные криптостойкие генераторы. Также теперь в книге рекомендуют использовать TestU01 и PractRand для проверки датчиков случайных чисел. Т.е. теперь этот раздел книги соответствует современным стандартам.

А.В. Столяров. «Программирование, введение в профессию». 2025.

Трёхтомник А.В. Столярова, около четверти века преподававшего на ВМиК МГУ, посвящён не численным методам, а основам программирования. Тем не менее, функция rand языка Си упомянута во втором томе в том числе в контексте использования для метода Монте-Карло. Вот цитата из Раздела 4.10.3:

Потребность внести в выполнение программы какое-то разнообразие чаще всего возникает при создании компьютерных игр, хотя, конечно, не только; случайные числа используются и в математических расчётах (небезызвестный «метод Монте-Карло»), и в области обеспечения безопасности [...] Во многих случаях, как правило, не связанных с безопасностью — например, в тех же компьютерных играх — непредсказуемость случайных чисел не слишком важна [...] В такой ситуации случайные числа обычно заменяют псевдослучайными, получить которые намного проще.

Далее идёт описание функций rand и srand, и автор книги абсолютно чётко говорит о недопустимости использования их в области обеспечения безопасности. Но при этом далее утверждает, что «в целом псевдослучайные числа имеют распределение, достаточно близкое к равномерному», что не так ни в glibc, ни в msvcrt, ни в musl. К сожалению, попытки публично (в комментариях гостевой книги) разъяснить недопустимость использования rand и для метода Монте-Карло успехом не увенчались.

В одной из своих программ, Thalassa CMS, он также использует следующую функцию для генерации токенов сессий и паролей:

void fill_random(void *buf, int len)
{
  int i;
  for(i = 0; i < len; i++)
    ((unsigned char*)buf)[i] = (rand() >> 7) & 0xff;
}

ГПСЧ из glibc инициализируется srand либо четырьмя байтами из /dev/urandom, либо при его отсутствии или ошибке чтения — time(0) ^ (getpid() << 8). Разумеется, использование такого кода для криптографических задач совершенно недопустимо, и здесь он приведён как пример того, как делать нельзя. Несколько месяцев назад Столярову на это указали в багрепорте, но понимания это не нашло:

Your approach to the problem has nothing to do with the real world. Anyway, you can fork Thalassa or issue a patch to it; however, please be aware I will not accept such a patch nor will mention it on the site. I simply refuse to fix what is not broken. And no, you won't convince me by any cryptography-related reasoning. It was a huge mistake from my part already to waste time on this thread.

Интересно, что на ВМиК МГУ в практикуме по программированию на Паскале для первокурсников приводят пример качественного некриптографического ГПСЧ, а именно KISS2003, разработанного Дж. Марсальей. Единственный недостаток этих рекомендаций — наличие в них слабых генераторов без явного указания на то, что на практике для симуляций нужно использовать не «дребезделки», а KISS2003. Марсалья выпустил много модификаций KISS, конкретно этот вариант взят из его статьи Random Number Generators 2003 г.

Хорошие учебные генераторы

Я уже много кого раскритиковал, пора переходить к чему-то конструктивному и доброму. Бытует миф о якобы высокой сложности хороших ГПСЧ, из-за которых преподаватели вынуждены показывать студентам линейный конгруэнтный генератор с плохими параметрами. Но ведь можно брать пример с практикума на ВМиК МГУ и использовать комбинированный генератор KISS2003 как учебную иллюстрацию. Вот мой перевод их кода на C:

typedef struct {
  uint32_t x; ///< 32-bit LCG state
  uint32_t y; ///< xorshift32 state
  uint32_t z; ///< MWC state: lower part
  uint32_t c; ///< MWC state: higher part (carry)
} Kiss03State;

static inline uint32_t Kiss03State_next(Kiss03State *obj)
{
  // LCG part
  obj->x = 69069U * obj->x + 12345U;
  // xorshift part
  obj->y ^= obj->y << 13;
  obj->y ^= obj->y >> 17;
  obj->y ^= obj->y << 5;
  // MWC part
  const uint64_t t = 698769069ULL * (uint64_t)obj->z + obj->c;
  obj->c = (uint32_t) (t >> 32);
  obj->z = (uint32_t) t;
  // Combined output
  return obj->x + obj->y + obj->z;
}

Период этого генератора — около $2^{124}$ . При инициализации нельзя устанавливать
y в 0. Значение c должно быть в диапазоне . KISS2003 проходит BigCrush, PractRand 0.94 по меньшей мере до 16 ТиБ, а также батарею full SmokeRand.

Но есть ещё более простое и при этом качественное решение на основе линейного конгруэнтного генератора, а именно MWC64X. Вот его исходный код:

uint32_t MWC64X(uint64_t *state)
{
  uint32_t c=(*state)>>32, x=(*state)&0xFFFFFFFF;
  *state = x*((uint64_t)4294883355U) + c;
  return x^c;
}

Он реализует мультипликативный конгруэнтный генератор с простым делителем , множителем и периодом около $2^{63}$ . При инициализации есть два недопустимых значения пары : и $(a-1,2^{32}-1)$ , где — множитель генератора. Также(перенос) не должен быть больше. Выходная функция-скремблер x^c необходима для маскировки дефектов генератора (провалы некоторых модификаций критерия промежутков между днями рождения, особенно трёхмерных) и прохождения батарей TestU01 и PractRand. Мы не будем вдаваться в теорию генераторов MWC (Multiply-with-Carry), желающие могут обратиться к статьям Марсальи и Goresky и Klapper. Мой самодельный «генератор для Excel» — тоже MWC, проходящий тесты, но рекомендовать его для реальных расчётов я пока бы не рискнул.

В качестве примера простого генератора для параллельных вычислений можно использовать поточный шифр ChaCha20, число раундов для некриптографических целей можно сократить до 8. Обязательно проверьте свою реализацию тестовыми векторами из RFC 7539 и прогоните в PractRand хотя бы на 1 ТиБ. При использовании для симуляций обязательно расширьте счётчик до 64 бит за счёт nonce: иначе ChaCha20 провалит PractRand уже на 256 ГиБ!

Возможные пути улучшения ситуации и шифры

Разумеется, многие могут сказать: статистические тесты развиваются, объёмы памяти растут, будут находить всё новые и новые дефекты, и где гарантия, что нынешние высококачественные ГПСЧ когда-нибудь не сочтут неприемлемыми? Что ж, это вполне возможно, и Кнут во втором томе «Искусства программирования» писал о подобном в разделе 3.6:

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

Но можно радикально снизить риски такого развития событий — использовать в качестве ГПСЧ поточные шифры без известных уязвимостей, например, AES-CTR, ChaCha, Speck-CTR, ThreeFish-CTR и т.п. Применение шифров вне криптографии может выглядеть как стрельба из пушки по воробьям, но это решение на самом деле не столь уж странное:

Требования к стойкости шифра аналогичны предположению о том, что статистический тест или симуляция устроены наиболее зловредным образом и прицельно бьют в слабые места ГПСЧ. При этом шифр считается качественным, если тест не может работать эффективнее полного перебора сидов (ключей).
Производительность AES и ChaCha с аппаратным ускорением с помощью инструкций AESNI и AVX2 на x86-64 может достигать 1 cpb (процессорных тактов на байт), т.е. сопоставима с такими «умеренно тяжеловесными» ГПСЧ, как Well1024a, KISS, MIXMAX, Ranecu, xorwow. Наиболее быстрые и качественные ГПСЧ (например, xoroshiro++, MWC128X, SFC64) могут выдавать 0.2-0.3 cpb даже без векторизации. Результаты измерений производительности разных ГПСЧ есть в репозитории SmokeRand.
Многие шифры очень удобны для параллелизации, т.к. работают как счетчиковые ГПСЧ (англ. Counter-Based PRNG, CBPRNG), дающие доступ к членам последовательности по их номерам.
Успешное использование AES для метода Монте-Карло описано более 20 лет назад, а широко применяющиеся для параллельных вычислений ThreeFry и Philox - это ослабленные некриптографические модификации шифра ThreeFish.

Приведу результаты бенчмарка разных генераторов псевдослучайных чисел на своём Intel Core i5-11400H 2.70GHz. Измерения выполнялись в SmokeRand под управлением Windows 11, компилятор TDM-GCC 10.3.0, ключи -O3 и -native. Полученные значения cpb (тактов на байт) являются весьма приблизительными, в них есть поправка на оверхед на вызов функции или накладные расходы на цикл при инлайнинге. Под AVX2 имеются в виду оптимизированные мной вручную версии генераторов с использованием интринсик компилятора, обычно с увеличенным состоянием для эффективной загрузки регистров. При попытках измерить скорость выполнения rand из glibc в разных виртуальных машинах получались скорости от 8 до 35 cpb, что связано с присутствием в ней мьютексов. Т.е. мы не просто имеем непригодный для использования генератор в стандартной библиотеке, он ещё и ощутимо медленнее ChaCha8! При этом даже упрощённая версия ChaCha с 8 ��аундами - это всё ещё криптографический генератор, см. знаменитую статью Too much crypto. В таблице есть неожиданный результат: ChaCha8 на x86-64 в несколько раз быстрее классической реализации линейного конгруэнтного генератора minstd $x_{n+1}=16807x_n \mod (2^{31}-1)$ на основе Schrage's method из статьи Парка и Миллера. Это связано с тем, что в шифре нет медленных операций деления, а сам он изначально проектировался с учётом существования конвейера процессора и SIMD.

Генератор	Скорость, cpb	Качество
SFC64	0.19	Высокое
xoroshiro128++	0.25	Высокое
MWC128X	0.38	Высокое
MWC64X	~0.6	Высокое
PCG64-DXSM	0.56	Высокое
MT19937	0.60	Скорее высокое, но биты линейно зависимы
ChaCha8-AVX2	0.64	Очень высокое (шифр)
KISS2003	0.76	Высокое
AES128 (AESNI)	1.0	Очень высокое (шифр)
Well1024a	1.3	Скорее высокое, но биты линейно зависимы
Threefish1024-AVX2	1.3	Очень высокое (шифр)
minstd	1.4	Очень низкое, много грубых дефектов
MIXMAX	1.4	Высокое
xorwow	1.5	Скорее низкое, плохие младшие биты, возможны проблемы с частотными тестами
HC256	1.5	Очень высокое (шифр)
ChaCha8 (portable)	2.2	Очень высокое (шифр)
Wichmann-Hill-1982	2.5	Очень низкое, много грубых дефектов
minstd (Schrage's method)	2.6	Очень низкое, много грубых дефектов
ThreeFish1024 (portable)	4.4	Очень высокое (шифр)
RC4	6.5	Среднее, провалы частотных тестов на 1 ТиБ
AES128 (программный)	6.9	Очень высокое (шифр)
DES	24	Скорее высокое, нет повторов 64-битных блоков в CTR-режиме.

Такая ситуация в принципе уже сейчас позволяет сменить парадигму: рассматривать ГПСЧ на основе шифров как решения по умолчанию для всего, даже для написания Тетриса. А некриптографические генераторы считать «битовыми трюками» (bithacks) для нишевых оптимизаций, выучивания наизусть, студенческих практикумов и прочих хороших дел. И да, инициализировать даже некриптографические генераторы для симуляций уже давно пора от системного криптогенератора, а не от текущего времени.

И с математической точки зрения использование криптографического примитива в ГПСЧ для симуляций эквивалентно реализации функций стандартной библиотеки вроде sin, cos, exp и log с относительной погрешностью порядка машинного эпсилона. Более того, разнообразие быстродействующих шифров даёт возможность выполнить другую рекомендацию Кнута вообще без использования некриптографических генераторов:

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

В нашем распоряжении имеются по меньшей мере три варианта: SP-сети (AES), ARX-конструкции со счётчиком (ChaCha, ThreeFish, LEA, Speck), поточные шифры ISAAC, ISAAC64, HC128 и HC256. Если для симуляции нужны жёсткие теоретические гарантии равномерности распределения в высоких размерностях, то можно использовать ThreeFish-1024 с 1024-битным блоком.

Конечно, шифры — не панацея: их стойкость не доказана строго математически, а за такое доказательство обещают миллион долларов. И статистические дефекты в RC4 легко обнаруживаются PractRand и даже простейшими частотными тестами, а DES-CTR проваливает тест «64-битный парадокс дней рождения» (см. дистрибутив SmokeRand с реализацией и описанием этот теста). Но насколько я знаю, другие генераторы той эпохи даже BigCrush «не пережили», т.е. даже устаревшие шифры оказались «на голову выше» подавляющего большинства своих некриптографических «современников».

ВНИМАНИЕ! Для криптографии (генерация ключей, паролей и т.п.) можно использовать только специально спроектированные для этих целей библиотеки, например, системный криптогенератор. Даже если ГПСЧ для симуляций в каком-то языке основан на шифре, использовать его для криптографии нельзя! Возможны неочевидные слабости в инициализации и т.п.

Язык C

Изменить ситуацию с функцией rand можно было бы, наверное, принятием таких изменений в стандарты Си и/или POSIX:

Начать требовать использования в функции rand поточных шифров без известных уязвимостей с генерацией ключа по умолчанию от системного криптогенератора.
При невозможности подобного (микроконтроллеры и т.п.) — даже некриптографический алгоритм должен иметь период не меньше $2^{60}$ , а также проходить TestU01 SmallCrush, Crush, BigCrush в разных режимах работы, в т.ч. с обращенным порядком бит, а также PractRand на 128 ТиБ. При подключении заголовочника стандартной библиотеки с подобным генератором должно выдаваться предупреждение компилятора «Bithack Random Is Enabled», подавляемое чем-то вроде #define USE_BITHACK_RANDOM.

Они могут показаться излишне максималистскими или жёсткими, но повторюсь: на самом деле они полностью аналогичны тому, что от реализации синуса ожидают относительной погрешности порядка машинного эпсилона! Ладно, возможно, USE_BITHACK_RANDOM - это скорее шутка, но про шифры, BigCrush и PractRand я пишу абсолютно серьёзно. Нынешняя ситуация, в которой ГПСЧ четверьвековой давности (MT19937) из MS Excel и PHP 8 на голову выше всех некриптографических генераторов-дребезделок из glibc, ненормальна. Особенно с учётом того, что алгоритм, проходящий BigCrush и PractRand, можно самостоятельно реализовать в электронных таблицах вручную, даже без функции СЛЧИС и VBA.

Язык C++

В современных стандартах (C++11 и выше) ситуация с ГПСЧ значительно лучше, чем в чистом C: имеется как подборка генераторов разного качества, так и готовые классы для преобразования диапазонов и формы распределений. Есть как низкокачественные (minstd, minstd0), так и весьма достойные (mt19937, mt19937_64) алгоритмы. В C++26 обещают добавить Philox, проходящий все тесты BigCrush и PractRand и очень удобный для многопоточных программ. Тут для дальнейшего улучшения ситуации осталось сделать не так много:

Нужно сделать обязательным использование в default_random_engine проходящего все современные тесты генератора, например, Philox. Ситуация с возможным применением по умолчанию minstd категорически неприемлема: это всё равно, что по умолчанию рассчитывать в стандартной библиотеке языка синус с погрешностью в 1 процент. И ещё рассуждая «большинству и так сойдет».
Необходим аналог std::random_device с обязательной криптостойкостью и индетерминизмом. В случае невозможности обеспечить подобную функцию на платформе — нужна не замена на обычный ГПСЧ, а сообщение об ошибке, т.е. поведение «я не могу, у меня лапки».
Идеальным было бы добавление в <random> ГПСЧ на основе ARX-шифра, например, ChaCha, LEA или ThreeFish. Не для связанных с безопасностью задач, просто как образцового генератора общего назначения.

Почему функции rand и lrand48 из glibc годятся только для Тетриса: о случайных числах всерьёз

Оглавление