Является ли Random.NextBytes предвзятым?

Справочный источник .NET показывает реализацию NextBytes() виде:

for (int i=0; i<buffer.Length; i++)
{
    buffer[i]=(byte)(InternalSample()%(Byte.MaxValue+1)); 
}

InternalSample предоставляет значение в [0, int.MaxValue), о чем свидетельствует его комментарий к документу и тот факт, что Next(), который задокументирован для возврата этого диапазона, просто вызывает InternalSample.

Меня беспокоит то, что, поскольку InternalSample может выдавать различные значения int.MaxValue, а это число не делится на 256 равномерно, то в результирующих байтах должно быть небольшое смещение, причем некоторые значения (в данном случае только 255) встречаются реже чем другие.

Мой вопрос:

  1. Является ли этот анализ правильным или метод на самом деле объективен?
  2. Если предвзятость существует, достаточно ли она важна для любого реального применения?

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

Ответы

Ответ 1

Ваш анализ действительно правильный. Но дефект составляет одну часть на два миллиарда, т.е. 1/2^31 так что ничтожно мал.

Вопрос, который нужно задать, таков: это вообще можно обнаружить? Например, сколько образцов N нужно, чтобы установить смещение, скажем, с уверенностью 99%. Из того, что я знаю, N> s ^ 2 z ^ 2/epsilon ^ 2, с

  • z = 2,58,
  • эпсилон = 1/2 ^ 32 и
  • s ^ 2 = p - p ^ 2
  • р = 1/2 ^ 8 - 1/2 ^ 31

для этого потребуется 4,77 × 10 17 выборок, такое большое число, что вряд ли будет самым очевидным дефектом.

Ответ 2

См. Knuth vol. 2, 3.2.1.1 Выбор модуля. Вам действительно нужен модуль, который не равен 256; используя 256, младшие 4 бита результирующего байта значительно менее случайны, чем полученные с использованием 257 (стр. 12).

257 также является простым, что удобно для уменьшения смещения и удлинения псевдослучайной последовательности.

Любая псевдослучайная последовательность по определению не является по-настоящему случайной. Что касается некриптографических приложений, что беспристрастно? Если у вас есть сомнения, моя рекомендация состоит в том, чтобы пробовать сгенерированные числа, как ваше приложение собирается их рисовать, и делать некоторый статистический анализ. Встроенные генераторы случайных чисел достаточно хороши для многих приложений, но не всегда достаточно хороши для ваших.