How to find multiplier x if x * c1 = c2, but x * c1 causes overflow

Question

I am writing a code that will find collisions for std::hash<std::string> and trying to reverse some of hash calculation steps.

There is such a multiplication in std::hash implementation.

size_t hash2 = shift_mix(hash1) * mul;

I know hash2 - from previous step, also I know mul - it's constant value = 0xc6a4a7935bd1e995UL.

shift_mix(hash1) * mul causes overflow (hash2 / mul = 0), so it takes only last 64 bits of multiplication result.

So, I need a way to find many variants of shift_mix(hash1) which satisfy equality. What is the best way to do it? Probably somehow use __int128_t?

Answer 1

Multiplication by an odd number modulo a power of two is invertible, so you can "undo" it perfectly, without multiple options appearing. However, division does not work after wrapping, you need to multiply by the multiplicative inverse of mul mod 2⁶⁴, which is 0x5f7a0ea7e59b19bd in this case. 0x5f7a0ea7e59b19bd * 0xc6a4a7935bd1e995 = 1.

uint64_t mul_inv = 0x5f7a0ea7e59b19bd;
uint64_t hash1 = unshift_mix(hash2 * mul_inv);