gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-03 00:11:33 37 4
gpt4 key购买 nike

我正在寻找一个函数,该函数从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是在服务器端设置的,所以我要查找的功能也是如此。

最佳答案

请记住,我在这里描述的算法基于列表[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

关于math - 如何制作一次接受一个值的置换函数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16416190/

37 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com