如何在python中找到pow(a，b，c)的反向? [英] How to find reverse of pow(a,b,c) in python?

问题描述

pow(a,b,c)运算符返回(a**b)%c.如果我有b，c的值以及此操作(res=pow(a,b,c))的结果，如何找到a的值?

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?

推荐答案

尽管注释中的语句这不是离散对数问题，但不是.这更类似于 RSA问题，其中c是两个结果的乘积大素数，b是加密指数，a是未知的明文.我总是喜欢使x为您要解决的未知变量，因此您具有y = x ^b mod c，其中已知y，b和c ，您想求解x.解决它涉及与RSA中相同的基本数论，即必须计算z = b ^-1 modλ(c)，然后可以通过x =来求解x. y ^z mod c. λ是 Carmichael的lambda函数，但是您也可以改用Euler的phi(totient)函数.我们已经将原始问题简化为计算逆模λ(c).如果c易于分解，或者我们已经知道c的分解，那么就很容易做到，否则很难.如果c小，那么蛮力是可以接受的技术，您可以忽略所有复杂的数学运算.

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)

这篇关于如何在python中找到pow(a，b，c)的反向?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！