How to find reverse of pow(a,b,c) in python?

Question

pow(a,b,c) operator in python returns (a**b)%c . If I have values of b, c, and the result of this operation (res=pow(a,b,c)), how can I find the value of a?

Solution 1

Despite the statements in the comments this is not the discrete logarithm problem. This more closely resembles the RSA problem in which c is the product of two large primes, b is the encrypt exponent, and a is the unknown plaintext. I always like to make x the unknown variable you want to solve for, so you have y= x^b mod c where y, b, and c are known, you want to solve for x. Solving it involves the same basic number theory as in RSA, namely you must compute z=b^-1 mod λ(c), and then you can solve for x via x = y^z mod c. λ is Carmichael's lambda function, but you can also use Euler's phi (totient) function instead. We have reduced the original problem to computing an inverse mod λ(c). This is easy to do if c is easy to factor or we already know the factorization of c, and hard otherwise. If c is small then brute-force is an acceptable technique and you can ignore all the complicated math.

Here is some code showing these steps:

import functools
import math


def egcd(a, b):
    """Extended gcd of a and b. Returns (d, x, y) such that
    d = a*x + b*y where d is the greatest common divisor of a and b."""
    x0, x1, y0, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def inverse(a, n):
    """Returns the inverse x of a mod n, i.e. x*a = 1 mod n. Raises a
    ZeroDivisionError if gcd(a,n) != 1."""
    d, a_inv, n_inv = egcd(a, n)
    if d != 1:
        raise ZeroDivisionError('{} is not coprime to {}'.format(a, n))
    else:
        return a_inv % n


def lcm(*x):
    """
    Returns the least common multiple of its arguments. At least two arguments must be
    supplied.
    :param x:
    :return:
    """
    if not x or len(x) < 2:
        raise ValueError("at least two arguments must be supplied to lcm")
    lcm_of_2 = lambda x, y: (x * y) // math.gcd(x, y)
    return functools.reduce(lcm_of_2, x)


def carmichael_pp(p, e):
    phi = pow(p, e - 1) * (p - 1)
    if (p % 2 == 1) or (e >= 2):
        return phi
    else:
        return phi // 2


def carmichael_lambda(pp):
    """
    pp is a sequence representing the unique prime-power factorization of the
    integer whose Carmichael function is to be computed.
    :param pp: the prime-power factorization, a sequence of pairs (p,e) where p is prime and e>=1.
    :return: Carmichael's function result
    """
    return lcm(*[carmichael_pp(p, e) for p, e in pp])

a = 182989423414314437
b = 112388918933488834121
c = 128391911110189182102909037 * 256
y = pow(a, b, c)
lam = carmichael_lambda([(2,8), (128391911110189182102909037, 1)])
z = inverse(b, lam)
x = pow(y, z, c)
print(x)

Solution 2

The best you can do is something like this:

a = 12
b = 5
c = 125

def is_int(a):
    return a - int(a) <= 1e-5

# ============= Without C ========== #
print("Process without c")
rslt = pow(a, b)

print("a**b:", rslt)

print("a:", pow(rslt, (1.0 / b)))

# ============= With C ========== #
print("\nProcess with c")
rslt = pow(a, b, c)

i = 0
while True:

    a = pow(rslt + i*c, (1.0 / b))

    if is_int(a):
        break
    else:
        i += 1

print("a**b % c:", rslt)
print("a:", a)

You can never be sure that you have found the correct modulo value, it is the first value that is compatible with your settings. The algorithm is based on the fact that a, b and c are integers. If they are not you have no solution a likely combination that was the original one.

Outputs:

Process without c
a**b: 248832
a: 12.000000000000002

Process with c
a**b % c: 82
a: 12.000000000000002

Comments

[Kevin]

I don't think there's an unambiguous solution. Consider: both (4**2)%2 and (6**2)%2 evaluate to 0. So given just b = 2 and c = 2 and a^b%c=0, you don't know whether a is 4 or 6 or any other even number for that matter.

[Azsgy]

I believe this is called the "discrete logarithm problem"? Please correct me if I'm wrong.

[Jean-François Fabre]

I recommend bruteforce. that's used in cryptography for a reason.

[Code-Apprentice]

Azsgy is correct. For more information about this, google "discrete logarithm".

[Stefan Pochmann]

@Azsgy Isn't that to find the exponent, not the base?

[r3mainer]

For an efficient calculation method, see en.wikipedia.org/wiki/Baby-step_giant-step

[Stefan Pochmann]

"The best you can do" [citation needed]

[President James K. Polk]

Sorry, but not only is this not the best you can do, it's incorrect. This assumes that the arguments are floating point numbers but pow(a,b,c) in python only works if all arguments are integers.