2
$\begingroup$

The below integer "hash" functions form a pair of reversible hash functions:

uint32_t hash ( uint32_t x ) {

    x = ( ( x >> 16 ) ^ x ) * 0x45d9f3b;
    x = ( ( x >> 16 ) ^ x ) * 0x45d9f3b;
    x = ( ( x >> 16 ) ^ x );

    return x;
}

uint32_t unhash ( uint32_t x ) {

    x = ( ( x >> 16 ) ^ x ) * 0x119de1f3;
    x = ( ( x >> 16 ) ^ x ) * 0x119de1f3;
    x = ( ( x >> 16 ) ^ x );

    return x;
}

The reversibility obviously depends on the "magic values". In the case of uint32_t's, given 0x45d9f3b, the value 0x119de1f3 can be easily found by exhaustive search.

I would like to design a 64-bit equivalent. Exhaustive search is in the 64-bit case no longer an option.

The question is: "Can this 'reversing magical constant' be found analytically?"

PS: I do realise that this is not a hash function in a cryptograhical sense.

$\endgroup$
  • 1
    $\begingroup$ Hint: $\mathrm{0x119de1f3} = \mathrm{0x45d9f3b}^{-1} \pmod {2^{32}}$ $\endgroup$ – gammatester Nov 24 '16 at 7:55
  • $\begingroup$ After understanding the above hint, you might want to head there. $\endgroup$ – fgrieu Nov 24 '16 at 9:10
  • $\begingroup$ @gammatester Thanks for that answer. Cannot accept a comment as "the accepted answer" though... $\endgroup$ – degski Nov 24 '16 at 10:30
  • $\begingroup$ @fgrieu Thanks for that implementation, easy to adapt to the 32-bit case, just for checking... $\endgroup$ – degski Nov 24 '16 at 10:30
  • $\begingroup$ wolframalpha.com/input/?i=PowerMod%5B0x45d9f3b,+-1,+2%5E32%5D $\endgroup$ – CodesInChaos Nov 24 '16 at 12:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.