Inverse of A*X MOD (2^N)-1

Question

Given a function y = f(A,X):

unsigned long F(unsigned long A, unsigned long x) {
    return  ((unsigned long long)A*X)%4294967295;
}

How would I find the inverse function x = g(A,y) such that x = g(A, f(A,x)) for all values of 'x'?

If f() isn't invertible for all values of 'x', what's the closest to an inverse?

(F is an obsolete PRNG, and I'm trying to understand how one inverts such a function).

• Updated
  If A is relatively prime to (2^N)-1, then g(A,Y) is just f(A-1, y).
  If A isn't relatively prime, then the range of y is constrained... Does g( ) still exist if restricted to that range?

Answer 1

You need to compute the inverse of A mod ((2^N) - 1), but you might not always have an inverse given your modulus. See this on Wolfram Alpha.

Note that

A = 12343 has an inverse (A^-1 = 876879007 mod 4294967295)

but 12345 does not have an inverse.

Thus, if A is relatively prime with (2^n)-1, then you can easily create an inverse function using the Extended Euclidean Algorithm where

g(A,y) = F(A^-1, y),

otherwise you're out of luck.

UPDATE: In response to your updated question, you still can't get a unique inverse in the restricted range. Even if you use CookieOfFortune's brute force solution, you'll have problems like

G(12345, F(12345, 4294967294)) == 286331152 != 4294967294.

Answer 2

You need the Extended Euclidean algorithm. This gives you R and S such that

gcd(A,2^N-1) = R * A + S * (2^N-1).

If the gcd is 1 then R is the multiplicative inverse of A. Then the inverse function is

g(A,y) = R*y mod (2^N-1).

Ok, here is an update for the case where the G = Gcd(A, 2^N-1) is not 1. In that case

R*y mod (2^N-1) = R*A*x mod (2^N-1) = G*x mod (2^N-1).

If y was computed by the function f then y is divisible by G. Hence we can divide the equation above by G and get an equation modulo (2^N-1)/G. Thus the set of solutions is

  x = R*y/G + k*(2^N-1)/G, where k is an arbitrary integer.

Answer 3

The solution is given here (http://en.wikipedia.org/wiki/Linear_congruence_theorem), and includes a demonstration of how the extended Euclidean algorithm is used to find the solutions.

The modulus function in general does not have an inverse function, but you can sometimes find a set of x's that map to the given y.

Answer 4

Accipitridae, Glenn, and Jeff Moser have the answer between them, but it's worth explaining a little more why not every number has an inverse under mod 4294967295. The reason is that 4294967295 is not a prime number; it is the product of five factors: 3 x 5 x 17 x 257 x 65537. A number x has a mutiplicative inverse under mod m if and only if x and m are coprime, so any number that is a multiple of those factors cannot have an inverse in your function.

This is why the modulus chosen for such PRNGs is usually prime.

Answer 5

Eh... here's one that will work:

unsigned long G(unsigned long A, unsigned long y)
{
    for(unsigned int i = 0; i < 4294967295; i++)
    {
        if(y == F(A, i)) return i);
    }
}