如何在python中找到pow（a，b，c）的指数

Question

python中的pow(a,x,c)运算符返回(a**x)%c。如果我有a，c的值和这个运算的结果，我怎么能找到x的值呢

此外，这是我所有的信息

pow(a,x,c) = pow(d,e,c)

我知道a，c，d和e的值

这些数字非常大（a=814779647738427315424653119，d=3，e=401376773778629769409284441239，c=12233344555666677777），所以我不能直接计算这些值

我知道Carmichael's lambda function可以用来解a，但我不确定这是否和/或如何适用于解x

任何帮助都将不胜感激

Answer 1

正如@user2357112在评论中所说的，这是离散对数问题，对于大c来说，计算起来非常困难，并且没有已知的快速通解

但是，对于小c，仍然可以做一些事情。假设a和c是互质，有一个指数k<；使a^k=1模c，之后功率重复。设b=a^x。所以，如果你通过计算a的所有幂来强迫它，直到你得到b，你最多需要循环c次：

def do_log(a, b, c):
    x = 1
    p = a
    while p != b and p != 1:
        x += 1
        p *= a
        p %= c
    if p == b:
        return x
    else:
        return None # no such x

如果使用相同的a多次运行此计算，则可以做得更好

# a, c constant
p_to_x = {1: 0}
x = 1
p = a
while p != 1:
    p_to_x[p] = x
    x += 1
    p *= a
    p %= c

def do_log_a_c(b):
    return p_to_x[b]

在这里，缓存是在循环中生成的，最多运行c次，缓存是在log函数中访问的