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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.