Inverted multiplication operation that is full

Question

Based on the code:

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

Entering the value 0x300 gives the result 0x69D04700. These are only the lower 32 bits of the result. Given the result of 0x69D04700 and the coefficient of 0x123456D, is it possible to quickly get all numbers, such as (value * 0x123456D) and 0xFFFFFFFF = 0x69D04700?

Edit: the code I'm showing is pseudo code - I cannot extend the return type.

Answer 1

You need modular division, which can be calculated using the Euclidean algorithm. In this case, the result is 768.

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

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

Answer 2

Well, you can build long values ​​with a low half equal to your result, and the upper half = 1,2,3,4,5 ..., divide by your fixed factor and see if you get the result with no remainder. Perhaps this could be accelerated a bit by understanding the patterns of numbers so that you can even throw away values ​​or some of them.

But I think that there is no significantly less comprehensive approach (and there is a vague suspicion that the fact that this is difficult to do is connected with some encryption methods).

Well...

Take it all

 import java.io.*; public class multiply { public static void main(String[] argv) { long multiplier = 0x123456DL; // long result = 0x69D04700L; long result = (multiplier * 300L) & 0xFFFFFFFFL; System.out.println("New result = " + Long.toHexString(result)); long offset = (multiplier * 300L) >> 32; System.out.println("New offset = " + offset); for (int i = 0; i < 30; i++) { long test = result + (((i * multiplier) + offset) << 32); long quotient = test / multiplier; long remainder = test % multiplier; System.out.println("Test: " + Long.toHexString(test) + " quotient: " + Long.toHexString(quotient) + " remainder: " + Long.toHexString(remainder)); } } } 

Results (fixed):

 C:\JavaTools>java multiply New result = 55555bbc New offset = 1 Test: 155555bbc quotient: 12c remainder: 0 Test: 123456e55555bbc quotient: 10000012c remainder: 0 Test: 2468adb55555bbc quotient: 20000012c remainder: 0 Test: 369d04855555bbc quotient: 30000012c remainder: 0 Test: 48d15b555555bbc quotient: 40000012c remainder: 0 Test: 5b05b2255555bbc quotient: 50000012c remainder: 0 Test: 6d3a08f55555bbc quotient: 60000012c remainder: 0 Test: 7f6e5fc55555bbc quotient: 70000012c remainder: 0 Test: 91a2b6955555bbc quotient: 80000012c remainder: 0 Test: a3d70d655555bbc quotient: 90000012c remainder: 0 Test: b60b64355555bbc quotient: a0000012c remainder: 0 Test: c83fbb055555bbc quotient: b0000012c remainder: 0 Test: da7411d55555bbc quotient: c0000012c remainder: 0 Test: eca868a55555bbc quotient: d0000012c remainder: 0 Test: fedcbf755555bbc quotient: e0000012c remainder: 0 Test: 1111116455555bbc quotient: f0000012c remainder: 0 Test: 123456d155555bbc quotient: 100000012c remainder: 0 Test: 13579c3e55555bbc quotient: 110000012c remainder: 0 Test: 147ae1ab55555bbc quotient: 120000012c remainder: 0 Test: 159e271855555bbc quotient: 130000012c remainder: 0 Test: 16c16c8555555bbc quotient: 140000012c remainder: 0 Test: 17e4b1f255555bbc quotient: 150000012c remainder: 0 Test: 1907f75f55555bbc quotient: 160000012c remainder: 0 Test: 1a2b3ccc55555bbc quotient: 170000012c remainder: 0 Test: 1b4e823955555bbc quotient: 180000012c remainder: 0 Test: 1c71c7a655555bbc quotient: 190000012c remainder: 0 Test: 1d950d1355555bbc quotient: 1a0000012c remainder: 0 Test: 1eb8528055555bbc quotient: 1b0000012c remainder: 0 Test: 1fdb97ed55555bbc quotient: 1c0000012c remainder: 0 Test: 20fedd5a55555bbc quotient: 1d0000012c remainder: 0 

OK, I see that relationships (other than the first) are> 32 bits.

Answer 3

If you take 0x100000000 and divide it by 0x123456D, you will get 224.9999 (decimal). This tells you that approximately every 225 numbers you get to the rest. Of course, since it's not quite 225, you don't end up with integers in the remainder. As @Jacob noted, in a 32-bit world you will only get one value (768 or 0x300). Therefore, for this particular test, the answer is 2 ^ 32 * X + 768, for all integers X> = 0.

Answer 4

Yes it is possible.

Use the Chinese break theorem .

Do you know that

 n = 0 (mod 0x123456D) 

and

 n = 0x69D04700 (mod 0x100000000) 

They are mutually simple, since 0x123456D is odd, and "0x100000000" is the power of two. So the Chinese remainder theorem applies, and it gives you

 n = 0x369D04700 (mod 0x123456D00000000) 

This suggests that the results without truncation are 0x369D04700 + k * 0x123456D00000000 . Dividing this by 0x123456D you 0x300 + k * 0x100000000 .

Answer 5

Your function:

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

multiplied by uint (which works like integers modulo 2**64 in the so-called unchecked context) an odd number. Such an odd number has a unique inverse modulo 2**64 . In this case, it is 0xE2D68C65u , because as you can check (C # syntax):

 unchecked(0x123456Du * 0xE2D68C65u) == 1u 

This multiplication is associative and commutative. So your "reverse" method:

 uint UndoFunction(uint value) { return value * 0xE2D68C65u; } 

Intended Context

( unckecked ).

For any input x both UndoFunction(Function(x)) and Function(UndoFunction(x)) return the original x .

---

PS! To find the modular inverse of 0xE2D68C65u , I used something other than .NET. Actually GP / PARI, like Charles in his answer. In GP, ​​you can make 1/Mod(19088749, 2^32) or Mod(19088749, 2^32)^-1 . The default is decimal notation.

Answer 6

Not with the specified return type. If you want to be able to process 64 bits, you must specify the return type as ulong (or UInt64). C # uses strict static typing in such cases and will not automatically “increase the conversion” of values ​​if the result cannot be stored in a specific type. Even if it were an upconvert conversion, it would have to be thrown back to provide a legal return type, because in the .NET inheritance hierarchy, UInt64 is not derived from UInt32.