Finding the minimum value to satisfy a modulus

Question

The problem I have is x = (16807 x k) % 65536

ie 16807k ≡ x (mod 65536)

I need to calculate k knowing x. My best effort so far is something of a brute force. Is there a mathematical way to calculate k? If not any optimisations on my current code would be appreciated.

t = x;
while ( t += 15115 ) // 16807k = 65536n + x - this is the n
{
    if (t%16807 == 0)
    return t/16807;
}
return x;

EDIT: Changed += to 15115

Answer 1

An odd numbers has a multiplicative inverse modulo a power of two.

The inverse of 16807 mod 2¹⁶ is 22039.

That means that (16807 * 22039) % 65536 == 1, and consequently, that

(16807 * 22039 * x) % 65536 == x

And

k = (22039 * x) % 65536

So you don't have to try anything, you can simply calculate k directly.

Answer 2

You solve this kind of problems using the extended euclidean algorithm for the GCD of 16807 and 65536

The remainder sequence is initiated with

R0=65536
R1=16807

and the computation of the inverse with

V0=0  (V0*16807 == R0 mod 65536)
V1=1  (V1*16807 == R1 mod 65536)

Then using integer long division,

Q1=R0/R1=3,
R2=R0-Q1*R1=15115
V2=V0-Q*V1=-3 (V2*16807 == R2 mod 65536)

Q2=R1/R2=1,  
R3=R1-Q2*R2=1692
V3=V1-Q2*V2=4

Q3=8,  R4=1579,  V4=-35
Q4=1,  R5=113,   V5=39
Q5=13, R6=110,   V6=-542
Q6=1,  R7=3,     V7=581
Q7=36, R8=2,     V8=-21458
Q8=1,  R9=1,     V9=22039

so that 22039 is found as the modular inverse of 15115 modulo 65536.

Answer 3

If you have to look up k repeatedly for different x, you can build a table of solutions before you start decoding:

uint16_t g = 16807u;
uint16_t *mods = malloc(0x10000 * sizeof(*mods));
int i;

for (i = 0; i < 0x10000; i++) {
    uint16_t x = g * i;    // x is effectively x mod 2**16

    mods[x] = i;
};

The solution to yor equation in the 16-bit-range is then:

uint16_t k = mods[x];

It is assumed that x is a 16-bit unsigned integer. Don't forget to free(mods) after you're done.

Answer 4

If k is a solution, then k+65536 is also a solution.

The straightforward brute-force method to find the first k (k>= 0) would be:

for (k=0; k < 65536; k++) {
    if ( (k*16807) % 65536 == x ) {
        // Found it!
        break;
    }
}
if (k=65536) {
    // No solution found
}
return k;