Кстати, они всё же похожи на реальные тесты, применяемые для контроля качества ГПСЧ, особенно там, где считают частоты подпоследовательностей и распределение весов Хемминга.
И какой теоретический критерий псевдослучайности используется на практике? Мне приходит в голову только тест на следующий бит. Ещё видел критерий "может ли ГПСЧ выдать все возможные комбинации чисел для n-мерных векторов".
Когда я поработал с LFSR в рамках хобби, то мне стало казаться, что математики порой ради высокой абстракции могут переусложнять многие вещи даже в научпопе. Да, теория нужна, но большинство людей мыслят не от абстракций, а от чего-то более осязаемого. Максимальность периода какого-нибудь xorshift можно доказать куда нагляднее:
1) Функция перехода ГПСЧ записывается в виде матрицы (и отдельно проговаривается, что тут всё не как обычно, т.е. вектор с битами пишут нередко горизонтально и слева от матрицы), операции в GF(2) объясняется по простому: заменяй сложение и вычитание на XOR, умножение - на AND. Да, тут возможны неочевидные нюансы в виде вырожденности матрицы, но обычно xorshift собирают по таблице с биективыми операциями над машинными словами.
2) Отдельно показывают, как эта самая матрица (часто companion matrix, но для xorshift может быть и иначе) выдает биты или машинные слова. Прям проговаривая и водя маркером.
3) Потом возводят матрицу в степень "период", и смотрят, получилась ли единичная матрица (что логично - оно должно в конце зациклиться)
4) Дальше возводят матрицу в степени "период / простой делитель периода" и смотрят, "не зациклилось ли по дороге".
5) Если ГПСЧ большой и матрицы тормозят, то можно уже переходить к характеристическим полиномам как к рекуррентным соотношениям. И через jump function проверять уже полиномы на примитивность. Отдельно показывая то, что деление многочленов уголком может соответствовать "промотке" членов последовательности.
В п.1 можно упростить себе жизнь, используя код на Си напрямую как математическую формулу.
Если M-последовательность удовлетворяет неким теоретическим критериям псевдослучайности, то откуда взялось столько странных ГПСЧ из LFSR с разреженными полиномами, проваливающих тесты на веса Хемминга или даже gap test? Тот же T800, LRND, вихрь Мерсенна без выходной функции, ещё куча ранних работ? У меня сложилось впечатление, что прогон хотя бы терабайта последовательности через PractRand и TestU01 не менее важен, чем теория. Также очень странны какие-либо мысли о ее криптостойкости, она же линейная.
Насколько я понимаю, это - тот самый алгоритм, который используется в тестах вроде Linear Complexity пакета статистических тестов TestU01 для того, чтобы "поймать" вихрь Мерсенна или xorshift64? Если да, то можно ли посмотреть на алгоритм Берлекэмпа-Месси как на высокооптимизированный для конкретной задачи (поиск коэффициентов рекуррентного соотношения) метод Гаусса, дающего уменьшение сложности по времени с O(n^4) до O(n^2)?
Неудобен ещё и зависимостью RAND_MAX от платформы. И ещё плохо то, что в стандарте Си приводят шуточный генератор в качестве примера для библиотеки. Наверное, наиболее радикальный и частично ломающий обратную совместимость способ - это потребовать в стандарте Си использования поточного шифра в rand(). Уж если менять генератор, то так, чтобы ещё на 50-100 лет его хватило бы.
Это да, в C++11 уже есть два быстрых и приличных генератора: mt19937 и mt19937_64. Когда в C++26 появится Philox - вообще хорошо станет, т.к. он и удобен для многопоточности, и все тесты проходит.
Вот бы это предупреждение из cppreference про rand() еще и в документацию glibc и man-страницы добавить.
Да, на bare metal с источником энтропии может быть не очень просто, тут соглашусь. Впрочем, можно было бы сделать так:
1) Внести в стандарт C требование использования поточного шифра и системного криптогенератора для инициализации в функции rand(). В стандарты C++ обязать это использовать как ГПСЧ по умолчанию в модуле random. В C++26 уже добавили почти криптографический Philox (но он - не шифр всё же), жалко, что хотя бы его не обязали использовать как генератор по умолчанию.
2) В случае отсутствия криптогенератора программа с использованием rand() должна просто не компилироваться, отключаться это должно только чем-то вроде #define USE_BAD_RANDOM_SEEDS
3) В случае невозможности использовать в rand() поточный шифр - аналогично. Компиляция должна включаться чем-то вроде #define USE_BITHACK_PRNG. И некриптографический генератор даже в этом случае должен выдерживать 128 ТиБ в PractRand и батареи TestU01.
Но насчёт криптографических примитивов: их использование в rand() - это эквивалент реализации синуса и косинуса с максимально возможной точностью. Но почему-то к одной математической функции (rand) считается допустимым куда более безалаберный подход, чем к функции sin.
Также из-за мьютексов в rand() glibc оно всё равно ощутимо медленнее AES. Считаю, что нужно либо менять ГПСЧ, либо добавлять предупреждение о низком качестве генератора в документацию glibc и man-страницах.
Возможно только о криптостойскости мы иногда не хотим думать
Ну а если не хотим думать, то почему бы не использовать криптографические примитивы как ГПСЧ по умолчанию? Да, это может не быть полноценным криптогенератором, но в случае сидирования от /dev/urandom или его аналогов хотя бы не даст катастрофических последствий при использовании для генерации паролей или ключей.
Я говорил о совсем вырожденных случаях, когда нам просто нужно чтобы "изменения были"
Тогда почему бы не использовать обычный счётчик?
С учебными ситуациями и тестированием ситуация с моей точки зрения такая:
Если в учебной задаче хоть что-то вычисляется, то целесообразно считать, что в качестве ГПСЧ по умолчанию нужен поточный шифр. Компромиссы вроде MT19937 возможны, но должны осознаваться как компромиссы.
rand() для написания тестов в принципе непригодна, т.к. в стандарте языка алгоритм не указан, и на разных платформах будет разная последовательность.
Насколько я помню, в DOOM так и делали, выдавали именно из закольцованного буфера, и всё нормально было. Но для меня сущая загадка, почему в rand() до сих пор остаются плохие алгоритмы, и man-страницы даже не предупреждают об этом. Если бы к ней подходили бы как к синусу или косинусу - там бы явно крутился бы по умолчанию поточный шифр.
Весь вопрос - что такое наколеночные случаи, как это формализовать. Я границу провожу просто - rand() подходит только в том случае, если устроит даже такой ГПСЧ как .
Конкретно функция rand() может причинить ущерб, если кто-то всерьёз решит, что она подчиняется равномерному распределению и её можно использовать для каких-то количественных оценок. Тут техдолг скорее в плохих алгоритмах в glibc и msvcrt.
В том-то и проблема, что более-менее приличный std::mt19937 - не дефолтный, а что будет выбрано по умолчанию - стандарт не специфицирует (default_random_engine теоретически может быть и какой-нибудь плохой генератор вроде minstd). А вообще я считаю, что ГПСЧ по умолчанию даже для некриптографических применений должен быть основан на каком-то поточном шифре вроде AES, ChaCha или ThreeFish.
У функции rand() есть одна проблема: ни одна из её широко распространённых реализаций не подчиняется равномерному распределению. Даже вариант из glibc с большим RAND_MAX проваливает простейшие проверки вроде birthday spacings или gap test.
Думаю, что личный выбор человека никак не может отменить или переписать биологическую эволюцию или естественный отбор. Человек - это тоже животное (и перестать быть животным автоматически означает перестать быть человеком), и продолжает эволюционировать, а наш разум и цивилизация - это просто еще один из вариантов адаптации к среде, резко повышающие живучесть.
Чтобы именно "переписать" естественный отбор нужно будет заменить его искусственным, т.е. генной инженерией человека.
Не заметили различия между ГПСЧ и ответами именно при использовании статистических критериев? Если да, то какие модификации критериев Вы использовали и какие p-значения получали? Провалы на гистограмме, выданные Алисой, часть статистических критериев скорее всгео "почувствует".
А что показывают критерии хи-квадрат и Колмогорова-Смирнова, примененные к этим последовательностям? Вообще "для розыгрышей" - это скорее даже не обычный ГПСЧ из библиотеки Python, а системный криптогенератор, т.к. генерация паролей или результатов лотереи - это криптография.
Кстати, они всё же похожи на реальные тесты, применяемые для контроля качества ГПСЧ, особенно там, где считают частоты подпоследовательностей и распределение весов Хемминга.
И какой теоретический критерий псевдослучайности используется на практике? Мне приходит в голову только тест на следующий бит. Ещё видел критерий "может ли ГПСЧ выдать все возможные комбинации чисел для n-мерных векторов".
Когда я поработал с LFSR в рамках хобби, то мне стало казаться, что математики порой ради высокой абстракции могут переусложнять многие вещи даже в научпопе. Да, теория нужна, но большинство людей мыслят не от абстракций, а от чего-то более осязаемого. Максимальность периода какого-нибудь xorshift можно доказать куда нагляднее:
1) Функция перехода ГПСЧ записывается в виде матрицы (и отдельно проговаривается, что тут всё не как обычно, т.е. вектор с битами пишут нередко горизонтально и слева от матрицы), операции в GF(2) объясняется по простому: заменяй сложение и вычитание на XOR, умножение - на AND. Да, тут возможны неочевидные нюансы в виде вырожденности матрицы, но обычно xorshift собирают по таблице с биективыми операциями над машинными словами.
2) Отдельно показывают, как эта самая матрица (часто companion matrix, но для xorshift может быть и иначе) выдает биты или машинные слова. Прям проговаривая и водя маркером.
3) Потом возводят матрицу в степень "период", и смотрят, получилась ли единичная матрица (что логично - оно должно в конце зациклиться)
4) Дальше возводят матрицу в степени "период / простой делитель периода" и смотрят, "не зациклилось ли по дороге".
5) Если ГПСЧ большой и матрицы тормозят, то можно уже переходить к характеристическим полиномам как к рекуррентным соотношениям. И через jump function проверять уже полиномы на примитивность. Отдельно показывая то, что деление многочленов уголком может соответствовать "промотке" членов последовательности.
В п.1 можно упростить себе жизнь, используя код на Си напрямую как математическую формулу.
Если M-последовательность удовлетворяет неким теоретическим критериям псевдослучайности, то откуда взялось столько странных ГПСЧ из LFSR с разреженными полиномами, проваливающих тесты на веса Хемминга или даже gap test? Тот же T800, LRND, вихрь Мерсенна без выходной функции, ещё куча ранних работ? У меня сложилось впечатление, что прогон хотя бы терабайта последовательности через PractRand и TestU01 не менее важен, чем теория. Также очень странны какие-либо мысли о ее криптостойкости, она же линейная.
Насколько я понимаю, это - тот самый алгоритм, который используется в тестах вроде Linear Complexity пакета статистических тестов TestU01 для того, чтобы "поймать" вихрь Мерсенна или xorshift64? Если да, то можно ли посмотреть на алгоритм Берлекэмпа-Месси как на высокооптимизированный для конкретной задачи (поиск коэффициентов рекуррентного соотношения) метод Гаусса, дающего уменьшение сложности по времени с O(n^4) до O(n^2)?
Неудобен ещё и зависимостью RAND_MAX от платформы. И ещё плохо то, что в стандарте Си приводят шуточный генератор в качестве примера для библиотеки. Наверное, наиболее радикальный и частично ломающий обратную совместимость способ - это потребовать в стандарте Си использования поточного шифра в rand(). Уж если менять генератор, то так, чтобы ещё на 50-100 лет его хватило бы.
Это да, в C++11 уже есть два быстрых и приличных генератора: mt19937 и mt19937_64. Когда в C++26 появится Philox - вообще хорошо станет, т.к. он и удобен для многопоточности, и все тесты проходит.
Вот бы это предупреждение из cppreference про rand() еще и в документацию glibc и man-страницы добавить.
Да, на bare metal с источником энтропии может быть не очень просто, тут соглашусь. Впрочем, можно было бы сделать так:
1) Внести в стандарт C требование использования поточного шифра и системного криптогенератора для инициализации в функции rand(). В стандарты C++ обязать это использовать как ГПСЧ по умолчанию в модуле random. В C++26 уже добавили почти криптографический Philox (но он - не шифр всё же), жалко, что хотя бы его не обязали использовать как генератор по умолчанию.
2) В случае отсутствия криптогенератора программа с использованием rand() должна просто не компилироваться, отключаться это должно только чем-то вроде #define USE_BAD_RANDOM_SEEDS
3) В случае невозможности использовать в rand() поточный шифр - аналогично. Компиляция должна включаться чем-то вроде #define USE_BITHACK_PRNG. И некриптографический генератор даже в этом случае должен выдерживать 128 ТиБ в PractRand и батареи TestU01.
Но насчёт криптографических примитивов: их использование в rand() - это эквивалент реализации синуса и косинуса с максимально возможной точностью. Но почему-то к одной математической функции (rand) считается допустимым куда более безалаберный подход, чем к функции sin.
Также из-за мьютексов в rand() glibc оно всё равно ощутимо медленнее AES. Считаю, что нужно либо менять ГПСЧ, либо добавлять предупреждение о низком качестве генератора в документацию glibc и man-страницах.
Ну а если не хотим думать, то почему бы не использовать криптографические примитивы как ГПСЧ по умолчанию? Да, это может не быть полноценным криптогенератором, но в случае сидирования от /dev/urandom или его аналогов хотя бы не даст катастрофических последствий при использовании для генерации паролей или ключей.
Тогда почему бы не использовать обычный счётчик?
С учебными ситуациями и тестированием ситуация с моей точки зрения такая:
Если в учебной задаче хоть что-то вычисляется, то целесообразно считать, что в качестве ГПСЧ по умолчанию нужен поточный шифр. Компромиссы вроде MT19937 возможны, но должны осознаваться как компромиссы.
rand() для написания тестов в принципе непригодна, т.к. в стандарте языка алгоритм не указан, и на разных платформах будет разная последовательность.
Насколько я помню, в DOOM так и делали, выдавали именно из закольцованного буфера, и всё нормально было. Но для меня сущая загадка, почему в rand() до сих пор остаются плохие алгоритмы, и man-страницы даже не предупреждают об этом. Если бы к ней подходили бы как к синусу или косинусу - там бы явно крутился бы по умолчанию поточный шифр.
Весь вопрос - что такое наколеночные случаи, как это формализовать. Я границу провожу просто - rand() подходит только в том случае, если устроит даже такой ГПСЧ как
.
Конкретно функция rand() может причинить ущерб, если кто-то всерьёз решит, что она подчиняется равномерному распределению и её можно использовать для каких-то количественных оценок. Тут техдолг скорее в плохих алгоритмах в glibc и msvcrt.
Единственное что - если такой упрощенный дефолт в язык заводить, то целесообразно сразу требовать использование поточного шифра в качестве движка.
В том-то и проблема, что более-менее приличный std::mt19937 - не дефолтный, а что будет выбрано по умолчанию - стандарт не специфицирует (default_random_engine теоретически может быть и какой-нибудь плохой генератор вроде minstd). А вообще я считаю, что ГПСЧ по умолчанию даже для некриптографических применений должен быть основан на каком-то поточном шифре вроде AES, ChaCha или ThreeFish.
У функции rand() есть одна проблема: ни одна из её широко распространённых реализаций не подчиняется равномерному распределению. Даже вариант из glibc с большим RAND_MAX проваливает простейшие проверки вроде birthday spacings или gap test.
Думаю, что личный выбор человека никак не может отменить или переписать биологическую эволюцию или естественный отбор. Человек - это тоже животное (и перестать быть животным автоматически означает перестать быть человеком), и продолжает эволюционировать, а наш разум и цивилизация - это просто еще один из вариантов адаптации к среде, резко повышающие живучесть.
Чтобы именно "переписать" естественный отбор нужно будет заменить его искусственным, т.е. генной инженерией человека.
Думаю, что это, пожалуй, единственный корректный способ сгенерировать случайные числа с помощью LLM. Особенно если код вручную перепроверить.
Не заметили различия между ГПСЧ и ответами именно при использовании статистических критериев? Если да, то какие модификации критериев Вы использовали и какие p-значения получали? Провалы на гистограмме, выданные Алисой, часть статистических критериев скорее всгео "почувствует".
Обычные - это какие именно?
А есть ли уверенность в том, что чатгпт и джемини запустят именно криптографический генератор, необходимый для лотерей и розыгрышей?
А что показывают критерии хи-квадрат и Колмогорова-Смирнова, примененные к этим последовательностям? Вообще "для розыгрышей" - это скорее даже не обычный ГПСЧ из библиотеки Python, а системный криптогенератор, т.к. генерация паролей или результатов лотереи - это криптография.