c++ - 如果x * c1 = c2，如何找到乘数x，但x * c1会导致溢出

Question

我正在编写一个代码，它将找到冲突std::hash<std::string>并尝试反转一些哈希计算步骤。

在实现中有这样的乘法std::hash。

size_t hash2 = shift_mix(hash1) * mul;

我知道hash2- 从上一步开始，我也知道mul- 它是常数值 = 0xc6a4a7935bd1e995UL。

shift_mix(hash1) * mul导致溢出（hash2 / mul = 0），所以它只需要最后 64 位的乘法结果。

所以，我需要一种方法来找到shift_mix(hash1)满足相等性的许多变体。最好的方法是什么？可能以某种方式使用__int128_t？

Answer 1

乘以奇数模 2 的幂是可逆的，因此您可以完美地“撤消”它，而不会出现多个选项。但是，换行后除法不起作用，您需要乘以mulmod 2 ⁶⁴的乘法逆元，在这种情况下为 0x5f7a0ea7e59b19bd。0x5f7a0ea7e59b19bd * 0xc6a4a7935bd1e995 = 1.

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