О критериях качества генераторов псевдослучайных чисел

[Skipper]

Dig386 в сообщении #1710892 писал(а):

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

Если человек - "плохой источник случайности", и его можно рассматривать как "биоробота", то я уже выше описал как я получил истинно случайные числа, разбавив энтропию своей случайностью. Можете доказать,
что она как то отличается от случайной без присутсвия энтропии человека?
Я могу отправить такой файл, белый шум, с энтропией человека- самого себя.

Цитата:

При нажатии клавиш можно, например, смотреть не введенные байты, а младшие биты счетчика тактов RDTSC.

Извините, я как программист говорю, 1) если смотреть "младшие биты счетчика тактов RDTSC" то получить любое число можно было бы если бы была у нас ОС - операционная система реального времени.
Вот нажал я допустим в момент когда на счётчике тактов процессора было значение
19475495016209876271254750982...
и она выдаёт это любое число.

Большинство систем которые используются, например та же Windows у меня, работает вот так.
Там куча процессов и потоков сидит в очереди. Планировщик задач ОС, даёт каждому потоку,
20 миллисекунд времени, после чего переключает на другой поток, который стоит в очереди с учетом приоритета.
Если я нажал клавишу в этот момент, то за эти 20 миллисекунд реального времени, пройдёт много миллионов тактов процессора, и только одно число, (после переключения планировщиком ОС) в
мою программу генерации рандомных чисел- будет выдано как рандомное.
А не все , не абсолютно все значения счётчика тактов процессора, могут быть туда выданы! (большинство просто "пролетают мимо"!)
Я вот это хочу донести ещё со студенческих лет..

Статистически, мой "человеческий белый шум" может и не отличается никак от псевдо-случайного, но по моему принципу есть разница!

PS Потому, именно как раз не считывание счетчика генератора процессора здесь может выдать
ВСЕ числа, согласно моему принципу,

Skipper в сообщении #1710882 писал(а):

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

Но в реальных компьютерах, такого попросту, нет.
Вот недавно я задался целью сгенерировать истинно случайное число, длиной в 1024 бита.
Это значит, с точностью до порядка $10^{309}$ , то есть длиной в $309$ цифр в десятичной записи.
Учитывая, что число атомов во Вселенной, порядка $10^{80}$ , я не представляю, что такого,
(без квантового генератора), можно такое прочитать генератору псевдослучайных чисел, чтобы он мог выдать действительно ЛЮБОЕ из этого множества, $10^{309}$ , число!

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

Взять тот же номер такта процессора. Но планировщик задач ОС, переключает потоки между собой с частотой в 20 миллисекунд, и на протяжении этого промежутка времени, все промежуточные номера тактов "выпадают" из возможного множества определяемых рандомными, чисел. То есть не могли бы быть выданы.
По остальным параметрам, аналогичное утверждение.

Но вот как я добился всё таки ИСТИННО, рандомного числа, то есть считаю, что получил действительно число, по такому принципу, что могло сюда выпасть действительно ЛЮБОЕ из этого множества, $10^{309}$ , число?

Я просто "разбавил" этот криптостойкий генератор случайного числа, своей собственной энтропией.
Побарабанил пальцами, совсем случайно по клавишам, чтобы набрать достаточное количество рандомных байтов, затем сдвинул каждый int64, согласно линейному конгруэнтному методу на шаг вперед, чтобы получить равномерное распределение по всему интервалу,
а затем (хотя это уже и необязательно)- "склеил" xor-м (исключающим или), с рандомным числом полученным от криптостойкого генератора случайных чисел.

После подобной процедуры, уже неважно что там криптостойкий генератор случайных чисел, действительно не может выдать любое число на интервале $10^{309}$ чисел, это могли "выдать мои пальцы" на каждое его значение, так что после операции xor- результат тоже получается таким,
что мы можем утверждать- на компьютере могло быть получено действительно любое из $10^{309}$ чисел,

а потому, свои 1024-битные числа, я получил истинно случайными.. Согласно моему определению,

2) А нажатие клавиш- может. Просто потому что я действительно мог нажать любую клавишу!

-- Ср дек 24, 2025 15:53:56 --

Dig386 в сообщении #1710892 писал(а):

писал(а):
Вот недавно я задался целью сгенерировать истинно случайное число, длиной в 1024 бита.
Есть генераторы псевдослучайных чисел, способные гарантированно выдать любое число от 0 до $2^{1024} - 1$. Например, шифр Threefish-1024 в режиме гаммирования.

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

