Reverse multiplication of 32-bit numbers

Question

I have two large signed 32-bit numbers (java ints) being multiplied together such that they'll overflow. Actually, I have one of the numbers, and the result. Can I determine what the other operand was?

knownResult = unknownOperand * knownOperand;

Why? I have a string and a suffix being hashed with fnv1a. I know the resulting hash and the suffix, I want to see how easy it is to determine the hash of the original string.

This is the core of fnv1a:

hash ^= byte
hash *= PRIME

Answer 1

It depends. If the multiplier is even, at least one bit must inevitably be lost. So I hope that prime isn't 2.

If it's odd, then you can absolutely reverse it, just multiply by the modular multiplicative inverse of the multiplier to undo the multiplication.

There is an algorithm to calculate the modular multiplicative inverse modulo a power of two in Hacker's Delight.

For example, if the multiplier was 3, then you'd multiply by 0xaaaaaaab to undo (because 0xaaaaaaab * 3 = 1). For 0x01000193, the inverse is 0x359c449b.

Answer 2

You want to solve the equation y = prime * x for x, which you do by division in the finite ring modulo 2³²: x = y / prime.

Technically you do that by multiplying y with the multiplicative inverse of the prime modulo 2³², which can be computed by the extended Euclidean algorithm.

Answer 3

Uh, division? Or am I not understanding the question?

Answer 4

It's not the fastest method, but something very easy to memorise is this:

unsigned inv(unsigned x) {
  unsigned xx = x * x;
  while (xx != 1) {
    x *= xx;
    xx *= xx;
  }
  return x;
}

It returns x**(2**n-1) (as in x*(x**2)*(x**4)*(x**8)*..., or x**(1+2+4+8+...)). As the loop exit condition implies, x**(2**n) is 1 when n is big enough, provided x is odd.

So, x**(2**n-1) equals x**(2**n)/x equals 1/x equals the thing you multiply x by to get the value 1 (mod 2**n). Which you then apply:

knownResult = unknownOperand * knownOperand
knownResult * inv(knownOperand) = unknownOperand * knownOperand * inv(knownOperand)
knownResult * inv(knownOperand) = unknownOperand * 1

or simply:

unknownOperand = knownResult * inv(knownOperand);

But there are faster ways, as given in other answers here. This one's just easy to remember.

Also, obligatory SO "use a library function" answer: BN_mod_inverse().