如何在Python中找到pow(a,b,c)的逆序？

Question

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

Answer 1

尽管评论中有这样的陈述，但这不是离散对数问题。这更类似于RSA 问题，其中c是两个大素数的乘积，b是加密指数，a是未知的明文。我总是喜欢让x你想要解决的未知变量，所以你有y= x ^b mod c 其中y，b， 和c是已知的，你想要解决x。求解它涉及与 RSA 中相同的基本数论，即您必须计算z=b ^-1 mod \xce\xbb(c)，然后可以求解xvia x= y ^z mod c。\xce\xbb 是Carmichael 的 lambda 函数，但您也可以使用 Euler 的 phi（totient）函数代替。我们将原始问题简化为计算逆模 \xce\xbb(c)。c如果容易因式分解或者我们已经知道 的因式分解，那么这很容易做到c，否则就很难。如果c很小，那么暴力破解是一种可以接受的技术，您可以忽略所有复杂的数学运算。

\n\n

以下是显示这些步骤的一些代码：

\n\n

import functools\nimport math\n\n\ndef egcd(a, b):\n    """Extended gcd of a and b. Returns (d, x, y) such that\n    d = a*x + b*y where d is the greatest common divisor of a and b."""\n    x0, x1, y0, y1 = 1, 0, 0, 1\n    while b != 0:\n        q, a, b = a // b, b, a % b\n        x0, x1 = x1, x0 - q * x1\n        y0, y1 = y1, y0 - q * y1\n    return a, x0, y0\n\n\ndef inverse(a, n):\n    """Returns the inverse x of a mod n, i.e. x*a = 1 mod n. Raises a\n    ZeroDivisionError if gcd(a,n) != 1."""\n    d, a_inv, n_inv = egcd(a, n)\n    if d != 1:\n        raise ZeroDivisionError(\'{} is not coprime to {}\'.format(a, n))\n    else:\n        return a_inv % n\n\n\ndef lcm(*x):\n    """\n    Returns the least common multiple of its arguments. At least two arguments must be\n    supplied.\n    :param x:\n    :return:\n    """\n    if not x or len(x) < 2:\n        raise ValueError("at least two arguments must be supplied to lcm")\n    lcm_of_2 = lambda x, y: (x * y) // math.gcd(x, y)\n    return functools.reduce(lcm_of_2, x)\n\n\ndef carmichael_pp(p, e):\n    phi = pow(p, e - 1) * (p - 1)\n    if (p % 2 == 1) or (e >= 2):\n        return phi\n    else:\n        return phi // 2\n\n\ndef carmichael_lambda(pp):\n    """\n    pp is a sequence representing the unique prime-power factorization of the\n    integer whose Carmichael function is to be computed.\n    :param pp: the prime-power factorization, a sequence of pairs (p,e) where p is prime and e>=1.\n    :return: Carmichael\'s function result\n    """\n    return lcm(*[carmichael_pp(p, e) for p, e in pp])\n\na = 182989423414314437\nb = 112388918933488834121\nc = 128391911110189182102909037 * 256\ny = pow(a, b, c)\nlam = carmichael_lambda([(2,8), (128391911110189182102909037, 1)])\nz = inverse(b, lam)\nx = pow(y, z, c)\nprint(x)\n

\n