Генератор случайных чисел на основе счетчиков (CBRNG) - Counter-based random number generator (CBRNG)

А генерация случайных чисел на основе счетчика (CBRNG, также известный как генератор псевдослучайных чисел на основе счетчиков, или CBPRNG) является своего рода генератор псевдослучайных чисел который использует в качестве внутреннего состояния только целочисленный счетчик.

Фон

Мы можем думать о генераторе псевдослучайных чисел (PRNG) как о функции, которая преобразует последовательность битов, известную как государственный в новое состояние и случайное число.

То есть, учитывая функцию PRNG и начальное состояние ${\displaystyle \mathrm {state} _{0}}$, мы можем многократно использовать PRNG для генерации последовательности состояний и случайных чисел.

$${\displaystyle {\begin{aligned}\mathrm {PRNG} (\mathrm {state} _{0})&=\mathrm {state} _{1},\ \mathrm {num} _{1}\\\mathrm {PRNG} (\mathrm {state} _{1})&=\mathrm {state} _{2},\ \mathrm {num} _{2}\\\mathrm {PRNG} (\mathrm {state} _{2})&=\mathrm {state} _{3},\ \mathrm {num} _{3}\\\mathrm {PRNG} (\mathrm {state} _{3})&=\ldots \end{aligned}}}$$

В некоторых ГПСЧ, таких как Мерсенн Твистер, состояние большое, более 2048 байт. В других ГПСЧ, таких как xorshift, ${\displaystyle \mathrm {state} _{i}}$ и ${\displaystyle \mathrm {num} _{i}}$ являются одним и тем же (и поэтому состояние небольшое, всего 4, 8 или 16 байтов, в зависимости от размера генерируемых чисел). Но в обоих случаях, как и в большинстве традиционных ГПСЧ, состояние меняется непредсказуемо, поэтому, если вы хотите рассчитать конкретный ${\displaystyle \mathrm {state} _{i}}$ учитывая начальное состояние ${\displaystyle \mathrm {state} _{0}}$, вы должны рассчитать ${\displaystyle \mathrm {state} _{1}}$, ${\displaystyle \mathrm {state} _{2}}$и так далее, запуская ГПСЧ ${\displaystyle i}$ раз.

Такие алгоритмы по своей сути последовательный и не может работать на параллельных машинах, например многоядерные процессоры и GPU.

Напротив, генератор случайных чисел на основе счетчиков (CBRNG) - это ГПСЧ, в котором состояние «эволюционирует» особенно простым способом: ${\displaystyle \mathrm {state} _{i}=i}$. Таким образом, вы можете генерировать каждое число независимо, не зная результата предыдущего вызова ГПСЧ.

Это свойство упрощает запуск CBRNG на нескольких потоках ЦП или графическом процессоре. Например, чтобы сгенерировать ${\displaystyle n}$ случайные числа на графическом процессоре, вы можете создать ${\displaystyle n}$ темы и иметь ${\displaystyle i}$й поток вычислить ${\displaystyle \mathrm {PRNG} (i)}$.

Реализации

CBRNG на основе блочных шифров

Некоторые CBRNG основаны на версиях пониженной силы блочные шифры. Ниже мы объясним, как это работает.

При использовании криптографического изображения блочный шифр в режим счетчика, вы генерируете серию блоков случайных битов. В ${\displaystyle i}$-й блок вычисляется путем шифрования числа ${\displaystyle i}$ с использованием ключа шифрования ${\displaystyle k}$: ${\displaystyle \mathrm {Block} _{i}=E(i,k)}$.

Это похоже на CBRNG, где вы вычисляете ${\displaystyle i}$th случайное число как ${\displaystyle \mathrm {PRNG} (i)}$. Действительно, любой блочный шифр может использоваться как CBRNG; просто позвольте ${\displaystyle \mathrm {PRNG} (i)=E(i,\mathrm {seed} )}$!

Это дает сильный, криптографически безопасный источник случайности. Но криптографически безопасные генераторы псевдослучайных чисел обычно работают медленнее по сравнению с небезопасными ГПСЧ, и на практике многие виды использования случайных чисел не требуют такой степени безопасности.

В 2011 году Salmon et al. в D. E. Shaw Research представил^[1] два CBRNG, основанные на версиях блочных шифров с пониженной стойкостью.

• Threefry использует версию уменьшенной силы Три рыбы блочный шифр. (Молодые рыбы известны как "жарить ".)

• ARS использует версию уменьшенной силы AES блочный шифр. («ARS» - это игра слов от «AES»; «AES» означает «расширенный стандарт шифрования», а «ARS» означает «расширенная система рандомизации».^[2].)

ARS используется в последних версиях Intel Математическая библиотека ядра^[3] и получает хорошую производительность, используя инструкции из AES-NI набор инструкций, которые специально ускоряют шифрование AES.

Код, реализующий Threefry, ARS и Philox (см. Ниже), доступен у авторов.^[4]

CBRNG на основе умножения

В дополнение к Threefry и ARS Salmon et al. описал третий ГПСЧ на основе счетчиков, Филокс. Он основан на широких умножениях, например умножение двух 32-битных чисел и получение 64-битного числа или умножение двух 64-битных чисел и получение 128-битного числа.

По состоянию на 2020 год Philox популярен среди процессоров и графических процессоров. На графических процессорах, nVidia библиотека cuRAND^[5] и TensorFlow^[6] предоставить реализации Philox. На процессорах Intel MKL обеспечивает реализацию.

В 2020 году Бернард Видински опубликовал Squares CBRNG.^[7][8] Squares основан на Джон фон Нейман С метод среднего квадрата, применяя несколько раундов к счетчику для получения случайного результата. ГПСЧ Squares отличается своей чрезвычайно простотой, всего 8 строк кода C.

Рекомендации

1. Лосось, Джон; Мораес, Марк; Дрор, Рон; Шоу, Дэвид (2011). «Параллельные случайные числа: так же просто, как 1, 2, 3». Материалы Международной конференции по высокопроизводительным вычислениям, сетям, хранению данных и анализу 2011 г., статья № 16. Дои:10.1145/2063384.2063405.
2. http://www.thesalmons.org/john/random123/releases/1.11.2pre/docs/. Получено 8 августа, 2020. Отсутствует или пусто | название = (помощь)
3. Федоров, Геннадий; Гладков, Евгений (2015). «Новые генераторы случайных чисел на основе счетчиков в библиотеке Intel® Math Kernel». Intel. Получено 22 августа, 2016.
4. "Random123".
5. https://docs.nvidia.com/cuda/curand/device-api-overview.html. Получено 8 августа, 2020. Отсутствует или пусто | название = (помощь)
6. https://www.tensorflow.org/guide/random_numbers#general. Отсутствует или пусто | название = (помощь)
7. Видинский, Бернар (апрель 2020 г.). «Квадраты: быстрый ГСЧ на основе счетчиков». arXiv:2004.06278v3.
8. Сайт Squares RNG