如何找到x乘数如果xc1=c2，但xc1会导致溢出

Question 1

我写代码，将找到碰撞 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?

Question 2

乘由奇数数量的模力的两个是可逆的，因此可以"撤消"这完全的，没有多选择出现。然而，司不工作之后，包裹，需要乘以乘性逆的 mul 国防部2^64个，这是0x5f7a0ea7e59b19bd在这种情况。 0x5f7a0ea7e59b19bd * 0xc6a4a7935bd1e995 = 1.

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

harold · Answer 1 · 2021-11-23T19:41:58

乘由奇数数量的模力的两个是可逆的，因此可以"撤消"这完全的，没有多选择出现。然而，司不工作之后，包裹，需要乘以乘性逆的 mul 国防部2^64个，这是0x5f7a0ea7e59b19bd在这种情况。 0x5f7a0ea7e59b19bd * 0xc6a4a7935bd1e995 = 1.

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

的问题