How can you calculate the coefficient if you have a different factor and a product with overflows?

Question

a * x = b 

I have a seemingly rather complicated problem of / imul multiplication: if I have a and I have b, how can I calculate x if all of them are 32-bit words (e.g. 0-1 = FFFFFFFF, FFFFFFFF + 1 = 0)? For instance:

 0xcb9102df * x = 0x4d243a5d 

In this case, x is 0x1908c643. I found a similar question, but the room was different, and I hope that there will be a simpler solution than those that were given.

Answer 1

Numbers have a modular multiplicative inverse modulo degree two if they are odd. Everything else is a bit-shifted odd number (even zero, which can be any, with all bits shifted). So, there are several cases:

Given a * x = b

• tzcnt(a) > tzcnt(b) no solution
• tzcnt(a) <= tzcnt(b) solvable, with solutions 2 ^{tzcnt (a)}

The second case has a special case with 1 solution, for odd a , namely x = inverse(a) * b

In general, x = inverse(a >> tzcnt(a)) * (b >> tzcnt(a)) is a solution because you write a as (a >> tzcnt(a)) * (1 << tzcnt(a)) , therefore we cancel the left factor with its inverse, leave the right factor as part of the result (in any case, you cannot cancel) and then multiply by what remains to bring it to b . Obviously, it works only in the second case. If you want, you can list all the solutions by filling out all the options for the upper bits of tzcnt(a) .

The only thing left is to get the opposite, you probably saw it in another answer, whatever it may be, but for completeness you can calculate it as follows: (not verified)

 ; input x dword y = (x * x) + x - 1; dword t = y * x; y *= 2 - t; t = y * x; y *= 2 - t; t = y * x; y *= 2 - t; ; result y