C# – How to Undo an Integer Wraparound

c

I ran into an interesting theoretical problem a number of years ago. I never found a solution, and it continues to haunt me when I sleep.

Suppose you have a (C#) application that holds some number in an int, called x. (The value of x is not fixed). When the program is run, x is multiplied by 33 and then written to a file.

Basic source code looks like this:

int x = getSomeInt();
x = x * 33;
file.WriteLine(x); // Writes x to the file in decimal format

Some years later, you discover that you need the original values of X back. Some calculations are simple: Just divide the number in the file by 33. However, in other cases, X is large enough that the multiplication caused an integer overflow. According to the docs, C# will truncate the high-order bits until the number is less than int.MaxValue. Is it possible, in this case, to either:

  1. Recover X itself or
  2. Recover a list of possible values for X?

It seems to me (though my logic could certainly be flawed) that one or both should be possible, since the simpler case of addition works (Essentially if you add 10 to X and it wraps, you can subtract 10 and wind up with X again) and multiplication is simply repeated addition. Also helping (I believe) is the fact that X is multiplied by the same value in all cases – a constant 33.

This has been dancing around my skull at odd moments for years. It'll occur to me, I'll spend some time trying to think through it, and then I'll forget about it for a few months. I'm tired of chasing this problem! Can anyone offer insight?

(Side note: I really don't know how to tag this one. Suggestions welcome.)

Edit: Let me clarify that if I can get a list of possible values for X, there are other tests I could do to help me narrow it down to the original value.

Best Answer

Multiply by 1041204193.

When the result of a multiplication doesn't fit in an int, you won't get the exact result, but you will get a number equivalent to the exact result modulo 2**32. That means that if the number you multiplied by was coprime to 2**32 (which just means it has to be odd), you can multiply by its multiplicative inverse to get your number back. Wolfram Alpha or the extended Euclidean algorithm can tell us 33's multiplicative inverse modulo 2**32 is 1041204193. So, multiply by 1041204193, and you have the original x back.

If we had, say, 60 instead of 33, we wouldn't be able to recover the original number, but we would be able to narrow it down to a few possibilities. By factoring 60 into 4*15, computing the inverse of 15 mod 2**32, and multiplying by that, we can recover 4 times the original number, leaving only 2 high-order bits of the number to brute-force. Wolfram Alpha gives us 4008636143 for the inverse, which doesn't fit in an int, but that's okay. We just find a number equivalent to 4008636143 mod 2**32, or force it into an int anyway to have the compiler do that for us, and the result will also be an inverse of 15 mod 2**32. (We get -286331153.)

Related Topic