经过几次乘法**有溢出**之后是否有可能得到一个数字的原始值？

Question

摘要：假设我有一个unsigned int 数字。然后我将其相乘几次（并且存在溢出，这是预期的）。那么是否可以“恢复”原始值？

---

详细信息：

这都是关于 < strong>Rabin-Karp 滚动哈希。我需要做的是：我有一个长字符串的哈希值 - 例如：“abcd”。然后我得到了较短子字符串的哈希值 - 例如“cd”。如何使用两个给定的哈希值以 O(1) 计算“ab”哈希值？

我现在的算法是：

• 从“abcd”哈希中减去“cd”哈希（从多项式中删除最后一个元素）
• 将“abcd”哈希除以 p ^ len( "cd" ) ，其中 p 是基数（质数）。

所以这是：

a * p ^ 3 + b * p ^ 2 + c * p ^ 1 + d * p ^ 0 - abcd

c * p ^ 1 + d * p ^ 0 - cd

ab 得到：

( 
  ( a * p ^ 3 + b * p ^ 2 + c * p ^ 1 + d * p ^ 0 ) -
  ( c * p ^ 1 + d * p ^ 0 ) 
)
/ ( p ^ 2 )
= a * p ^ 1 + b * p ^ 0

如果我没有溢出（如果 p是小数字）。但如果不是——它就不起作用。

有什么技巧或者什么吗？

PS c++ 标签是因为数字溢出，因为它是特定的（并且与 python、scheme 或 sth 不同）

Answer 1

不知道溢出部分，但有一种方法可以恢复原始值。

中国剩余定理有很大帮助。让我们调用h = abcd - cd。 G 是值 h，没有溢出，G = h + k*2^32，假设溢出只是 %2^32 。因此ab = G / p^2。

G = h (mod 2^32)
G = 0 (mod p^2)

如果 p^2 和 2^32 互质。 中国余数定理上的这个页面，给了我们

G = h * b * p^2 (mod 2^32 * p^2)

其中 b 是模块化的p^2 模 2^32 的乘法逆元，b * p^2 = 1 (mod 2^32)。计算出 G 后，只需除以 p^2 即可找到 ab。

Answer 2

扩展欧几里得算法是一个很好的解决方案，但它过于复杂且难以实现。还有一个更好的。

---

还有另一种方法可以做到这一点（感谢我的朋友（:）

wikipedia<中有一篇很好的文章/a> - 当 m 和 a 互质时，使用欧拉定理的模乘法逆元：

其中 φ(m) 是 Euler 的 totient 函数。

在我的例子中，m（模）是哈希类型的大小 - 2 ^32、2^64 等（在我的例子中是 64 位）。
嗯，这意味着，我们应该只找到 φ(m) 的值。但想想 - m == 2 ^ 64 所以，这给了我们保证 m 将与所有奇数和 < em>不会与任何偶数互质。因此，我们需要做的是获取所有值的数量并将它们除以 2。

此外，我们知道 m 将是无符号的，否则我们会遇到一些问题。这让我们有机会做到这一点：

hash_t x = -1;
x /= 2;
hash_t a_reverse = fast_pow( a, x );

嗯，对于 64 位数字，x 确实是一个很大的数字（19 位数字：9 223 372 036 854 775 807），但是 < code>fast_pow 确实很快，我们可以缓存相反的数字，以防我们需要多个查询。

fast_pow 是一种著名的算法：

hash_t fast_pow( hash_t source, hash_t pow )
{
    if( 0 == pow )
    {
        return 1;
    }

    if( 0 != pow % 2 )
    {
        return source * fast_pow( source, pow - 1 );
    }
    else
    {
        return fast_pow( source * source, pow / 2  );    
    }

}

---

加法：例如：

    hash_t base = 2305843009213693951;  // 9th mersenne prime
    hash_t x = 1234567890987654321;

    x *= fast_pow( base, 123456789 );   // x * ( base ^ 123456789 )

    hash_t y = -1;
    y /= 2;
    hash_t base_reverse = fast_pow( base, y );

    x *= fast_pow( base_reverse, 123456789 );   // x * ( base_reverse ^ 123456789 )
    assert( x == 1234567890987654321 ) ;

效果完美且速度非常快。

Answer 3

你有一个 * b = c mod 2^32 （或 mod 其他东西，具体取决于你如何进行哈希）。如果你能找到 d 使得 b * d = 1 mod 2^32 （或 mod 其他），那么你可以计算 a * b * d = a
并检索 a.如果 gcd(b, mod 2^32) = 1 那么您可以使用 http://en.wikipedia。 org/wiki/Extended_Euclidean_algorithm 找到 x 和 y，使得 b * x + 2^32 * y = 1，或者
b * x = 1 - y * 2^32，或
b * x = 1 mod 2^32，因此 x 是您要乘以的数字。

Answer 4

您应该使用无符号整数来获得定义的溢出行为（模 2^N）。有符号整数溢出未定义。

另外，您应该乘以 p 的乘法逆元对适当的值取模，而不是除法。例如，如果 p=3 并且您的哈希值是 8 位，则乘以 171，因为 171*3=513=2*256+1。如果 p 和模值互质，则存在乘法逆元。

Answer 5

这里只是一个部分的侧面答案：我相信使用无符号整数并不是严格必要的。您可以使用补语。

但请注意，这将有 -0 和 +0 的单独表示，并且您可能必须在此过程中手动编写算术运算。

某些处理器指令与整数表示无关，但并非全部。

Answer 6

所以溢出其实只是你的编译器对你好而已； C/++ 标准实际上表明溢出是未定义的行为。因此，一旦溢出，您实际上无能为力，因为您的程序不再是确定性的。

您可能需要重新考虑算法，或者添加模运算/减法来修复您的算法。