生成(完全确定的)伪随机比特流

Question

受随意地绑着你的手启发：

目标

这个挑战的目标是编写一个生成伪随机比特流的程序，它是一个由1s和0组成的字符串，看起来完全是随机的，但实际上是以确定性的方式生成的。您的程序应该输出1和0的字符串(带有可选的空格)，并应满足以下要求：

1. 给定无限的时间和内存，您的程序必须永远继续输出1和0的字符串。
2. 你的程序必须在一台合理的机器上，在大约一分钟内输出1000多个随机位。如果这个要求是不可能的，那我就减少它。
3. 位串可以重复，但是重复段的长度必须超过1000位。
4. 位串必须通过尽可能多的随机性测试(如下所述)。
5. 程序不能从任何外部源接收任何输入，也不能使用任何内置的rand()-like函数。
6. 由于上述要求，程序每次运行时都必须输出相同的位串。

随机检验#1

伪随机位的字符串在视觉检查时不能包含任何明显的图案。

随机性测试#2 (根据注释可能发生变化)

位串必须包含相同分布的1s和0。为了测试这一点(以及其他事情也是如此)，比特流被分解成3位长的段，比如101|111|001。

在所有这些片段中，1/8应该有3个1s而不是0，3/8应该有两个1s和一个0，3/8应该有1和2 0，1/8应该没有1和3 0。

随机性测试#3

"run“被定义为一系列连续的位，它们都具有相同的值。字符串1001001110有三次大小为1 (1..1.....0)、两次为2次(.00.00....)和一次为3次(......111.)的运行。注意，运行不重叠。

在1000个随机位串中，应该有250个大小的运行，125个大小的运行，62个大小的运行，等等。一般来说，对于运行大小R，应该有类似大小的1000/(2**(R+1))运行。

随机性测试#4

第一840位被分成两半，每个420位。上半部分的每一个位与下半部分的对应位进行比较。两位应该匹配大约百分之五十的时间。

这里是执行测试2到4的Perl程序的源代码。到目前为止，它要求位串不包含任何空格。

目标赢得标准时间！

胜利者是通过所有6项要求和所有随机性测试的程序，达到与随机性无法区分的程度。如果多个程序完成了这一任务，那么重复所需时间最长的程序将获胜。如果多个程序实现了这一点，那么我可能必须找到更多的随机性测试来充当平分器。

Answer 1

这个问题实质上等同于“实现流密码”。所以我实现了RC4，因为它比较简单。

我不使用键，并删除前100000位，因为RC4的开头有点偏颇，特别是因为我跳过了密钥计划。但我希望它能够通过您的测试，即使没有它(节省20个字符的代码)。

通常情况下，每个周期都会输出一个完整的字节，但是在C#中转换为二进制非常难看，所以我只是简单地放弃了所有的东西，除了最不重要的位。

var s=Enumerable.Range(0,256).ToArray();
byte i=0,j=0;
for(int k=0;;k++)
{
    i++;
    j+=(byte)s[i];
    var t=s[i];s[i]=s[j];s[j]=t;
    if(k>99999)
        Console.Write(s[i]+s[j]&1);
}

或无空位：

var s=Enumerable.Range(0,256).ToArray();byte i=0,j=0;for(int k=0;;k++){i++;j+=(byte)s[i];var t=s[i];s[i]=s[j];s[j]=t;if(k>99999)Console.Write(s[i]+s[j]&1);}

C#，156个字符，在LinqPad的语句模式下工作。对于一个完整的C#程序，添加通常的样板。

我们还可以使用内置的密码原语(Cheater解决方案)：

var h=SHA256.Create();for(BigInteger i=0;;i++){Console.Write(h.ComputeHash(i.ToByteArray())[0]%2);}

(C#，99个字符，在LinqPad的语句模式下工作。对于普通的C#编译器，您需要添加一些样板)

密码散列函数的输出被设计成与随机数据无法区分，所以我希望它能够通过所有的随机性测试(更难，.)你扔了它，但我太懒了，不愿意测试。

Answer 2

JavaScript - 1ms至2ms为1000伪随机比特(139 1ms至153 1ms为100000位)

这个解使用了一个事实，即平方根是非理性的，因此几乎是随机的。基本上，它需要2的平方根开始，将其转换为二进制，抛出与前一个根匹配的主导部分，将其附加到随机字符串中，用下一个更高的数字重复(如果数字重复并且至少有30位长，则返回到2)，并在足够长时返回随机字符串。

var getDeterministicPseudoRandString = function(length){
    var randString = '';

    var i = 2;
    var prevRand = '';

    outerLoop:
    while(randString.length < length){
        var nextRand, nextFullRand = Math.sqrt(i++).toString(2).substring(1).replace('.', '');
        nextRand = nextFullRand;
        for(var j = prevRand.length; j > 0; j--){
            var replaceString = prevRand.substring(0, j);

            nextRand = nextFullRand;

            if(nextFullRand.indexOf(replaceString) == 0){
                if(j == prevRand.length && j > 30){
                    //start i over at 2
                    console.log('max i reached: ' + i);

                    i = 2;
                    continue outerLoop;
                } else {
                    nextRand = nextFullRand.replace(replaceString, '');
                }

                break;
            }
        }
        prevRand = nextFullRand;

        randString += nextRand;
    }

    return randString.substring(0, length);//Return the substring with the appropriate length
};

我还没有通过测试，但我想它会做得很好。这里有把小提琴，这样你就可以看到它的作用了。对于我的时间，我只是运行了几次程序，并以最快和最慢的值作为范围。

Answer 3

Python

import hashlib
x=''
while 1:
    h=hashlib.sha512()
    h.update(x)
    x=h.digest()
    print ord(x[0])%2

应该有2^512左右的周期。