How To Find Reverse Of Pow(a,b,c) In Python?

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 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 mod λ(c), and then you can solve for x via x = y 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


defegcd(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, 1while 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


definverse(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


deflcm(*x):
    """
    Returns the least common multiple of its arguments. At least two arguments must be
    supplied.
    :param x:
    :return:
    """ifnot x orlen(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)


defcarmichael_pp(p, e):
    phi = pow(p, e - 1) * (p - 1)
    if (p % 2 == 1) or (e >= 2):
        return phi
    else:
        return phi // 2defcarmichael_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 = 125defis_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 = 0whileTrue:

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

    if is_int(a):
        breakelse:
        i += 1print("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:

Processwithoutca**b: 248832a: 12.000000000000002Processwithca**b % c: 82a: 12.000000000000002