Почему бы не использовать простые числа для генераторов случайных чисел?

Question

Я не уверен, как работают rng в настоящее время, но я знаю, что они используют время как семя ... Итак, почему бы просто не использовать разные простые числа каждый раз? Насколько я знаю, простые числа - это единственная реальная случайная вещь, известная нам, так, например, каждый раз, когда программа запрашивает случайное число, вы даете ему n-е правое и увеличиваете n на единицу. Разве это не было бы чисто случайным? Потому что различия между nth и n + 1th!

Answer 1

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

1] Безопасность ГСЧ частично зависит от неспособности злоумышленника узнать, какое именно семя использовалось. В то время как расстояние между одним простым и следующим случайным образом, последовательность простых чисел не является случайной. Другими словами, 3 является простым, и я не могу предсказать, какое следующее правление будет основано на том, что 3 является простым. Но я уже знаю, что 5 является следующим простым (так как известны все числа с малым числом чисел). Исходя из вашего алгоритма, если я определяю, что семена для последних случайных чисел были 3, а затем 5, я могу догадаться, что следующее семя, которое вы будете использовать, будет 7. Таким образом, это не будет работать для низких простых чисел. Список простых чисел от 1 до 10 006 721 хорошо известен и опубликован.

2] Поиск простых чисел является сложным (вычислительно дорого). Хотя он дешевле для низких чисел, он становится очень дорогим для больших простых чисел. Большая часть кода, который использует случайные числа, предполагает, что число будет возвращено системой очень быстро, поэтому оно используется, например, в жестких петлях для игр. Этот алгоритм нарушит эти варианты использования.

Так что это не будет хорошим способом создания генератора случайных чисел.

Answer 2

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

Простые числа могут быть случайными .. но с учетом того же числа N i все равно будет генерировать одно и то же n + 1-е правое число, поэтому нет никакой разницы с нашими текущими псевдослучайными алгоритмами, но время простоя, генерирующее n + 1-е число, равно нулю постоянное время работы.

Использование времени в качестве семени - очень удобный способ сделать детерминированный быстрый алгоритм кажущимся случайным. Но это не так и ваш предложенный метод.

Подумайте о времени, когда ваше n и оба работают практически одинаково.