[Dig386]

Skipper в сообщении #1713300 писал(а):

Можете доказать,
что она как то отличается от случайной без присутсвия энтропии человека?

Попробуйте для начала отправить эти файлы в PractRand через потоки ввода-вывода. Там размер тестируемой выборки от 1 КиБ как раз начинается.

Цитата:

Просто потому что я действительно мог нажать любую клавишу!

Когда человек пытается сделать что-то якобы случайно, особенно сознательно, получается плохо.

Цитата:

А не все , не абсолютно все значения счётчика тактов процессора, могут быть туда выданы!

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

Цитата:

Побарабанил пальцами, совсем случайно по клавишам, чтобы набрать достаточное количество рандомных байтов, затем сдвинул каждый int64, согласно линейному конгруэнтному методу на шаг вперед, чтобы получить равномерное распределение по всему интервалу,
а затем (хотя это уже и необязательно)- "склеил" xor-м (исключающим или), с рандомным числом полученным от криптостойкого генератора случайных чисел.

Выглядит это так:
1) Взяли водно-углеродный ГПСЧ с плохим алгоритмом, т.е. оператора :) Единственное преимущество - в этом ГПСЧ иногда случаются сбои и может быть некоторая нерегулярность. Если набрать побольше ввода оператора - то можно и получить чуть-чуть истинной случайности.
2) Взяли примитивный скремблер, основа которого в ГПСЧ общего назначения без дополнительных модификаций не годится.
3) Полученное из п.2 поXORили с хорошим генератором случайных чисел.

В этом случае системный криптогенератор явно будет намного более качественным. И если уж есть желание "смешивать" собственный ввод с системным криптогенератором, то нужны не самопальные миксеры, а готовые криптографические хеши. Размер хеша обычно 256 или 512 бит, иногда 1024 бита (Skein-1024). Им можно на вход подать и выход /dev/urandom, и RDTSC, и набранные пользователем данные на клавиатуре. Причём подать с запасом, не 1024 бита, а несколько килобайт. И от криптогенератора хорошо бы взять выход как два хеша по размеру.

Цитата:

Там куча процессов и потоков сидит в очереди

Именно поэтому системный криптогенератор реализован в самой ОС.

-- 24.12.2025, 17:15 --

Skipper в сообщении #1713300 писал(а):

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

ThreeFish-1024 в режиме гаммирования - это именно что ГПСЧ, полностью детерминированный, прямо как какой-нибудь синус или косинус. Но как только мы задаём ключ (его можно получить и от аппаратного генератора случайных чисел), то получаем обратимое преобразование счётчика в 1024-битный блок. И из-за обратимости на выходе ThreeFish-1024 может появиться любой 1024-битный блок. Также он спроектирован так, чтобы без знания ключа его выход было бы затруднительно отличить от истинно случайного.

[Skipper]

Dig386 в сообщении #1713301 писал(а):

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

Я плохо клавиши нажимаю? Ну если "плохо", то предскажите, или выявите статистическую закономерность от нажатий. Тут конечно , случайность будет расти в зависимости от промежутка времени между нажатиями клавиш, я это всё понимаю. Но самое главное что мой принцип такой абсолютной случайности- возможность получить ЛЮБОЕ число от 2 до 2^1024 будет соблюдаться.
Тут или человеческая энтропия даёт такую возможность, или некий квантовый генератор, приёмник,

[Dig386]

Skipper в сообщении #1713302 писал(а):

Я плохо клавиши нажимаю?

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

[Skipper]

Dig386 в сообщении #1713304 писал(а):

Skipper в сообщении #1713302 писал(а):

Я плохо клавиши нажимаю?

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

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

[Dig386]

Skipper в сообщении #1713305 писал(а):

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

Вот здесь всё написано: https://pracrand.sourceforge.net/
Проше всего ввести что-нибудь вроде (для тестирования выборки от 1 КиБ):

$ cat your_file | RNG_test stdin32 -tlmin 10

Файл должен быть двоичным. Под виндой остерегайтесь проблем с двоичным/текстовым режимом потока.

-- 24.12.2025, 18:09 --

SergeyGubanov в сообщении #1713276 писал(а):

Например, как-то так (x - имеет слабые младшие биты, y - имеет слабые старшие биты):

У меня, кажется, получилось ощутимо улучшить и ускорить алгоритм. Вот таким образом:

