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:
- Recover X itself or
- 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.
m
is just 2^32 or 2^64, plus the exponentiation ofa
modulom
is straightforward (just ignore overflow there)r*s^-1 mod m
and you need to find bothr
ands
. Here, we haver*s mod m
and we know everything butr
.