- проходит все статистические тесты
Каждый PRNG, упомянутый в других ответах, до сих пор широко принадлежит к семейству GNSR / LFSR PRNG. Все они не соответствуют бинарному рангу матрицы и, возможно, тестам линейной сложности.
Есть много много PRNG, которые проходят все статистические тесты общего назначения, но по некоторым причинам люди, кажется, считают GFSR более сексуальными.
Вот пример PRNG, который проходит все статистические тесты общего назначения, но не является криптографически безопасным:
static unsigned long long rng_a, rng_b, rng_c, rng_counter;
unsigned long long rng64() {
unsigned long long tmp = rng_a + rng_b + rng_counter++;
rng_a = rng_b ^ (rng_b >> 12);
rng_b = rng_c + (rng_c << 3);
rng_c = ((rng_c << 25) | (rng_c >> (64-25))) + tmp;
return tmp;
}
void seed(unsigned long long s) {
rng_a = rng_b = rng_c = s; rng_counter = 1;
for (int i = 0; i < 12; i++) rng64();
}
(Предполагается, что long long - это 64-битный целочисленный тип ... Я думаю, это верно везде, где этот тип определен?)
Этого вполне достаточно для любого обычного использования, а также достаточно быстро. Если вам нужно что-то лучше, переключитесь на CSPRNG - они, как правило, намного лучше, чем любой не крипто-PRNG. Например, ChaCha (http://cr.yp.to/chacha.html) - это сплошная CSPRNG с быстрым посевом, произвольным доступом и регулируемым качеством. HC-256 (http://en.wikipedia.org/wiki/HC-256) - это еще более качественный CSPRNG, он медленный, но достаточно быстрый после посева.
- ведет себя хорошо даже при очень больших размерах
Это в значительной степени эквивалентно пункту № 1. Кроме того, пример PRNG, который я предложил, относится к хаотическому типу - такие PRNG, если они плохо себя ведут, делают это при небольшом количестве измерений, а не при большом количестве.
- имеет чрезвычайно большой период
Определить чрезвычайно большой?
Пример PRNG, который я предложил выше, имеет доказуемый минимальный период 2 ^ 64, средний период 2 ^ 255 и пространство состояний 2 ^ 256. Для двух CSPRNG, которые я связал, ChaCha имеет период 2 ^ 68 и пространство состояний 2 ^ 260, а HC-256 имеет средний период где-то порядка 2 ^ 65000 или около того IIRC и предлагает вероятностное доказательство того, что его кратчайший цикл больше 2 ^ 128 с вероятностью больше 1- (2 ^ -128) и имеет пространство состояний около 2 ^ 65000.
На практике период не имеет значения более 2 ^ 60, и даже это маргинально. Обычно причина, по которой люди спрашивают о высоком периоде, заключается в том, что либо они не знают, о чем говорят, либо потому, что им нужно большое пространство состояний (которое, по крайней мере, равно периоду, но часто больше), что может быть полезно около 2 ^ 250. Но большое пространство состояний не очень поможет, если вы не заполняете что-то большее, чем одно целое число, а большинство людей этого не делают.
(примечание: в коде ^ используется для обозначения xor, но в тексте ^ используется для обозначения показателя степени)