2

我正在使用一个简单的散列函数，该函数将取一个以二为底的范围内的整数，并（随机）散列到该范围内的另一个整数而不会发生冲突。这将用于构造排列，最好是从种子值。所以仅仅偏移整数和调制是行不通的。任何人都知道用 C 编写的一个不错的选择吗？

谢谢，乔什

4

2 回答 2

2

我在Andrew Kensler的论文Correlated Multi-Jittered Sampling中找到了一个很好的解决方案。这里使用仅由可逆运算符组成的混合函数构造排列。这保证了在二次幂范围内没有碰撞。

该函数是通过使用爬山程序迭代地找到的，该程序根据其雪崩特性评估每个候选者。此外，Kensler 通过使用称为循环行走的技术对哈希进行概括，以允许不是 2 的幂的范围。

由于这一点，结果的质量以及轻松打乱排列的能力，所提出的函数是对原始问题的一个很好的解决方案。有关可逆运算符和生成质量混合函数的更多详细信息，请参阅 Bret Mulvey 关于散列函数的文章。

于 2017-05-07T21:48:15.643 回答
1

这可能会有所帮助（有关更通用的方法，请参见底部）：乘法循环组允许您选择k“种子”值、n“最大值”值，并以非常有效的方式将自然数从零置换到 n-1 （k 可以在 Z 中，但最好是两个自然数）。如果你想要一个排列，唯一的问题是它n必须是一个素数，我不确定所有排列是否均匀分布在种子空间周围（一些密码学知识在这里会有很大帮助）。

主要操作将是这样的，在伪代码中：

for i in range(0, n){ i:= (i*k)(mod n);}

这里有一个 C 语言的工作玩具程序：

#include <stdio.h>

int main(void)
{
  // take a prime number (from https://primes.utm.edu/lists/2small/0bit.html)
  //int n = (int)pow(2,13)-1;
  // for the sake of test, let's take a little one:
  int n = 23;
  // take a random integer seed:
  int k = 1234;
  printf("permutation of numbers from 0 below %d with seed %d:\n", n, k);
  for (int i=0; i<n; i++){
    printf("%d ", ((i*k)%n));
  }
  printf("\n");
  return 0;
}

返回：

permutation of numbers from 0 below 23 with seed 1234:
0 15 7 22 14 6 21 13 5 20 12 4 19 11 3 18 10 2 17 9 1 16 8

这并不完全是您想要的，但是通过一些调整它可以正常工作......除非我们谈论的是高端安全性东西。可能最直接的解决方案是选择接近 2 次方的素数，并进行一些调整？ https://primes.utm.edu/lists/2small/

让我知道它是否有帮助！

编辑我忍不住在我的 emacs 上直接测试它，所以这里是后代的功能：

(defun permute (n seed)
  "prints a permutation of the set of numbers between 0 and n-1, 
   provided n is prime"
  (let ((permuted (loop for i below n collect (% (* i seed) n))))
    (print permuted)
    ;(print (sort permuted '<)) ; debug print
    ))

(test 23  1234) ; returns (0 15 7 22 14 6 21 13 5 20 12 4 19 11 3 18 10 2 17 9 1 16 8)

编辑 2实际上，正如Bézout's theorem所述 ，这已经足够了，k并且n互为素数。所以从技术上讲，如果你确保的话，你可以有任意的自然值。一种简单但有限的方法是从素数列表中随机选择。一个可能更好的解决方案是计算每个给定的相对素数，然后从那里挑选（声明：8 和 9 都不是素数，但它们互为素数，因为 9(mod 8)= 1）。它并没有比这更“完整”，但我仍然不知道排列是如何用这种方法分布的。nkn

于 2016-09-24T16:15:18.853 回答