Find Divisor and Dividend from Remainder

Question

I am developing some software to "Mutate" inline constants in source code to make them hard to read (eg. Obfuscation) and need a way to determine two values that when divided by each other gets a predetermined remainder.

I have read up on the Remainder theorem but am finding it difficult to wrap my head around exactly what I need to implement/determine.

Basically I need a way to do the following:

Original:

x = 12

Mutated:

x = 1561312 % 13

Of course the dividend and the divisor will be much larger (I'm thinking of values like 1825141394). I considered brute forcing, but I thought I might ask around math exchange if you knew a formula or algorithm that would do what I wanted :)

André Nicolas · Accepted Answer · 2013-09-07T06:36:43.603

3

Work backwards. Given your remainder $r$ ($12$ in the example), make a "random" choice of $q$ and $m$, with $m\gt r$, and calculate $x=qm +r$. Then use $x\,\%\, m$.

edited Sep 07 '13 at 06:36

answered Sep 07 '13 at 06:18

André Nicolas

507,029

Does $x$ have to be positive? – jduncanator Sep 07 '13 at 06:39
You can use negative $q$ if you want, giving negative $x$. – André Nicolas Sep 07 '13 at 06:42
Thanks heaps! Works now! Was getting some weird negatives but that was due to some integer overflows (int.MaxValue * int.MaxValue is never good ;)). Thanks heaps again! – jduncanator Sep 07 '13 at 06:54
1

You are welcome. I am afraid I can give no programming advice, the last serious programming I did (a long time ago) was in Assembler. – André Nicolas Sep 07 '13 at 07:36

Find Divisor and Dividend from Remainder

1 Answers1