algorithm - 寻找5字节PRNG的种子

Question

这是一个古老的想法，但是从那以后，我一直无法找到某种合理的好方法来解决它提出的问题。因此，我“发明”了一个非常紧凑的，性能良好的PRNG(见下文)，但我无法弄清楚在大位深度上为其构建合适的种子值的算法。我当前的解决方案只是蛮力，它的运行时间是O(n ^ 3)。

生成器

我的想法来自XOR抽头(主要是LFSRs)，这些旧的8bit机器用于生成声音。我摆弄XOR作为C64的基础，试图将操作码放在一起，并对结果进行了体验。最终的工作解决方案如下所示:

asl
adc #num1
eor #num2

这是6502上的5个字节。选择正确的num1和num2，在累加器中以看似随机的顺序遍历所有256个值，也就是说，当用于填充屏幕时，它看起来是相当随机的(我写了一点256b演示然后在此)。有40对合适的num1和num2对，它们都给出了看起来不错的序列。

该概念可以很好地概括，如果用纯C表示，则可能看起来像这样( BITS是序列的位深度):

r = (((r >> (BITS-1)) & 1U) + (r << 1) + num1) ^ num2;
r = r & ((1U<<BITS)-1U);

由于此C代码具有通用性，因此它更长，即使使用无符号整数的完整深度，C也不会有必要的进位逻辑将移位的高位转移到加法运算。

有关一些性能分析和比较，请在问题后查看以下内容。

问题/问题

生成器的核心问题是找到合适的num1和num2，这将使其在给定位深度的整个可能序列上进行迭代。在本节的最后，我附上我的代码，该代码只是蛮力地执行它。它将在合理的时间内完成最多12位，您可以等待所有16位(顺便说一句，可能有5736对，前一整夜通过全搜索获得)，您可能会得到20位如果你有耐心。但是O(n ^ 3)真的很讨厌...

(谁将找到第一个完整的32位序列？)

出现其他有趣的问题:

对于num1和num2，只有奇数值才能产生完整序列。为什么？这可能并不困难(我想逻辑很简单)，但是我从来没有合理地证明过这一点。

沿num1(加值)有一个镜像属性，即如果给定'b'的'a'和num2给出了完整序列，则'a'的2个补码(在给定的位深度)与同样num2也是完整序列。我只观察到我计算的所有后代都可靠地发生了这种情况。

第三个有趣的属性是，对于所有num1和num2对，结果序列似乎形成了适当的圆，也就是说，至少数字零似乎始终是圆的一部分。没有此属性，我的强力搜索将死于无限循环。

奖励:此PRNG以前是否已知？ (而我只是重新发明了)？

这是蛮力搜索的代码(C):

#define BITS 16

#include "stdio.h"
#include "stdlib.h"

int main(void)
{
 unsigned int r;
 unsigned int c;
 unsigned int num1;
 unsigned int num2;
 unsigned int mc=0U;

 num1=1U;  /* Only odd add values produce useful results */
 do{
  num2=1U; /* Only odd eor values produce useful results */
  do{
   r= 0U;
   c=~0U;
   do{
    r=(((r>>(BITS-1)) & 1U)+r+r+num1)^num2;
    r&=(1U<<(BITS-1)) | ((1U<<(BITS-1))-1U); /* 32bit safe */
    c++;
   }while (r);
   if (c>=mc){
    mc=c;
    printf("Count-1: %08X, Num1(adc): %08X, Num2(eor): %08X\n", c, num1, num2);
   }
   num2+=2U;
   num2&=(1U<<(BITS-1)) | ((1U<<(BITS-1))-1U);
  }while(num2!=1U);
  num1+=2U;
  num1&=((1U<<(BITS-1))-1U); /* Do not check complements */
 }while(num1!=1U);

 return 0;
}

为了说明它是有效的，在每次迭代之后，如果序列长度等于或大于前一个序列，则会输出找到的对。修改其他深度序列的 BITS常数。

猎种子

我做了一些有关种子的绘图。这是显示所有9位序列长度的漂亮图像:

白色点是全长序列，X轴用于num1(加)，Y轴用于num2(异或)，点越亮，序列越长。其他位深度在模式上看起来非常相似:它们似乎都被分解为16个主要图块，其中两个模式重复镜像。磁贴的相似性并不完整，例如，从左上角到右下角的对角线上方清晰可见，而对角线不存在，但是对于全长序列，此属性似乎是可靠的。

