有没有好的可逆 1-1 函数可以将一个整数映射到另一个整数？例如，给定范围 0-5，我想找到一个映射：
0->3
1->2
2->4
3->5
4->1
5->0
此外，映射应该看起来是随机的。
问问题
120 次
4 回答
4
您可以按升序填充数组并打乱它。如果不是最有效的内存，这通常会表现得相当好。
您还可以依赖封闭的离散变换，例如乘法。如果你有 2 个数字，P 和 K，那么（我认为）只要 P 和 K 互质，P^n mod K 将产生长度为 (K - 1) 的非重复伪随机序列，范围从 1 到K. 离散数学的这种特殊表现是密码学的前提之一。从序列倒退到指数被称为离散对数问题，这也是传统 RSA 安全的原因。
你要求一个可逆算法。如果您跟踪指数，您可以毫不费力地从 P^n mod K 转到 P^(n-1) mod K。您可以采取一些捷径从幂倒退到在密码学中不起作用的指数，因为算法的某些参数被故意丢弃以使其更难。
也就是说，如果您在处理此问题时碰巧通过解决离散日志问题来破坏 RSA，请务必让我知道。
于 2012-07-18T04:24:50.177 回答
0
您可以使用分组密码生成这样的排列，而不必将整个事物保存在内存中（就像您要对列表进行洗牌一样）。我前段时间写了一篇关于它的博客文章，你可以在这里找到。
于 2012-07-20T03:31:05.490 回答
0
置换多项式怎么样？请参阅本文中的第 3 部分：http ://webstaff.itn.liu.se/~stegu/jgt2012/article.pdf它用于那里的噪音，但它看起来与您想要的完全一样。
它建议构造函数的形式(Ax^2 + Bx) mod M。这些函数中只有一小部分是可逆的/产生排列，但如果它存在的话，应该不难找到实际的逆。
于 2012-07-18T08:21:51.877 回答
0
在范围内的非重复随机搜索算法中讨论了与此类似的内容。我很感兴趣，把一些想法放在http://www.mcdowella.demon.co.uk/PermutationFromHash.html
于 2012-07-18T18:12:45.840 回答