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

[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 писал(а):

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

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