Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am primarily a programmer (rather than a mathematician) and have recently come across a coding problem where I must invert a function which is the the modulo of a multiplication (given certain constraints which ensure that there is a 1 to 1 mapping between the inputs and the outputs of the function), and I cannot seem to work out how to do it.

Given the following:

(x * a) % b = c

Where 0 <= x <= b

and 0 <= a <= b

and (in case it matters) where the lowest common multiple of a and b is a * b (is co-prime the correct term for this?).

I want to find the inverse function which will give me x, when I know a, b, and c. More specifically, if b and c are kept constant, and c is varied, I want to work out what x is.

In order to try to work it out myself, I set a = 3 and b = 16. I chose these numbers because the lowest common multiple of 3 and 16 is 3 * 16, which is one of the constraints. I then wrote down a list of all possible values of x (between 0 and 15) and the corresponding values for c, using the equation c = (x * 3) % 16

(0 * 3) % 16 =  0    ( 6 * 3) % 16 =   2    (11 * 3) % 16 =   1
(1 * 3) % 16 =  3    ( 7 * 3) % 16 =   5    (12 * 3) % 16 =   4
(2 * 3) % 16 =  6    ( 8 * 3) % 16 =   8    (13 * 3) % 16 =   7
(3 * 3) % 16 =  9    ( 9 * 3) % 16 =  11    (14 * 3) % 16 =  10
(4 * 3) % 16 = 12    (10 * 3) % 16 =  14    (15 * 3) % 16 =  13
(5 * 3) % 16 = 15

I have arranged this in columns, such that each time the value of c "wraps around", a new column is started. From this, I can derive an equation based on the column number:

x = (c + ((column_number - 1) * 16)) / 3

E.g.:

x = (12 + (0 * 16)) / 3 = 4
x = ( 2 + (1 * 16)) / 3 = 6
x = (10 + (2 * 16)) / 3 = 14

What I cannot see, is how to derive the correct amount to multiply by 16 in order to generalise the equations so that I can use it for any c in the above table (i.e. how to derive the "column_number").

share|improve this question
    
If $a,b$ are coprime, then there are integers $u,v$ such that $au+bv=1$, which gives $au \mod b = 1$, that is, $u$ is the multiplicative inverse of $a$. Then $a (cu) \mod b = c$. In the above, for $a=3$, $b=16$ you have $u=11$, so the formula is $x=(11 c \mod 16)$. –  copper.hat Feb 21 at 7:22
add comment

1 Answer

up vote 4 down vote accepted

Look up the Euclidean algorithm, which you can write into your code. Since $a$ and $b$ are coprime, the Euclidean algorithm lets you find $s$ and $t$ such that $$a\cdot s+t\cdot b=1$$ and it does it fairly quickly. This means that $$a\cdot s\equiv1\mod{b}$$ So then you can multiply the sides of your original equation ($x\cdot a\equiv c\mod{b}$) by the $s$ that is output from the Euclidean algorithm, and: $$\begin{align} x\cdot a\cdot s&\equiv c\cdot s\mod{b}\\ x\cdot 1&\equiv c\cdot s\mod{b}\\ x&\equiv c\cdot s\mod{b} \end{align}$$ and you can reduce $c\cdot s$ down so that you get something in between $0$ and $b$.

There is no significantly quicker algorithm to do this for general $a$, $b$, and $c$ than what is outlined here. That is, there is no closed form formula for $x$ in terms of $a$, $b$ and $c$ that could be programmed to be computed quicker.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.