Используется синтаксис C

static inline uint64_t get_bits_raw(Lcg64State *state)
{
    const uint64_t x = state->x * 2163025688268396121ull + 7524640194127809971ull;
    state->x = x;
    const uint64_t y = rbit64(x) * 6906969069U;
    return rotl64(y, x & 0x1F);
}
 

Идея очень простая: сначала перевернуть биты, затем умножить на константу из хорошего LCG, и младшие биты с большим периодом замаскируют плохие старшие биты. Выходной псевдослучайный сдвиг разрушает остатки решетчатой структуры, идея взята из PCG. Кстати, а откуда у Вас именно это константа LCG, хорошо ли она проходит спектральный тест Кнута?

После этого он стал проходить простые проверки на равномерность распределения, например, батарею full из пакета SmokeRand. А это уже значит, что можно тестировать более капитально, т.е. в PractRand и TestU01 (но мне пока лень). Алгоритм ускорился где-то до 0.7 cpb на x86-64, что сопоставимо с ChaCha8 на AVX2. Т.е. на x86-64 он скорее бессмысленен, т.к. шифр даёт сопоставимую скорость. Может, на ARM он и будет быстрый. Но для практического использования его нужно куда серьёзнее тестировать.

Используется синтаксис Text

==================== 'full' battery report ====================
Generator name:    LCG64str2
Output size, bits: 64
Used seed:         _05_IsL/FV/cOWaV95vA+m2b266p+I9YI820XM3V3JmCkY0=

    # Test name                    xemp              p Interpretation  Thr#
-------------------------------------------------------------------------------
    1 monobit_freq             0.238029          0.406 Ok                 3
    2 byte_freq                0.975213          0.298 Ok                 1
    3 word16_freq              0.713387          0.689 Ok                 2
    4 bspace64_1d                   944          0.961 Ok                 5
    5 bspace32_1d                 32734          0.573 Ok                 3
    6 bspace32_1d_high            32578          0.852 Ok                 5
    7 bspace32_2d                  1012          0.345 Ok                 4
    8 bspace32_2d_high             1018          0.278 Ok                 1
    9 bspace21_3d                   756          0.939 Ok                 4
   10 bspace21_3d_high              792          0.602 Ok                 1
   11 bspace16_4d                   822          0.213 Ok                 1
   12 bspace16_4d_high              803          0.448 Ok                 4
   13 bspace8_8d                    789          0.643 Ok                 4
   14 bspace8_8d_high               790          0.630 Ok                 4
   15 bspace4_8d_dec                  3          0.567 Ok                 3
   16 bspace4_16d                   770          0.852 Ok                 2
   17 bspace4_16d_high              810          0.353 Ok                 3
   18 collover20_2d               56926          0.362 Ok                 5
   19 collover20_2d_high          56865          0.461 Ok                 1
   20 collover13_3d              113810          0.353 Ok                 2
   21 collover13_3d_high         113526          0.679 Ok                 3
   22 collover8_5d                57217          0.058 Ok                 5
   23 collover8_5d_high           56801          0.568 Ok                 1
   24 collover5_8d                57207          0.063 Ok                 2
   25 collover5_8d_high           56977          0.286 Ok                 2
   26 gap_inv8                  118.585          0.545 Ok                 3
   27 gap_inv512                3784.82          0.845 Ok                 5
   28 gap_inv1024               9624.71          0.052 Ok                 1
   29 gap16_count0              -0.3728          0.645 Ok                 2
   30 hamming_distr            -2.28173          0.989 Ok                 5
   31 hamming_ot               0.372902          0.355 Ok                 1
   32 hamming_ot_low1         0.0701581          0.472 Ok                 3
   33 hamming_ot_low8           1.40721          0.080 Ok                 4
   34 hamming_ot_values        0.975345          0.165 Ok                 4
   35 hamming_ot_u128          0.704417          0.241 Ok                 4
   36 hamming_ot_u256         -0.823346          0.795 Ok                 3
   37 hamming_ot_u512         -0.580147          0.719 Ok                 5
   38 linearcomp_high            500000          0.667 Ok                 2
   39 linearcomp_mid             500001          0.667 Ok                 2
   40 linearcomp_low             500001          0.667 Ok                 1
   41 matrixrank_4096           1.15489          0.561 Ok                 4
   42 matrixrank_4096_low8      1.60204          0.449 Ok                 5
   43 matrixrank_8192           6.05528          0.048 Ok                 2
   44 matrixrank_8192_low8      2.25263          0.324 Ok                 3
   45 mod3                     -1.37018          0.915 Ok                 5
   46 sumcollector              20.9904          0.860 Ok                 2
