hash - 32 位数字的逆乘法

Question

我有两个大的有符号 32 位数字(java int)相乘，这样它们就会溢出。事实上，我有一个数字和结果。我可以确定另一个操作数是什么吗？

knownResult =unknownOperand *knownOperand;

为什么？我有一个字符串和一个后缀，用 fnv1a 进行哈希处理。我知道生成的哈希值和后缀，我想看看确定原始字符串的哈希值有多么容易。

这是fnv1a的核心:

hash ^= byte
hash *= PRIME

Answer 1

这要看情况。如果乘数是偶数，则至少不可避免地会丢失一位。所以我希望素数不是 2。

如果它是奇数，那么你完全可以反转它，只需乘以 modular multiplicative inverse乘数来撤消乘法。

Hacker's Delight 中有一种算法可以计算模乘逆模 2 的幂。

例如，如果乘数为 3，则您需要乘以 0xaaaaaaab 来撤消(因为 0xaaaaaaab * 3 = 1) 。对于0x01000193，其逆是0x359c449b。