31 位双射（完美）哈希算法

Question

我需要的

我需要一个产生双射输出的算法。我有一个 31 位输入，需要一个伪随机 31 位输出。

我考虑过的

CRC 在其位宽内是双射的。

我查看了 Google 并找到了多项式，但找不到表格或算法。

谁能指出我正确的方向？

我需要一个使用多项式的 CRC-31 算法，比如说 0x737e312b，或者任何可以满足我需要的双射函数。

注意

我找到了以下代码，但遗憾的是我没有编译和运行它的工具。

Answer 1

对于任何哈希函数hash，你可以这样做：

function bijectiveHash31(int val) {
    val &= 0x7FFFFFFF; //make sure it's 31 bits
    for (int i=0; i<5; ++i) {
        // the high bits affect the low bits
        val ^= hash(val>>15) & 32767;
        // rotate bits
        val = ((val&32767)<<16) | ((val>>15)&65535);
    }
    return val;
}

这是一个 Feistel 结构，它构成了许多密码的基础：https://en.wikipedia.org/wiki/Feistel_cipher

如果您需要它的速度快而不需要它非常好，那么这很好用：

function bijectiveHash31(int val) {
    val = ((val*RANDOM_ODD_NUMBER) + RANDOM_NUMBER) & 0x7FFFFFFF;
    val ^= (val>>15);
    val ^= (val>>8);
    return val;
}

在这两种情况下，弄清楚如何撤消每个基本操作并不太困难，这表明整个散列是双射的。如果您需要帮助确定乘法，请参阅 https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

31 位双射（完美）哈希算法

31-bit Bijective (Perfect) Hash algorithm

algorithm

hash

crc

bijection

perfect-hash