-------------------------------------------------------------------------------
Passed:        46
Suspicious:    0
Failed:        0
Quality (0-4): 4.00 (good)
Elapsed time:  00:48:09
Used seed:     _05_IsL/FV/cOWaV95vA+m2b266p+I9YI820XM3V3JmCkY0=
 

[SergeyGubanov]

Dig386 в сообщении #1713306 писал(а):

Используется синтаксис C

static inline uint64_t get_bits_raw(Lcg64State *state)
{
    const uint64_t x = state->x * 2163025688268396121ull + 7524640194127809971ull;
    state->x = x;
    const uint64_t y = rbit64(x) * 6906969069U;
    return rotl64(y, x & 0x1F);
}
 

Наверное ещё лучше будет взять старшие биты x, они же более "сильные":

Используется синтаксис C

return rotl64(y, ((x >> 56) & 0x1F));

Dig386 в сообщении #1713306 писал(а):

а откуда у Вас именно это константа LCG, хорошо ли она проходит спектральный тест Кнута?

Это случайные простые числа из Вольфрам Альфы: Table[NextPrime[RandomInteger[Power[2,63]]], {10}]. Кнута читал давно, помню только что что-то с чем-то должно быть взаимно простым, но если взять простые числа, они же всяко будут взаимно просты с чем угодно. Правда экспериментальным путём обнаружил, что с некоторыми простыми числами период получается в два раза больше чем с другими.

В свою очередь, удивляюсь вашей непростой константе:

$$ 6906969069 = 3 \times 7 \times 11 \times 13 \times 23 \times 9091. $$

[Dig386]

SergeyGubanov в сообщении #1713316 писал(а):

Наверное ещё лучше будет взять старшие биты x, они же более "сильные":

Да, так лучше должно быть. Ещё можно маску взять & 0x3F, чтобы диапазон циклических сдвигов был шире.

Цитата:

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

Там немного другие условия. Для делителя - степени двойки они сводятся к тому, что (а) константа и множитель должны быть нечётными; (б) множитель при делении на 4 должен давать остаток 1. Также нужно проверять качество множителей спектральным тестом Кнута. Константа 6906969069 для m=2^{64} предложена Дж. Марсальей, у неё хорошие спектральные характеристики, и её легко запомнить. Вообще множители в LCG, запаздывания в генераторах Фибоначчи и сдвиги в LFSR без теоретического анализа трогать нельзя.

[SergeyGubanov]

Странно. Оказалось, что если сдвинуть $x$ на 56, то становится невероятно плохо на тесте который измеряет распределение расстояний между двумя одинаковыми байтами. Например, встретили в младшем байте число 42, сколько раз надо после этого выполнить генерацию следующего числа для того чтобы опять встретить 42?

Вероятность в следующий раз встретить тот же самый байт через $n$ генераций описывается формулой:

$$ P_{\text{Byte}}(n) = \operatorname{const} \, \exp \left( - \frac{n}{256.0} \right). $$

Если взять 1023 счётчика для расстояний от 1 до 1023 и нагенерировать 8 миллионов испытаний (в среднем по 8192 раз на счётчик), то для хороших генераторов среднеквадратичное отклонение частотности от этой формулы будет примерно $2\%$ почти не зависимо от значения повторяемого байта. А вот для этого алгоритма со сдвигом $x$ на 56 для разных значений байта отклонение разное и для некоторых достигает нескольких десятков процентов.

[Dig386]

SergeyGubanov в сообщении #1713394 писал(а):

если сдвинуть $x$ на 56, то становится невероятно плохо на тесте который измеряет распределение расстояний между двумя одинаковыми байтами

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

Используется синтаксис Text

==================== 'brief' battery report ====================
Generator name:    LCG64str
Output size, bits: 64
Used seed:         _0B_sdBfuNEV/21MvzmAGBDj1tDXEi+teuJ1Z+RNnaHhAPA=

    # Test name                    xemp              p Interpretation  Thr#
