31-битный алгоритм Bijective (Perfect) Hash - PullRequest
Новая
       67

31-битный алгоритм Bijective (Perfect) Hash

1 голос
/ 02 мая 2019

Что мне нужно

Мне нужен алгоритм, который производит биективный вывод.У меня есть 31-битный вход и мне нужен псевдослучайный 31-битный выход.

То, что я рассмотрел

CRC биективны в пределах их битовой ширины.

Я посмотрел в Google и могу найти для этого полиномы, но не таблицы или алгоритм.

Может ли кто-нибудь указать мне правильное направление?

Мне нужен CRC-31 алгоритм с использованием полинома скажем 0x737e312b или любой биективной функции, которая будет делать то, что мне нужно.

NOTE

Я нашел следующий код, но, к сожалению, неесть инструменты для его компиляции и запуска.

1 Ответ

3 голосов
/ 03 мая 2019

Для любой хеш-функции 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;
}

Это структура Фейстеля, которая составляет основу многих шифров: 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

...