Сегодня мы пришли поболтать с вамислучайное число.
Если вы изучали программирование, вы должны быть знакомы со случайными числами и более или менее использовать их. Как бы плохо это ни было, наши еженедельные лотереи разыгрываются со случайными числами.Когда мы используем случайные числа, мы часто добавляем префикс, говоря, что этоПсевдослучайное число, тогда как объяснить псевдослово этого псевдослучайного числа, и что такое истинное случайное число?
Истинные и ложные случайные числа
В настоящее время способ деления истинных и ложных случайных чисел в академических кругах очень прост и может быть объяснен одним предложением.Все, что сгенерировано программой с использованием определенного алгоритма, является псевдослучайным числом., случайные числа, генерируемые физическими явлениями, являются действительно случайными числами. То есть ученые-вычислители доказали, что невозможно генерировать настоящие случайные числа, только полагаясь на алгоритмы, и это также можно рассматривать как проблему NP.
Доказательство того, что алгоритм генерирует псевдослучайные числа, слишком сложно, и мы можем его игнорировать, но что такое случайные числа, порождаемые физическими явлениями? На самом деле, это тоже очень просто.Очень простой пример — подбрасывание монет и бросание игральных костей. Конечно, помимо этих физических явлений, таких как шум электронных компонентов, распад элементов и так далее, существует нечто большее.
Где самая большая разница между истинными и ложными случайными числами? фактическио том, можно ли это предсказать. Причина, по которой все виды случайных чисел, полученных с помощью компьютерных алгоритмов, являются псевдослучайными числами, заключается в том, что их результаты предсказуемы.Пока мы знаем алгоритм, начальное состояние и различные параметры, мы можем предсказать следующий случайный результат. Действительно случайное число нельзя предсказать, оно чисто случайное.
Но вопрос в том, действительно ли физические явления подбрасывания монет и костей случайны? Если мы знаем начальное состояние монеты, а также угол и силу броска, можем ли мы предсказать результат броска монеты? Далее, можем ли мы предположить, что все так называемые случайные числа предсказуемы, если мы знаем все состояния всех примеров? Но в соответствии с принципом неопределенности квантовой механики мы знаем, что не можем знать положение и импульс частицы одновременно, что не только показывает, что мы не можем предсказать, но также показывает, что мы не можем предсказать гипотетически.
Так что в определенной степени вопрос о том, действительно ли физические явления случайны, стал философским вопросом. Но, по крайней мере, в компьютерной области эта проблема ясна, все алгоритмы представляют собой псевдослучайные числа, и только те, которые получены с помощью физических явлений, являются истинными случайными числами.
В компьютерной системе,Псевдослучайные числа являются периодическими, пока мы сохраняемся достаточное количество раз, мы можем видеть такие циклы. Для истинных случайных чисел такого цикла нет Старший провел эксперимент по визуализации случайных чисел, то есть результаты, полученные из случайных чисел, превратились в картинки. Интуитивно можно сравнить, вот такая картина после визуализации реального случайного числа:
Это похоже на то, что показывал старый телевизор, когда не было сигнала? Давайте посмотрим на результаты после визуализации псевдослучайных чисел, сгенерированных алгоритмом:
При сравнении это вполне очевидно, хорошо видно, что псевдослучайные числа регулярны, и эта закономерность отражается в текстуре на изображении. Если вы хотите получить настоящие случайные числа, вы можете посетить сайт random.org, это бесплатно, мы можем искусственно установить верхний и нижний пределы, чтобы получить случайные числа в заданном диапазоне.
После сравнения истинных и ложных случайных чисел давайте рассмотрим принцип алгоритма генерации псевдослучайных чисел, обычно используемого в компьютерных системах.
квадратный метод
Сначала мы вводим метод квадратов, который очень прост и груб и используется для генерации четырехзначных случайных чисел.
Какая конкретная логика? Сначала нам нужно случайное начальное число, скажем, 2333, мы возводим это случайное начальное число в квадрат, чтобы получить 5442889. Это число состоит всего из 6 цифр. Мы заполняем его 0 слева, чтобы получить 05442889, и, наконец, убираем его средние четыре цифры до 4428. Это результат, который мы получаем случайным образом. Когда мы вычислим случайное число в следующий раз, начальным числом случайного числа будет 4428.
Автор этого алгоритма — знаменитый отец компьютера.фон Нейман, который использовался с тех пор, как он определил архитектуру компьютера. Причина, по которой он хвалил этот алгоритм в то время, была очень проста, его было удобно вычислять, быстро и легко устранять ошибки. Он считает, что если сложный алгоритм действительно предназначен для генерации случайных чисел, которые хорошо выглядят, в нем может быть больше скрытых ошибок, чем решенных проблем.
seed = 2333
def random():
global seed
seed = seed ** 2
return int(str(seed)[1:5])
Я написал код и фактически запустил его, и результат не казался таким уж ненадежным.
Алгоритм LCG
Хотя алгоритм случайных чисел фон Неймана выглядит простым, он очень небрежен и, очевидно, не может использоваться во многих ситуациях. Вот и придумали люди новый алгоритм.Алгоритм этот тоже очень простой.Кажется английская аббревиатура высокая.На самом деле перевод такойЛинейная конгруэнтность. то есть использоватьдля генерации случайных чисел.
Окончательный возвращаемый результат — это результат вычисления по приведенной выше формуле, а три числа abc — это выбранные нами параметры. В следующий раз, когда это происходит случайно, последний результат используется в качестве нового начального значения для расчета. Запишем его рекуррентную формулу в виде:
Этот алгоритм ясен с первого взгляда, и его суть полностью заключается в выборе трех параметров abc. Если выбор неправильный, эффект случайного числа не может быть достигнут.Здесь я поделюсь с вами часто используемым выбором в отрасли, a = 25214903917, b = 11, c =. Эти числа не выбираются случайным образом, а рассчитываются учеными-компьютерщиками. ФактическиКласс Random в Java JDK использует такой алгоритм.
seed = 2
def lcg():
global seed
seed = (25214903917 * seed) & ((1 << 48) - 1)
return seed
Этот алгоритм также очень прост в реализации, и результаты также хороши. Если мы хотим увеличить случайность, мы также можем выполнить некоторую оптимизацию выходных результатов, например сдвиг или изменение порядка двоичных битов и т. д. Однако этот алгоритм также имеет тот недостаток, что его метод расчета фиксирован, но случайное начальное число неизвестно. пока ты хочешь,Мы можем вывести эти параметры, получив случайные результаты.
Это несложный алгоритм, поэтому случайное число, полученное алгоритмом LCG, нельзя использовать в некоторых приложениях с высоким уровнем безопасности, иначе могут возникнуть риски безопасности.
Алгоритм вращения Мерсенна
Псевдослучайное число, реализованное алгоритмом LCG, дает хороший эффект, но цикл недостаточно длинный, и хакерам легко вычислить случайное начальное число. Позже два японских ученых исследовали и предложили новый алгоритм псевдослучайных чисел, в котором используются простые числа Мерсенна, поэтому он называетсяАлгоритм вращения Мерсенна.
Краткое введение в простые числа Мерсенна, простые числа Мерсенна означают формупростые числа. Используя свойства простых чисел Мерсенна, можно создать период случайного числа с периодом, равным простому числу Мерсенна. Например, пакеты для вычисления случайных чисел, используемые в настоящее время в таких языках, как Python и C++11, используют этот алгоритм. Обычно используемые циклы текущей версии:
, что является огромной астрономической цифрой.
Принцип реализации алгоритма вращения Мерсенна очень сложен, и информации в Интернете не так много, я видел некоторые из них, и понять их не очень просто. Я не буду представлять это здесь, если вам интересно, вы можете проверить это. Но я лично не думаю, что это имеет большой смысл, потому что он действительно не используется, и интервью вообще не будет тестироваться.
Хотя период действия алгоритма вращения Мерсенна очень велик, он по-прежнему не является безопасным алгоритмом случайных чисел и может быть взломан хакерами. Однако по сравнению с алгоритмом LCG вероятность и сложность взлома значительно возросли.
Вам может быть любопытно, какой алгоритм безопасен? На самом деле алгоритмы безопасности в отрасли довольно сложны.Воспользуйтесь математической задачейразработать алгоритм. Например, алгоритм шифрования RSA использует проблему факторизации больших целых чисел. В отрасли нет хорошего метода для таких задач, кроме расчета методом полного перебора, а сложность расчета методом полного перебора очень и очень высока, и решить его за ограниченное время невозможно.Естественно, это безопасный алгоритм. Если у хакера есть возможность разработать алгоритм взлома, ему вообще не нужно ничего взламывать.Пока решение опубликовано в виде статьи, он, естественно, может получить известность и богатство.
Вы можете видеть, что за такой общей функцией случайных чисел скрывается такой глубокий научный принцип, и что еще более шокирует, так это то, что такая могущественная цивилизация, как мы, люди, не может даже вычислить случайное число. Не знаю, что ты чувствуешь, когда видишь это?
Вот и все, что касается сегодняшней статьи, и я искренне желаю вам удачи каждый день. Если вам все еще нравится сегодняшний контент, пожалуйста, зайдите на одинТройная поддержкабар~(Нравится, подписывайтесь, делайте репост)
Оригинальная ссылка, обратите внимание
В этой статье используетсяmdniceнабор текста