# Analytically finding magic constant in reversible hash function

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.

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