-------------------------------------------------------------------------------
    1 monobit_freq             0.290237          0.386 Ok                 8
    2 byte_freq                 64.0026              0 FAIL               2
    3 bspace64_1d                   186          0.020 Ok                11
    4 bspace32_1d                 17103       1.19e-08 SUSPICIOUS         6
    5 bspace32_1d_high            16832       2.42e-04 SUSPICIOUS         3
    6 bspace32_2d                    18          0.619 Ok                 3
    7 bspace21_3d                    19          0.530 Ok                10
    8 bspace16_4d                    25          0.112 Ok                 7
    9 bspace8_8d                     28          0.034 Ok                 5
   10 bspace4_8d_dec                  7          0.051 Ok                 9
   11 collover20_2d                5176      1.05e-173 FAIL               3
   12 collover13_3d                9904      6.32e-268 FAIL              10
   13 collover8_5d                 4456       7.72e-66 FAIL              11
   14 collover5_8d                 3557          0.006 Ok                 6
   15 gap_inv8                   238641              0 FAIL               4
   16 gap_inv512                 175205              0 FAIL               1
   17 gap16_count0              345.491              0 FAIL               5
   18 hamming_distr             21.6667      2.12e-104 FAIL               2
   19 hamming_ot_low1          -1.74522          0.960 Ok                 9
   20 hamming_ot_values         1.42297          0.077 Ok                 7
   21 hamming_ot_u128         -0.686759          0.754 Ok                 4
   22 linearcomp_high             25001          0.667 Ok                 8
   23 linearcomp_mid              25001          0.667 Ok                 2
   24 linearcomp_low              25000          0.667 Ok                 1
   25 mod3                     -0.27196          0.607 Ok                 4
-------------------------------------------------------------------------------
 

Тест gap16_count0 делает примерно то же самое, что и Ваш тест, только на 16-битных словах.

[SergeyGubanov]

Уточнение по поводу формулы. Для повтора числа из $m$-битов через $n$ генераций (для не слишком больших $n$) рабочая формула получается такая:

$$ P_{m}(n) = C_{m} \, \exp \left( - \frac{n}{2^{m} - \frac{1}{2}} \right). $$

Почему там в знаменателе из $2^{m}$ надо вычесть $\frac{1}{2}$ не знаю, удивительный экспериментальный факт. При больших $m$ это погоды не делает, но при малых $m$ эта минус одна вторая очень сильно влияет. А ещё при больших $n > 2^{m}$ либо эта формула не верна, либо рандомные генераторы косячат. При увеличении числа испытаний оно к экспоненциальному хвосту что-то не сходится. Причём чем больше $n$, тем сильнее не сходится. По факту наблюдаю, что оно затухает быстрее экспоненты.

[Dig386]

SergeyGubanov в сообщении #1713409 писал(а):

либо эта формула не верна, либо рандомные генераторы косячат

Тут надо учитывать то, что мы имеем дело с дискретными величинами, а не с непрерывными. Также какими ГПСЧ Вы калибровали тест? Для таких калибровок необходимо использовать криптографические генераторы.

[SergeyGubanov]

Вобщем, это я с формулой накосячил. Правильная формула такая:

$$ P_{m}(n) = C_{m} \left( 1 - \frac{1}{2^m} \right)^{n} $$

Надо было сначала подумать, а не подгонять под эксперимент

[Dig386]

SergeyGubanov в сообщении #1713417 писал(а):

Вобщем, это я с формулой накосячил. Правильная формула такая:

Если в слове m бит, то вероятность получить то или иное значение слова - 2^{-m}. Тогда вероятности выпадения интервалов длиной n будут такими:
1) Для интервала длиной 1: 2^{-m}
2) Для интервала длиной 2: 2^{-m}\left(1 - 2^{-m}\right)
3) Для интервала длиной 3: 2^{-m}\left(1 - 2^{-m}\right)^2
И получится в итоге нужная формула. Кстати, она есть в TAOCP (том 2) в описании Gap Test. И специфично настроенный Gap Test легко выявляет неслучайность функции rand из glibc, что говорит о низком качестве использованного там алгоритма.

SergeyGubanov в сообщении #1713417 писал(а):

не подгонять под эксперимент

Эксперимент тоже иногда применяют, в том же PractRand многие распределения получены эмпирически. Но там для этого используют не "хакерские" генераторы типа LCG или MT19937, а поточный шифр HC256, а также огромные выборки порядка сотен терабайт. И без шифров или криптографических хеш-функций качественная экспериментальная проверка тестов для ГПСЧ невозможна: для калибровки и отладки следует использовать самые качественные ГПСЧ без известных человечеству дефектов.