This post is a pre-requisite for the next thing I want to talk about so may not make a whole lot of sense or be all that interesting until shown in that context.

Say you have a function like this:

If you know the values of a, m and n, how do you solve for x? Note in this post we are only dealing with integers, so we are looking for the integer solution for x.

It might be hard to visualize with so many symbols, so here it is with some constants:

How would you solve that for x? In other words, what do you need to multiply 5 by, so that when you divide the result by 7, that you get 3 as the remainder?

One way to solve for x would be brute force. We could try plugging every value from 0 to 6 into x (every value from 0 to n-1), and see if any gives us the result we are looking for.

Brute force can be a challenge if the numbers are really large, like in some cryptographic situations.

Interestingly, there might not even be a valid answer for x that satisfies the equation! The below has no answer for instance:

Better Than Brute Force

There’s something called the “Modular Multiplicative Inverse” which looks eerily familiar:

Where a and m are known, and the inverse itself is the value of x.

Using the same constants we did above, that gives us this:

In this case, the inverse (x) is 3. You can verify that by seeing that (5*3) % 7 is 1.

Once you have the inverse, if you wanted to solve the original equation where the modulus end up being 3, you just multiply the inverse by the desired modulus amount. Since the inverse is 3 and the desired modulus value is 3, you multiply them together and get 9. Plugging the numbers in, we can see that (5*9) % 7 = 3.

Pretty cool, but how to calculate the inverse? You can calculate it by using something called the “Extended Euclidean Algorithm”.

The regular Euclidean algorithm is in a post here: Programmatically Calculating GCD and LCM.

The extended euclidean algorithm is explained really well on wikipedia: Wikipedia: Extended Euclidean Algorithm.

Sample Code

Here’s some sample code that asks the user for input and solves these style of equations for x. Below the code I’ll show some example runs and talk about a few more things.

#include <stdio.h>
#include <algorithm>
#include <array>

//=================================================================================
unsigned int ExtendedEuclidianAlgorithm (int smaller, int larger, int &s, int &t)
{
    // make sure A <= B before starting
    bool swapped = false;
    if (larger < smaller)
    {
        swapped = true;
        std::swap(smaller, larger);
    }

    // set up our storage for the loop.  We only need the last two values so will
    // just use a 2 entry circular buffer for each data item
    std::array<int, 2> remainders = { larger, smaller };
    std::array<int, 2> ss = { 1, 0 };
    std::array<int, 2> ts = { 0, 1 };
    int indexNeg2 = 0;
    int indexNeg1 = 1;

    // loop
    while (1)
    {
        // calculate our new quotient and remainder
        int newQuotient = remainders[indexNeg2] / remainders[indexNeg1];
        int newRemainder = remainders[indexNeg2] - newQuotient * remainders[indexNeg1];

        // if our remainder is zero we are done.
        if (newRemainder == 0)
        {
            // return our s and t values as well as the quotient as the GCD
            s = ss[indexNeg1];
            t = ts[indexNeg1];
            if (swapped)
                std::swap(s, t);
            return remainders[indexNeg1];
        }

        // calculate this round's s and t
        int newS = ss[indexNeg2] - newQuotient * ss[indexNeg1];
        int newT = ts[indexNeg2] - newQuotient * ts[indexNeg1];

        // store our values for the next iteration
        remainders[indexNeg2] = newRemainder;
        ss[indexNeg2] = newS;
        ts[indexNeg2] = newT;

        // move to the next iteration
        std::swap(indexNeg1, indexNeg2);
    }
}

//=================================================================================
void WaitForEnter ()
{
    printf("nPress Enter to quit");
    fflush(stdin);
    getchar();
}

//=================================================================================
int main(int argc, char **argv)
{
    // get user input
    int a, m, n;
    printf("Given a, m and n, solves for X.n(a * X) %% m = nnn");
    printf("a = ");
    scanf("%i", &a);
    printf("m = ");
    scanf("%i", &m);
    printf("n = ");
    scanf("%i", &n);

    // show details of what they entered
    printf("n(%i * X) mod %i = %in", a, m, n);

    // Attempt brute force
    printf("nBrute Force Testing X from 0 to %i:n", (m-1));
    for (int i = 0; i < m; ++i) {
        if ((a*i) % m == n)
        {
            printf("  X = %in", i);
            printf("  %i mod %i = %in", a*i, m, (a*i) % m);
            break;
        }
        else if (i == (m - 1))
        {
            printf("  No solution!n");
        }
    }

    // Attempt inverse via Extended Euclidean Algorithm
    printf("nExtended Euclidean Algorithm:n");
    int s, t;
    int GCD = ExtendedEuclidianAlgorithm(a, m, s, t);

    // report failure if we couldn't do inverse
    if (GCD != 1)
    {
        printf("  Values are not co-prime, cannot invert! GCD = %in", GCD);
    }
    // Else report details of inverse and show that it worked
    else
    {
        printf("  Inverse = %in", t);
        printf("  X = Inverse * n = %in", t*n);
        printf("  %i mod %i = %in", a*t*n, m, (a*t*n) % m);
    }

    WaitForEnter();
    return 0;
}

Example Runs

Here is a normal run that solves , to come up with a value of 8 for x.

Here is a run that solves . Brute force gives us a value of 2 for x, while the inverse gives us a value of 9. Both are valid, and in fact are equivalent since 9 % 7 = 2. This shows that getting the inverse and then multiplying it to get the desired answer doesn’t always give you the smallest possible value of x.

Here is a large number run that solves . Brute force gives a value of 571,506 for x, while using the inversion method gives us a value of 230,571,736.

Lastly, here is a run that solves . Brute force gives us a value of 2 for x, but interestingly, it isn’t invertible, so the inversion based solution can’t even find us an answer!

This happens when a and m are not co-prime. In other words, if they have a GCD that isn’t 1, they aren’t coprime, and the modulus can’t be inverted.

Links

You can read more about the modular multiplicative inverse here: Wikipedia: Modular Multiplicative Inverse.