Find a,b,n so that (a^b)%n=x

Question

Say I choose a value for x that can be between 0 and 2147483647. (Int32.MaxValue) I am trying to figure out how I can find values for a,b,n so that (a^b)%n=x I already know that I can use ModPow to verify the values, but I don't know how I can find a fitting a,b and n.

#include <iostream>

/// Calculate (a^b)%n
/// \param a The base
/// \param b The exponent
/// \param n The modulo
/// \return (a^b)%n
int ModPow(int a, int b, int n) {
    long long x = 1, y = a;
    while (b > 0) {
        if (b % 2 == 1) {
            x = (x * y) % n; // multiplying with base
        }
        y = (y * y) % n; // squaring the base
        b /= 2;
    }
    return x % n;
}

int main() {

    int x = 1337;

    // How to find a,b,n so that (a^b)%n=x
    int a = ?;
    int b = ?;
    int n = ?;

    if(x == ModPow(a,b,n))
        printf("ok");

    return 0;
}

Answer 1

int n = 2147483647
int a = ModPow(x, 9241, n);
int b = 464773;

n = 2³¹ − 1 is a prime number. So due to Fermat's little theorem, xⁿ mod n = x and x^{n − 1} mod n = 1 (unless x = 0) so x^{2 n − 1} mod n = x, too. 2 n − 1 = 9241 × 464773. So (x⁹²⁴¹ mod n)⁴⁶⁴⁷⁷³ mod n = x. Note that you need x < n for this to work; x = 2147483647 cannot work if n is a 31 bit (i.e. signed) integer, too.

It took me a while to get here; for a long time I've had this answer messing about with Carmichael numbers and the Carmichael function before I reached this easy solution. See edit history for details.