Reversing multiplication operation that has overflowed

Question

Given the code:

uint Function(uint value)
{
  return value * 0x123456D;
}

Inputting the value 0x300 yields the result 0x69D04700. This is only the lower 32 bits of the result. Given the result 0x69D04700 and the factor 0x123456D, is it possible to retrieve all numbers such that (value * 0x123456D) & 0xFFFFFFFF = 0x69D04700 in a fast way?

Edit: The code I show is pseudocode - I can't widen the return type.

Answer 1

What you need is modular division, which can be computed with a version of Euclid's algorithm. In this case the result is 768.

This is very fast -- time (log n)² even for a naive implementation. (If you needed to work with large numbers I could give references to better algorithms.)

See extended Euclidean algorithm for a sketch of how to implement this.