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

[Dig386]

realeugene в сообщении #1710913 писал(а):

успешно используют "отвратительный" LFSR

В том-то и дело, что в glibc - не классический LFSR, а аддитивный генератор Фибоначчи, проваливающий тривиальные gap test и birthday spacings test. А грамотно спроектированный LFSR с достаточно плотной матрицей перехода и хорошей выходной функцией, например, xoroshiro++, может быть как раз довольно неплох, особенно для микроконтроллеров. Уж точно лучше LCG. И это прекрасно - иметь запас таких алгоритмов для особых случаев. Я просто ставлю под сомнение целесообразность их использования на обычных рабочих станциях в подавляющем большинстве случаев. Есть же знаменитый принцип "преждевременная оптимизация — корень всех зол".

Я понимаю, что требования определяются задачей. Но если задача - это качественная функция rand() для настольного ПК без экстремальных требований к скорости, то шифр идеально подходит.

realeugene в сообщении #1710913 писал(а):

Те, кто занимаются серьёзно, и так всё понимают.

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

Также у меня складывается впечатление, что авторы учебников далеко не всегда понимают, что такое хороший ГПСЧ, и там можно и Wichmann-Hill увидеть, и LCG, и какие-то плохо спроектированные LFSR. Упоминание шифров как образцовых генераторов можно увидеть тоже далеко не всегда. А уж в старых книгах много плохих алгоритмов, но там хотя бы на возраст книги списать можно.

[realeugene]

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

не классический LFSR

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

-- 28.11.2025, 16:09 --

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

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

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

-- 28.11.2025, 16:10 --

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

авторы учебников далеко не всегда понимают, что такое хороший ГПСЧ, и там можно и Wichmann-Hill увидеть, и LCG, и какие-то плохо спроектированные LFSR

Или не считают такие генераторы плохими для своих задач.

[Dig386]

realeugene в сообщении #1710916 писал(а):

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

Я думаю, что у разработчиков аппаратных протоколов есть и sympy, и TestU01 с PractRand для проектирования LFSR, и они знают, что делают, и чего они хотят от своего регистра сдвига. Но это опять же - узкоспециализированная ниша. И заметьте - LCG тут нет, т.к. умножение здесь дорогое. Тащить же микроконтроллерно-железячные оптимизации на рабочие станции обычно нецелесообразно.

Впрочем, я как-то видел пример реализации LFSR на Си, в которой умудрились быть медленнее AES в 100 раз.

realeugene в сообщении #1710916 писал(а):

Или не считают такие генераторы плохими для своих задач.

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

[realeugene]

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

и чего они хотят от своего регистра сдвига

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

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

Или же просто они не осознают характер проблемы и не знакомы с современными подходами

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

[Dig386]

realeugene в сообщении #1710928 писал(а):

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

Я ориентируюсь не просто на специалистов, а на специалистов мирового уровня.
1) Разработчики TestU01 (https://simul.iro.umontreal.ca/testu01/tu01.html) - они ещё около 20 лет назад говорили про "very bad lattice structure" и/или "should be discarded" про почти все линейные генераторы из учебников. И наименее проблемными ГПСЧ у них были комбинированные генераторы и криптографические генераторы.
2) Разработчик PractRand (https://pracrand.sourceforge.net/) - использует поточные шифры для калибровки своей батареи тестов и всячески рекомендует их как эталон.
3) Дональд Кнут - ещё 30 лет назад в своей трёхтомной монографии предупреждал об артефактах многих линейных генераторов. А для 32-битных LCG рекомендует такие малые выборки, на которых тесты ещё не начинают "видеть" артефакты генератора.
4) Дж. Марсалья открыл решетчатую структуру LCG, очень много внимания уделял проблеме поиска качественных ГПСЧ, и предложил в итоге семейство довольно качественных комбинированных генераторов KISS. А модификации его LCG с большим состояниям (RANLUX) до сих пор трудятся в CERN.
5) Современные издания Numerical Recipes - рекомендуют комбинированные и похожие на KISS ГПСЧ, а также шифр RC4 (ныне устаревший, в нем нашли дефекты)
6) Разработчики ThreeFry и Philox - взяли шифры как основу, и упростили их для ускорения на GPU.

И если в каких-то учебниках по численным методам и статистике ещё остались всякие "дребезделки" вроде 32-64 битных LCG, xorshift64, аддитивных генераторов Фибоначчи или Wichmann-Hill-1982 - то их просто давно не обновляли. Также проблема может быть в отсутствии перевода многих вещей на русский язык, хотя вряд ли: авторы учебников по подобным предметам обязаны знать английский язык.