以 x,y 坐标为种子的随机数生成器

Question

我正在寻找一种高效、均匀分布的 PRNG，它可以为平面中的任何整数点生成一个随机整数，坐标 x 和 y 作为函数的输入。

int rand(int x, int y)

每次输入相同的坐标时，它必须传递相同的随机数。

您是否知道可用于此类问题以及更高维度的算法？

我已经尝试使用像 LFSR 这样的普通 PRNG，并将 x、y 坐标合并在一起以将其用作种子值。像这样。

int seed = x << 16 | (y & 0xFFFF)

此方法的明显问题是种子没有多次迭代，而是针对每个 x,y 点再次初始化。如果您可视化结果，这会导致非常难看的非随机模式。

我已经知道使用某种大小（如 256）的随机排列表的方法，你可以像这样从中得到一个随机整数。

int r = P[x + P[y & 255] & 255];

但是我不想用这个方法，因为范围非常有限，周期长度受限，内存消耗大。

感谢任何有用的建议！

Answer 1

我的做法

总的来说，我认为您需要一些哈希函数（大多数这些函数都是为了输出随机性而设计的；RNG 的雪崩效应，CryptoPRNG 明确需要的随机性）。与 this 线程进行比较。

以下代码使用了这种方法：

1) 根据您的输入构建可散列的内容
2) 哈希 -> 随机字节（非加密）
3) 以某种方式将这些随机字节转换为您的整数范围（很难做到 correctly/uniformly！）

最后一步是用this的方法完成的，这个方法好像没那么快，但是理论上有很强的保证（用的是选答）。

我使用的散列函数支持种子，将在步骤3中使用！

import xxhash
import math
import numpy as np
import matplotlib.pyplot as plt
import time

def rng(a, b, maxExclN=100):
    # preprocessing
    bytes_needed = int(math.ceil(maxExclN / 256.0))
    smallest_power_larger = 2
    while smallest_power_larger < maxExclN:
        smallest_power_larger *= 2

    counter = 0
    while True:
        random_hash = xxhash.xxh32(str((a, b)).encode('utf-8'), seed=counter).digest()
        random_integer = int.from_bytes(random_hash[:bytes_needed], byteorder='little')
        if random_integer < 0:
            counter += 1
            continue # inefficient but safe; could be improved
        random_integer = random_integer % smallest_power_larger
        if random_integer < maxExclN:
            return random_integer
        else:
            counter += 1

test_a = rng(3, 6)
test_b = rng(3, 9)
test_c = rng(3, 6)
print(test_a, test_b, test_c) # OUTPUT: 90 22 90

random_as = np.random.randint(100, size=1000000)
random_bs = np.random.randint(100, size=1000000)

start = time.time()
rands = [rng(*x) for x in zip(random_as, random_bs)]
end = time.time()

plt.hist(rands, bins=100)
plt.show()
print('needed secs: ', end-start)
# OUTPUT: needed secs:  15.056888341903687 -> 0,015056 per sample
# -> possibly heavy-dependence on range of output

可能的改进

从某些来源添加额外的熵（随机数；可以放入 str）
制作一个class并初始化以记住预处理（如果对每个采样都进行，则成本很高）
处理负整数；也许只使用 abs(x)

假设：

输出范围是 [0, N) -> 只是为其他人移动！
输出范围小于（位）哈希输出（可以使用 xxh64）

评价：

勾选randomness/uniformity

检查输入是否确定

Answer 2

您可以使用各种 randomness extractors 来实现您的目标。您至少可以从两个来源寻找解决方案。

总而言之，你可以优先使用：

AES-CBC-MAC 使用随机密钥（可以修复并重复使用）
HMAC，最好使用 SHA2-512
SHA 系列哈希函数（SHA1、SHA256 等）；使用一个随机的最终块（例如在最后使用一个大的随机盐）

因此，您可以连接您的坐标、获取它们的字节、添加随机密钥（用于 AES 和 HMAC）或用于 SHA 的盐，并且您的输出具有足够的熵。根据 NIST，输出熵依赖于输入熵：

假设您使用 SHA1；因此 n = 160 位 。假设 m = input_entropy（您的坐标的熵）

if m >= 2n 那么 output_entropy=n=160 位
if 2n < m <= n then maximum output_entropy=m（但不能保证完全熵）。
if m < n then maximum output_entropy=m （这是你的情况）

参见 NIST sp800-90c（第 11 页）

Answer 3

我找到了一个基于xxhash算法的非常简单、快速、足够的哈希函数。

// cash stands for chaos hash :D
int cash(int x, int y){   
    int h = seed + x*374761393 + y*668265263; //all constants are prime
    h = (h^(h >> 13))*1274126177;
    return h^(h >> 16);
}

它现在比我上面描述的查找 table 方法快得多，而且看起来同样随机。我不知道与 xxhash 相比，随机属性是否好，但只要它看起来随机，就我的目的而言，它是一个公平的解决方案。

这是像素坐标作为输入的样子：

以 x,y 坐标为种子的随机数生成器

random number generator with x,y coordinates as seed

random

algorithm

hash

dimension

我的做法

可能的改进

假设：

评价：

勾选randomness/uniformity

检查输入是否确定