Случайно перебирайте последовательность целых чисел, от 1 до n

Question

У меня есть целый ряд целых чисел, в которые я хочу выполнить итерацию. Вы можете предположить, что последовательность начинается с 1 и заканчивается n, где n > 1. Тем не менее, я не хочу последовательно проходить через них. Цель состоит в том, чтобы перебрать все из них случайным образом. Кроме того, n может быть очень большим, возможно, в триллионы, поэтому я не могу хранить диапазон в памяти. Есть ли способ сделать это?

Я знаю, что есть способ сделать это с помощью массива, уже находящегося в памяти. Можно ли сделать что-то подобное, если вы не можете сразу сохранить весь диапазон?

Answer 1

Вы можете использовать Format-Preserving Encryption для шифрования счетчика.

Выберите симметричный шифр, созданный для шифрования чисел до N. (Вы можете использовать предложенную схему AES-FFX). Затем сгенерируйте случайный ключ с высокой энтропией и начните шифровать числа 0, 1, 2,. .. вверх. Поскольку шифрование обеспечивает сопоставление 1: 1 и хорошее шифрование выглядит случайным, вы получите последовательность неповторяющихся случайных чисел, используя только O (1) хранилище.

Использование блочного шифрования в counter mode (CTR) является хорошо известной методикой для создания cryptographically secure pseudo-random number generator (CSPRNG). Раздел 10.2.1. NIST SP 800-90A дает дополнительные советы. Использование AES в качестве базового блока шифрования рекомендуется для стохастического моделирования, так как качество случайности does not show any statistical weaknesses.

Идея ничего, кроме новых и уже предложил на StackOverflow несколько раз по Craig McQueen:

• Generating non-repeating random numbers in Python
• Unique (non-repeating) random numbers in O(1)?
• Generating millions of non-repeating random numbers in Java

Также crypto.stackexchange имеет несколько потоков о это:

• Random Number Generator based on AES CTR
• How do I produce a stream of secure random numbers from AES-Counter mode?