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

Question

总结:有办法做到这一点吗？这就是我的意思:假设我有一个无符号的int数.然后我将它乘以几次(并且有溢出,这是预期的).那么有可能"恢复"原来的价值吗？

---

详情如下:

这都是关于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)

其中bp ^ 2模2 ^ 32的模乘法逆b * p^2 = 1 (mod 2^32).计算完毕后G,只需除以p^2查找即可ab.

我希望我没有犯任何错误......

Answer 2

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

\n\n\n\n

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

\n\n

维基百科上有一篇很好的文章-在和互质的情况下使用欧拉定理的模乘法逆：ma

\n\n

\n\n

其中\xcf\x86(m)是欧拉的 totient 函数。

\n\n

在我的例子中，m(modulo) 是哈希类型的大小 - 2^32、2^64等（在我的例子中是 64 位）。
\n嗯，这意味着，我们应该只找到 的值\xcf\x86(m)。但想一想 -m == 2 ^ 64所以，这给了我们保证，它将与所有奇数m 互质，并且不会与任何偶数互质。所以，我们需要做的就是获取所有值的个数，并将它们除以 2。

\n\n

另外，我们知道它将m是未签名的，否则我们会遇到一些问题。这让我们有机会做到这一点：

\n\n

hash_t x = -1;\nx /= 2;\nhash_t a_reverse = fast_pow( a, x );\n

\n\n

好吧，关于 64 位数字，x确实是一个很大的数字（19 位数字：）9 223 372 036 854 775 807，但是fast_pow速度非常快，我们可以缓存反向数字，以防我们需要多个查询。

\n\n

fast_pow是一个著名的算法：

\n\n

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

\n\n\n\n

加法：例如：

\n\n

    hash_t base = 2305843009213693951;  // 9th mersenne prime\n    hash_t x = 1234567890987654321;\n\n    x *= fast_pow( base, 123456789 );   // x * ( base ^ 123456789 )\n\n    hash_t y = -1;\n    y /= 2;\n    hash_t base_reverse = fast_pow( base, y );\n\n    x *= fast_pow( base_reverse, 123456789 );   // x * ( base_reverse ^ 123456789 )\n    assert( x == 1234567890987654321 ) ;\n

\n\n

工作完美而且速度非常快。

\n