如何在 python 中找到 pow(a,b,c) 的反转？

Question

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

Answer 1

你能做的最好的事情是这样的：

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)

您永远无法确定找到了正确的模值，它是与您的设置兼容的第一个值。该算法基于 a、b 和 c 是整数这一事实。如果不是，则您无法找到可能的组合，即原始组合。

输出：

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

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

Answer 2

尽管评论中有陈述，但这不是离散对数问题。这更类似于 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，但您也可以改用 Euler 的 phi (totient) 函数。我们已将原始问题简化为计算逆 mod λ(c)。如果 c 很容易因式分解或者我们已经知道 c 的因式分解，这很容易做到，否则很难。如果 c 很小，那么蛮力是一种可以接受的技术，您可以忽略所有复杂的数学运算。

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

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) 的反转？

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

python

math

encryption

cryptography

modulus