“Undoing” an integer wraparound

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.

-
Something along the line of en.wikipedia.org/wiki/Modular_multiplicative_inverse – rwong Jul 23 '14 at 6:05
@rwong: your comment is the only correct answer. – kevin cline Jul 23 '14 at 6:16
Yup, and Euler's method seems particularly effective since the factorization of m is just 2^32 or 2^64, plus the exponentiation of a modulo m is straightforward (just ignore overflow there) – MSalters Jul 23 '14 at 7:54
I think the particular problem is in fact Rational Reconstruction – MSalters Jul 23 '14 at 7:57
@MSalters: No, that's where you have r*s^-1 mod m and you need to find both r and s. Here, we have r*s mod m and we know everything but r. – user2357112 Jul 23 '14 at 11:17

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.)

-
Oh boy. So all the work that my computer has done building the map was already done by Euclid. – v010dya Jul 23 '14 at 7:53
I like the matter-of-fact-ness in your first sentence. "Oh, it's 1041204193, of course. Don't you have that memorized?" :-P – Doorknob Jul 23 '14 at 8:30
It would be helpful to show an example of this working for a couple numbers, such as one where x*33 didn't overflow and one where it did. – Rob Watts Jul 23 '14 at 15:33
Mind blown. Wow. – Michael Gazonda Jul 23 '14 at 16:47
You don't need either Euclid nor WolframAlpha (certainly!) to find the inverse of 33 modulo $2^{32}$. Since $x=32=2^5$ is nilpotent (of order $7$) modulo $2^32$, you can just apply the geometric series identity $(1+x)^{-1}=1-x+x^2-x^3+\cdots+x^6$ (after which the series breaks off) to find the number $33^{-1}=1-2^5+2^{10}-2^{15}+\cdots+2^{30}$ which is $111110000011111000001111100001_2=1041204193_{10}$. – Marc van Leeuwen Jul 23 '14 at 16:59

This maybe better suited as an question to Math (sic) SE. You are basically dealing with modular arithmetic, since dropping the left-most bits is the same thing.

I am not as good at Maths as the people who are on Math (sic) SE, but i will try to answer.

What we have here is that the number is being multiplied by 33 (3*11), and its only common denominator with your mod is 1. That is because by definition the bits in the computer are powers of two, and thus your mod is some power of two.

You will be able to construct the table where for every previous value you calculate the following value. And the question becomes do the following numbers correspond to only one previous one.

If it were not 33, but a prime or some power of a prime, i believe that the answer would be yes, but in this case… ask on Math.SE!

Programmatic test

This is in C++ because i don't know C#, but the concept still holds. This seems to show that you can:

#include <iostream>
#include <map>

int main(void)
{
unsigned short count = 0;
unsigned short x = 0;
std::map<unsigned short, unsigned short> nextprev;

nextprev[0] = 0;
while(++x) nextprev[x] = 0;

unsigned short nextX;
while(++x)
{
nextX = x*33;
if(nextprev[nextX])
{
std::cout << nextprev[nextX] << "*33==" << nextX << " && " << x << "*33==" << nextX << std::endl;
++count;
}
else
{
nextprev[nextX] = x;
//std::cout << x << "*33==" << nextX << std::endl;
}
}

std::cout << count << " collisions found" << std::endl;

return 0;
}


After populating such a map, you would be always able to get the previous X if you know the next one. There is only a single value at all times.

-
Why would working with a non-negative datatype be easier? Aren't signed and unsigned handled the same way in the computer, only their human output format differs? – Xcelled194 Jul 23 '14 at 5:10
@Xcelled194 Well, it's easier for me to think about these numbers. – v010dya Jul 23 '14 at 5:15
Fair enough xD The human factor~ – Xcelled194 Jul 23 '14 at 5:16
I have removed that statement about non-negative to make it more obvious. – v010dya Jul 23 '14 at 5:17
@Xcelled194: Unsigned datatypes follow the usual rules of modular arithmetic; signed types do not. In particular, maxval+1 is 0 only for unsigned types. – MSalters Jul 23 '14 at 7:45

One way to get it is to use brute force. Sorry I don't know C# but the following is c-like pseudo code to illustrate the solution:

for (x=0; x<=INT_MAX; x++) {
if (x*33 == test_value) {
printf("%d\n", x);
}
}


Technically, what you need is x*33%(INT_MAX+1) == test_value but integer overflow will automatically do the % operation for you unless your language uses arbitrary precision integers (bigint).

What this gives you is a series of numbers that may have been the original number. The first number printed would be the number that would generate one round of overflow. The second number would be the number that would generate two rounds of overflow. And so on..

