保证值序列所有可能排列的伪随机分布 - C++

Question

随机问题。

我正在尝试创建一个可以生成伪随机分布的程序。我正在尝试找到适合我的需求的伪随机算法。这些是我的担忧：

1）我需要一个输入来在每次使用时生成相同的输出。

2) 它需要足够随机，以便查看输入 1 的输出的人看不到该输出与输入 2 的输出（等等）之间的联系，但它不需要密码安全或真正随机。

3）它的输出应该是 0 到 (29^3200)-1 之间的数字，该范围内的每个可能的整数都是可能且同等（或接近）可能的输出。

4) 我希望能够保证 410 个输出序列的每个可能排列也是连续输入的潜在输出。换句话说，0 到 (29^3200)-1 之间的 410 个整数的所有可能分组都应该是顺序输入的潜在输出。

5）我希望该函数是可逆的，这样我就可以采用一个整数或一系列整数，并说出哪个输入或一系列输入会产生该结果。

到目前为止我开发的方法是通过一个简单的 halson 序列运行输入：

boost::multiprecision::mpz_int denominator = 1;
boost::multiprecision::mpz_int numerator = 0;

while (input>0) {
    denominator *=3;
    numerator = numerator * 3 + (input%3);
    input = input/3;
}

并将结果乘以 29^3200。它满足要求 1-3，但不满足 4。并且它仅对于单个整数是可逆的，而不是序列（因为并非所有序列都可以由它产生）。我正在 C++ 中工作，使用 boost 多精度。

有人可以给我任何关于生成满足这些要求的随机分布的方法的建议，或者只是一类值得为此目的研究的算法，我将不胜感激。预先感谢您考虑我的问题。

- - 更新 - -

由于多个评论者都关注相关数字的大小，我只是想明确表示，我认识到使用此类集合所带来的实际问题，但在提出这个问题时，我只对理论或概念方法感兴趣问题 - 例如，想象一下使用更小的整数集（如 0 到 99），以及 10 个输出序列的排列。您将如何设计一个算法来满足这五个条件 - 1）输入是确定性的，2）看起来是随机的（至少对于人眼来说），3）范围内的每个整数都是可能的输出，4）不仅仅是所有值，而且值序列的所有排列都是可能的输出，5）函数是可逆的。

---第二次更新---

非常感谢@Severin Pappadeux，我能够反转 lcg。我想我应该添加一些关于我所做的事情，希望能让将来看到这一点的人更容易。首先，这些是关于反模函数的优秀资源：

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-inverses

https://www.khanacademy.org/computer-programming/discrete-reciprocal-mod-m/6253215254052864

如果您采用方程 next=ax+c%m，则使用以下代码以及 a 和 m 的值将打印出您需要找到 ainverse 的欧几里得方程以及 ainverse 的值：

    int qarray[12];
    qarray[0]=0;
    qarray[1]=1;
    int i =2;
    int reset = m;
    while (m % a >0) {
      int remainder=m%a;
      int quotient=m/a;
      std::cout << m << " = " << quotient << "*" << a << " + " << remainder << "\n";
      qarray[i] =qarray[i-2]-(qarray[i-1]*quotient);
      m=a;
      a=remainder;
      i++;
  }
if (qarray[i-1]<0) {qarray[i-1]+=reset;}
std::cout << qarray[i-1] << "\n";

我花了一段时间才弄清楚的另一件事是，如果你得到负面结果，你应该在其中添加 m 。您应该在新方程中添加一个类似的术语：

prev = (ainverse(next-c))%m;
if (prev<0) {prev+=m;}

我希望这对未来走这条路的人有所帮助。

Answer 1

好吧，我不确定是否有一个通用的答案，所以我会专注于具有 64 位内部状态/种子、产生 64 位输出并具有 2^64-1 周期的随机数生成器。特别是，我会研究以下形式的线性同余生成器（又名 LCG）：

next = (a * prev + c) mod m

其中a和m互质

所以：

1）检查

2）检查

3）检查（当然是64位空间）

4）检查（再次，除了 0 我相信，但是 64 位的每个排列都是以一些种子开始的 LCG 的输出）

5）检查。LCG 已知是可逆的，即可以得到

prev = (next - c) * a_inv mod m

其中 a_inv 可以使用欧几里得算法a从计算得出m

好吧，如果你觉得没问题，你可以尝试在你的 15546 位空间中实现 LCG

更新

快速搜索显示可逆 LCG 讨论/代码

可逆伪随机序列发生器