以此为基础，可以比以前的假设进一步减少工作量，但这仍然是O(n ^ 3)...

性能分析

截至目前，可能生成的最长序列是24位:在我的计算机上，为此花了大约5个小时的时间才完成了完整的24位序列。对于真正的PRNG测试(例如 Diehard)来说，仍然还是这样，所以到目前为止，我宁愿自己尝试。

首先，重要的是要了解生成器的作用。出于简单性考虑，这绝不是一个很好的生成器，它的目标是生成快速燃烧的体面的数字。在不需要乘法/除法运算的区域上， Galois LFSR可以产生类似的性能。因此，如果我的生成器能够胜过这一生成器，那么它就将发挥任何作用。

我执行的测试都是16位生成器。我选择此深度是因为它提供了有用的序列长度，而数字仍可能分成两个8位的部分，从而可以显示各种精确的位图以进行可视化分析。

测试的核心是寻找与先前和当前生成的数字的相关性。为此，我使用了X:Y绘图，其中上一代是Y，当前是X，都按照上面针对两个图表所述的方式分解为低/高部分。我创建了一个程序，能够实时绘制这些台阶，从而还可以粗略地检查数字之间的相互关系，图表的填充方式。在这里，显然只有最终结果显示为生成器经历了完整的2 ^ 16或2 ^ 16-1(Galois)循环。

字段说明:

图像由8x2 256x256图形组成，使得图像总大小为2048x512(请以原始尺寸检查)。

左上方的图仅确认确实已绘制了完整序列，它只是X = r % 256; Y = r / 256;图。

左下图显示了第二个数字，其绘制方式与顶部相同，只是确认了数字合理地随机出现。

从第二张图的第一行开始是高字节相关图。他们中的第一个使用上一代，第二个跳过一个数字(因此使用第二个上一个)，依此类推，直到第7个上一个。

从第二行开始是低字节相关图，其组织方式与上述相同。

Galois发电机，0xB400丝锥组

这是在 Wikipedia Galois example中找到的生成器。它的性能不是最差的，但绝对不是很好。

Galois发电机，0xA55A分接头组

我发现的一个不错的伽罗瓦“种子”之一。请注意，16位数字的低端部分似乎比上面的要好得多，但是我找不到任何会混淆高字节的Galois“种子”。

我的生成器，0x7F25(adc)，0x00DB(eor)种子

这是我的最佳发生器，其中EOR值的高字节为零。限制高字节在8位计算机上很有用，因为如果可以承受随机性的损失，那么对于较小的代码和更快的执行，可以忽略此计算。

我的生成器，0x778B(adc)，0x4A8B(eor)种子

根据我的测量，这是优质种子之一。

为了找到具有良好相关性的种子，我建立了一个小程序，可以对它们进行某种程度的分析，就像Galois和我的方法一样。该程序确定了“优质”示例，然后我测试了其中几个，并从中选择了一个。

一些结论:

Galois生成器似乎比我的更严格。在所有相关图上，即使不是由线组成，也可以观察到确定的几何图案(有些种子会产生“棋盘状”图案，此处未显示)。我的生成器还显示了模式，但是随着世代的增加，它们的定义也越来越少。

Galois生成器结果的一部分，包括高字节中的位，似乎天生就很僵化，而我的生成器似乎没有该属性。这是一个微弱的假设，但可能还需要更多研究(以查看Galois生成器是否总是这样，而不是我的其他位组合是否如此)。

Galois生成器缺少零(最大周期为2 ^ 16-1)。

到目前为止，不可能为我的生成器生成20比特以上的良好种子集。

后来，我可能会更深入地研究该主题，以寻求使用Diehard来测试生成器的方法，但是到目前为止，由于缺少生成足够大的种子的能力，这使它变得不可能。

Answer 1

这是非线性移位反馈寄存器的某种形式。我不知道它是否已经被使用过，但是在某种程度上类似于线性移位反馈寄存器。阅读此Wikipedia页，作为LSFR的介绍。在伪随机数生成中经常使用它们。

但是，您的伪随机数生成器本质上是不好的，因为先前生成的数字的最高位和接下来生成的数字的最低位之间存在线性关系。将最高位B移出，然后新数字的最低位将是XOR或B，加法常量num1的最低位和XORed常数num2的最低位，因为二进制加法是等效的排他或最低位。您的PRNG最有可能存在其他类似缺陷。创建好的PRNG很难。

但是，我必须承认C64代码非常紧凑!