Генератор случайных чисел на основе счетчика

( Генерация случайных чисел на основе счетчика CBRNG , также известная как генератор псевдослучайных чисел на основе счетчика или CBPRNG) — это своего рода генератор псевдослучайных чисел , который использует только целочисленный счетчик в качестве своего внутреннего состояния. Обычно они используются для генерации псевдослучайных чисел для больших параллельных вычислений.

Фон

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

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

$${\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}}$$

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

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

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

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

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

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

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

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

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

В 2011 году Салмон и др. в DE Shaw Research представили два CBRNG, основанные на версиях блочных шифров пониженной стойкости.

• Threefry использует уменьшенную версию блочного шифра Threefish . (Молодь рыбы известна как « мальки ».)

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

ARS используется в последних версиях библиотеки Intel Math Kernel Library. и обеспечивает хорошую производительность за счет использования инструкций из набора инструкций AES-NI , которые специально ускоряют шифрование AES.

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

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

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

По состоянию на 2020 год Philox популярен среди процессоров и графических процессоров. На графических процессорах — nVidia . библиотека cuRAND от и ТензорФлоу предоставить реализации Philox. Intel MKL На процессорах реализацию обеспечивает .

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