So, if you know you data better you can make a better guess. For example, common clock maths (overflow every 12 o'clock) tend to make the first number more likely since most people are interested in things that happened today.

-
C# behaves like C with basic types - ie int is a 4 byte signed integer that wraps, so your answer is still good, though brute forcing wouldn't be the best way to go if you have a lot of inputs! :) – Xcelled194 Jul 23 '14 at 5:07
Yeah, I tried doing it on paper with modulo algebra rules from here: math.stackexchange.com/questions/346271/…. But I got stuck trying to figure it out and ended up with a brute-force solution :) – slebetman Jul 23 '14 at 5:10
Interesting article, though I'll have to study it a bit more in depth for it to click, I think. – Xcelled194 Jul 23 '14 at 5:12
@slebetman Look at my code. It seems that there is only a single answer when it comes to multiplying by 33. – v010dya Jul 23 '14 at 5:19
Correction: C int is not guaranteed to wrap around (see your compiler's docs). It's true for unsigned types though. – Thomas Eding Jul 23 '14 at 5:41

You could the SMT solver Z3 to ask it to give you a satisfying assignment for the formula x * 33 = valueFromFile. It will invert that equation for you and give you all possible values of x. Z3 supports exact bitvector arithmetic including multiplication.

    public static void InvertMultiplication()
{
int multiplicationResult = new Random().Next();
int knownFactor = 33;

using (var context = new Context(new Dictionary<string, string>() { { "MODEL", "true" } }))
{
uint bitvectorSize = 32;
var xExpr = context.MkBVConst("x", bitvectorSize);
var yExpr = context.MkBVConst("y", bitvectorSize);
var mulExpr = context.MkBVMul(xExpr, yExpr);
var eqResultExpr = context.MkEq(mulExpr, context.MkBV(multiplicationResult, bitvectorSize));
var eqXExpr = context.MkEq(xExpr, context.MkBV(knownFactor, bitvectorSize));

var solver = context.MkSimpleSolver();
solver.Assert(eqResultExpr);
solver.Assert(eqXExpr);

var status = solver.Check();
Console.WriteLine(status);
if (status == Status.SATISFIABLE)
{
Console.WriteLine(solver.Model);
Console.WriteLine("{0} * {1} = {2}", solver.Model.Eval(xExpr), solver.Model.Eval(yExpr), solver.Model.Eval(mulExpr));
}
}
}


Output looks like this:

SATISFIABLE
(define-fun y () (_ BitVec 32)
#xa33fec22)
(define-fun x () (_ BitVec 32)
#x00000021)
33 * 2738875426 = 188575842

-

To undo that result will give you a non-zero finite amount of numbers (normally infinite, but int is a finite subset of ℤ). If this is this acceptable, just generate the numbers (see other answers).

Otherwise you need to maintain a list of history (of finite or infinite length) of the variable's history.

-

As always, there is a solution from a scientist and solution from an engineer.

Above you will find a very good solution from a scientist, which works always, but requires you to calculate “multiplicative inverse”.

Here is a quick solution from engineer, which will not force you to try all possible integers.

val multiplier = 33 //used with 0x23456789
val problemAsLong = (-1947051863).toLong & 0xFFFFFFFFL

val overflowBit = 0x100000000L
for(test <- 0 until multiplier) {
if((problemAsLong + overflowBit * test) % multiplier == 0) {
val originalLong = (problemAsLong + overflowBit * test) / multiplier
val original = originalLong.toInt
println(s"$original (test =$test)")
}
}


What are the ideas?

1. We got overflow, so let’s use larger types to recover (Int -> Long)
2. We probably lost some bits due to overflow, let’s recover them
3. The overflow was not more than Int.MaxValue * multiplier

Full executable code is located on http://ideone.com/zVMbGV

Details:

• val problemAsLong = (-1947051863).toLong & 0xFFFFFFFFL
Here we convert our stored number to Long, but since Int and Long are signed, we have to do it correctly.
So we limit the number using bitwise AND with bits of Int.
• val overflowBit = 0x100000000L
This bit or multiplication of it could be lost by initial multiplication.
It's a first bit outside of Int range.
• for(test <- 0 until multiplier)
According to 3rd Idea the maximal overflow is limited by multiplier, so don’t try more than we really need.
• if((problemAsLong + overflowBit * test) % multiplier == 0)
Check if by adding possibly lost overflow we come to a solution
• val original = originalLong.toInt
Original problem was in Int range, so let’s return to it. Otherwise we could incorrectly recover numbers, which were negative.
• println(s"$original (test =$test)")
Don’t break after the first solution, because there are could be other possible solutions.

PS: 3rd Idea is not strictly correct, but left so to be understandable.
Int.MaxValue is 0x7FFFFFFF, but maximal overflow is 0xFFFFFFFF * multiplier.
So the correct text would be “The overflow was not more than -1 * multiplier”.
This is correct, but not everybody will understand it.

-