math - 如何制作一次接受一个值的置换函数？

Question

我正在寻找一个函数，该函数从0,1 .... N间隔接受1个数字，并从同一间隔返回一个置换值。

0、1、2、3、4、5和f（x）的示例为：

f(0)=5;
f(1)=1;
f(2)=0;
f(3)=4;
f(4)=2;
f(5)=3;

根据我的研究/了解，这是一个循环群，其中f（x）是所有循环群的基础。
如果发现函数f（x）= 911 * x％N是我想要的示例，但是使用此函数时会出现模式。 911是一个很大的质数，通过更改它，我得到了另一个排列，但仍然出现了atter啪声。我希望结果是随机的。

我知道我可以使用[0，1，2 ... N] .shuffle（）之类的东西来预生成置换，但是就我而言，我不能做这样的事情。

我有一项服务，需要输入一个数字值并返回排列的值/位置。 N是在服务器端设置的，所以我要查找的功能也是如此。

Answer 1

请记住，我在这里描述的算法基于列表[1、2，... N-1]（长度为N-1）。如果您坚持使用列表[0，1，...，N]（长度为N + 1），请应用所需的较小修改。此外，为简洁起见，我使用％操作数的方式与大多数编程语言略有不同：a％b取值介于1和b之间，而不是0和b-1之间，但是当然，后面的主要思想没有改变，因此a％b的值是1到b之间的整数，与a取模b相等。

如果通读此书，对于您来说很明显，所产生的混洗根本不是随机的。但是，通过精心选择的参数，模式将不容易识别（我的模块化幂运算的基本思想来自密码学，在密码学中，不可识别的模式和不可恢复的功能非常重要）。

与实际的编程解决方案相比，这更是算法的语言不可知的描述。我不会详细介绍您可能遇到的有效实施和陷阱。希望对您有所帮助。我还用python编写了部分代码，因此我可以提供更多帮助，甚至在需要时共享我的代码，但这之前需要先完成和重构。

使用幂运算而不是乘法来消除模式

f（x）= t * x％N（您选择t为911的位置）的初始试验显示了一些模式，因为乘法具有线性（在其“模数”意义上）。

如果您使用指数运算而不是乘法运算，则可以赋予更多随机感。像f（x）= t ^ x％N。但是，必须明智地选择t（因为在乘法情况下，它是N的素数），并且此公式给出的输出不会提供明显的区别。仅在N为质数的情况下，不同x值的数字。

大学水平的数学即将到来，请忍受，我会尽量保持简单。

我们将需要使用原始根。相关的Wikipedia article可能有很大帮助，但是基本思想是，精心选择的基数的幂的余数取1到N-1之间的所有值。例如

3^1 = 3
3^2 = 9 = 2 (mod 7)
3^3 = 27 = 6 (mod 7)
3^4 = 81 = 4 (mod 7)
3^5 = 243 = 5 (mod 7)
3^6 = 729 = 1 (mod 7)

都不同（从这一点开始，值从头开始重复：3 ^ 7 = 3 ^ 1（mod 7），3 ^ 8 = 3 ^ 2（mod 7），依此类推）。

因此，如果您的N为7，则3可以很好地成为t。您可以将f（x）=（3 ^ x）％7用于1到6之间的x值。

结果为以下f：

f(1) = 3
f(2) = 2
f(3) = 6
f(4) = 4
f(5) = 5
f(6) = 1

引入移位，提供一些附加的随机效果

如果您对此进行一点操作，您会发现N-1始终会改编为1。如果要避免这种情况，我们可以更进一步，并选择任意数字k求幂。也就是说，使用g（x）=（f（x）+ k）％（N-1）=（（t ^ x）％N + k）％（N-1），在我们的示例中，令k为2，导致排列：

g(1) = 5
g(2) = 4
g(3) = 2
g(4) = 6
g(5) = 1
g(6) = 3

如何选择基地

现在您有了基本的感觉。但是，当N不是7时，通常如何使用呢？

问题的关键是选择参数t，在我们的示例中为3。

不幸的是，这通常是一个棘手的问题（数学家称之为 finding a primitive root），而且我所知道的并没有任何易于理解的即用型解决方案。

但这只是问题的一部分。更可悲的是，如果N是一个复合数，则原始根甚至不起作用。例如，如果N = 6，则不存在任何数字t，其表达式t ^ x模6取1到5之间的所有值。

但是解决这一部分并不难。

如何处理复合N

如果N是合成的，我们应该找到一个几乎不大的素数P，并基于该素数通过将出界后的数字替换为它们的洗后值（并在需要时进行迭代）来构建该算法。 。

例如，如果N为6，我们可以选择P为7并使用我们先前构造的g（x）。

g(1) = 5 ok (5<=N-1 holds)                          h(1) = 5
g(2) = 4 ok                                         h(2) = 4
g(3) = 2 ok                                    =>   h(3) = 2
g(4) = 6 too large, using g(g(4)) = g(6) = 3        h(4) = 3
g(5) = 1 ok                                         h(5) = 1

为了安全起见，我举另一个例子，N = 4，我们使用先前计算的P = 7解。

g(1) = 5, g(5) = 1                                  h(1) = 1
g(2) = 4, g(4) = 6, g(6) = 3                   =>   h(2) = 3
g(3) = 2                                            h(3) = 2

现在应该清楚了。选择接近N的P是明智的做法，因此对于g的越界值并不需要太多的重新计算。

回到寻找

因此，我们剩下的唯一问题是找到可以用作求幂基础的原始根。

如果我之前链接的页面上的数学引起一些内心的恶心，那么我对您来说有个好消息：可能的t好的值在[2，N-1]区间内密集，因此即使是随机猜测也可能有所帮助。

在链接的页面上有一些细节如何有效地验证随机选择的t是否真的对我们有用，但是除非您使用的是非常大的数字，否则您可以进行幂运算并检查数字1是否早于（ t的N-1次幂（也许您还记得我注意到在x = N-1的情况下t ^ x = 1（mod N）总是成立的，所以更早出现1会破坏唯一性）。

我建议您在N / 2附近寻找合适的t（意味着数量级-对于P = 91367，t = 54949可以正常工作）。如果您选择t太低（例如t = 2），则可以很容易地在一些相邻的x值上发现由幂运算引起的模式（2 + k，4 + k，8 + k，...将出现在旁边）彼此）。如果t太接近N，则如果在相同奇偶校验的连续x值中查看f（x），可能会出现类似现象。最好选择t来覆盖这些模式，并以足够随机的结果结束。

摘要

再一次，这是算法的步骤

（给定N）

找到一个略大于N的P素数

在1到P-1之间选择一个任意数字k

查找t是P的原始根

（对于给定的x，输出洗牌h（x）是）

计算

f(x) = (t ^ x) % P

计算

g(x) = (f(x) + k) % (P-1)

计算

h(x) = g(x)                                       if g(x)<=N-1,
       iterate the calculations with x = g(x)     otherwise