如何制作一次接受一个值的置换函数? [英] How do I make a permutation function that accepts one value at a time?

问题描述

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

I am looking for a function that accepts 1 number from an interval 0,1....N and returns a permuted value from the same interval.

0、1、2、3、4、5和f(x)的示例为:

An example for 0, 1, 2, 3, 4, 5 and f(x) would be:

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啪声.我希望结果是随机的.

From what I researched/understood this is a cyclic group where f(x) is what its all based upon. If have found the function f(x) = 911 * x % N to be an example of what I want, however, patterns come up when using this. 911 is a large prime number and by changing that, I get another permutations but still, patters arise. My wish is for the results to be random-ish.

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

I know I can pregenerate the permutation using something like [ 0, 1, 2...N ].shuffle() or something but in my case I cannot do such a thing.

我有一项服务，该服务接受输入数字值并返回排列后的值/位置. N是在服务器端设置的，所以我要查找的功能也是这样.

I have a service which takes for input a numeric value and returns the permuted value/position. N is set serverside, so is the function I am looking for.

推荐答案

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

Please keep in mind, that the algorithm I describe here is based on the list [1, 2, ... N-1] (with length N-1). If you insist using the list [0, 1, ..., N] (with length N+1), please apply the needed minor modifications. Moreover, for brevity, I am using the % operand in a slightly different manner than most programming languages do: a % b takes values between 1 and b, not between 0 and b - 1, but of course the main idea behind is not changed, so the value of a % b is the integer between 1 and b, which is congruent with a, modulo b.

如果您通读此书，对于您来说显而易见的是，产生的随机播放根本不是随机的.但是，如果选择了正确的参数，则模式将不容易识别(我的模块化幂运算的基本思想来自密码学，在密码学中，不可识别的模式和不可恢复的功能非常重要).

If you read this through, it will be obvious for you, that the shuffle generated is not random at all. However, with well chosen parameters, the pattern won't be easy to recognize, (my basic idea of modular exponentiation comes from cryptography, where it is important to have non-recognizable patterns and non-revertable functions).

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

And this is much more the language-agnostic description of the algorithm, than an actual programming solution. I do not go into details of effective implementations and pitfalls you may come across. I hope it still helps. I also coded some parts of this in python, so I can give further help and even share my code if it is needed, but that would need some completing and refactoring before.

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

您的f(x)= t * x％N(您选择t为911的初始试验)显示了一些模式，因为乘法保持线性(在其模数"意义上).

Your initial trial of f(x) = t * x % N (where you chose t to be 911) shows some patterns because multiplication holds linearity (in the 'modular' meaning of it).

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

You can give much more random feel if you use exponentiation instead of multiplication. Something like f(x) = t ^ x % N. However, t has to be chosen wisely (as it was in the multiplication case, to be a coprime to N), and the output given by this formula won't provide distinct numbers for distinct x values only in the case of N is prime.

大学水平的数学即将到来，请多多包涵，我会尽量保持简单.

University level math is coming, bear with me, I will try to keep it simple.

我们将需要使用原始根.相关的 Wikipedia文章可能会有所帮助，但基本思想是，精心挑选的底数取1到N-1之间的所有值.例如

We will need to use primitive roots. The related Wikipedia article may help a lot, but the basic idea is that the remainders of powers of a well chosen base take all the values between 1 and N-1. For example

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)，依此类推).

are all different (from this point, the values are repeating from the beginning: 3^7 = 3^1 (mod 7), 3^8 = 3^2 (mod 7), and so on).

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

So, if your N is 7, then 3 will work fine to be t. You can use f(x) = (3 ^ x) % 7 for x values between 1 and 6.

这将导致以下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，导致排列:

If you are playing with this a little bit, you can notice, that N-1 is always shuffled to 1. If you want to avoid this, we can go a step further, and choose an arbitrary number k to add after the exponentiation. That is, using g(x) = (f(x) + k) % (N-1) = ((t ^ x) % N + k) % (N-1), in our example let k be 2, resulting in the permutation:

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

如何选择基准

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

Now you get the basic feel. But how to use this generally, when N is not 7?

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

The key to the problem is choosing the parameter t, which was 3 in our example.

不幸的是，这通常是一个难题(数学家称之为找到原始的根)，而我所知道的却没有任何易于理解的现成解决方案.

Unfortunately this is generally a hard question (mathematician's call it finding a primitive root), and there isn't any easy-to-interpret, out-of-the-box solution I am aware of.

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

But this is only one part of the problem. Even more sadly, a primitive root won't even work if N is a composite number. For example, if N=6, there isn't any number t for which the expression t^x modulo 6 takes all the values between 1 and 5.

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

But it is not too hard to solve this part.

如何处理复合N

如果N是合成的，我们应该找到一个几乎不大的素数P，并以该素数为基础，通过将出界数替换为它们的洗后值(并进行迭代，如果需要的话.)

If N is composite, we should find a prime P, which is barely larger, and build upon the algorithm based on that one, by replacing out-of-bound numbers with their after-the-shuffle values (and iterate, if needed).

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

For example, if N is 6, we can choose P to be 7 and use our previously constructed 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的解决方案.

Just to be on the safe side, I give an other example with N=4, where we use our previously calculated solution for 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的越界值并不需要太多的重新计算.

This should be clear now. It is wise to choose P close to N, so there aren't too many recalculations needed for out-of-bound values of g.

返回找到t

所以我们剩下的唯一问题是找到可以用作求幂基础的原始根.

So our only problem left is to find the primitive root which can be used as the base of the exponentiation.

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

If the maths on the pages I linked before cause some visceral disgust, I have some good news for you: possible good values of t are dense in the interval [2, N-1], so even random guessing may help.

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

There are some details how to verify effectively if a randomly chosen t is really good for us on the linked pages, but unless you are working with really huge numbers, you can just do the exponentiations and check if the number 1 appears earlier than the (N-1)th power of t (maybe you remember I noted that t^x=1 (mod N) holds always in the case of x=N-1, so an earlier appearance of 1 would break uniqueness).

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

I would recommend to look for a suitable t around N/2 (meaning the order of magnitude - for P=91367, t=54949 works perfectly). If you choose t to be too low (for example t=2), you can easily spot the pattern caused by exponentiation on some neighbouring x values (2+k, 4+k, 8+k, ... will appear next to each other). If t is too close to N, a similar phenomena may appear if you look at f(x) in consecutive x values of the same parity. A good choice of t should cover these patterns, and end with a result randomish enough.

摘要

再一次，这是算法的步骤

So once again, here are the steps of the algorithm

(给定N个)

找到一个比N稍大的P素数

find a P prime slightly larger than N

选择1到P-1之间的任意数字k

choose an arbitrary number k between 1 and P-1

找到t是P的原始根

(对于给定的x，输出随机播放h(x)是)

(for a given x the output shuffle h(x) is)

计算

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

这篇关于如何制作一次接受一个值的置换函数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！