Is it possible to get the original value of a number, after several multiplications **with overflow**?

Summary: Is there a way to do that? Here's what I mean: suppose I have an unsigned int number. Then I multiply it several times(and there's overflow, which is expected). Then is it possible to "revert" the original value back?

In details:

It's all about Rabin-Karp rolling hash. What I need to do is: I have the hash of a long string - for example: "abcd". Then I have the hash for a shorter substring - for example "cd". How to calculate the "ab" hash with O(1), using the two given hashes?

What I have now as an algorithm:

• substract the "cd" hash from "abcd" hash (remove the last elements from the polynomial)
• devide the "abcd" hash by p ^ len( "cd" ), where p is the base (prime number).

So this is:

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

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

ab gets:

( 
  ( 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

And this works, if I don't have an overflow (if p is small number). But if it's not - it's not working.

Is there any trick or something?

P.S. The c++ tag is because of the number's overflow, as it is specific (and different from python, scheme or sth)