求解离散对数h=pow(g,x,p)：优化含缺失位x的暴力破解速度

嘿，这个场景我太熟悉了——10层嵌套循环暴力枚举确实会让Python慢到让人抓狂，毕竟哪怕2^10=1024次迭代看似不多，但每次都要执行大数模幂运算，累积下来的开销完全不可忽视。下面给你几个能大幅提速的实用方案，亲测有效：

这是针对这种部分已知私钥+少量缺失位场景的最优解，能把时间复杂度从O(2^n)降到O(2(n/2))，n是缺失位数量（这里n=10，直接从1024次运算降到64次）。

核心思路： #

把10个缺失位分成两组（比如5个一组），先预计算第一组所有可能的模幂结果并存在哈希表中，再遍历第二组的所有可能，通过逆运算查找哈希表中是否存在匹配项，找到后就能组合出完整的私钥x。

具体步骤：

• 把x拆分为 x = x_known + x_missing，其中x_missing是10个缺失位对应的数值之和。
• 将x_missing拆分为x_left + x_right（两组缺失位的数值和）。
• 原方程变形为：h * g^(-x_known) ≡ g^(x_left) * g^(x_right) mod p，令左边为target。
• 预计算所有g^(x_left) mod p的结果，存入字典（键是结果，值是对应的x_left）。
• 遍历所有g^(x_right) mod p，计算target * inv(g^(x_right)) mod p，去字典中查找是否存在匹配的g^(x_left)，找到后即可拼接出完整的x。

代码示例： #

from collections import defaultdict

def solve_partial_discrete_log(h, g, p, x_known, missing_bit_positions):
    # 拆分缺失位为两组
    n = len(missing_bit_positions)
    split_idx = n // 2
    left_bits = missing_bit_positions[:split_idx]
    right_bits = missing_bit_positions[split_idx:]

    # 预计算每个缺失位对应的g^(2^bit) mod p
    left_terms = [pow(g, 1 << bit, p) for bit in left_bits]
    right_terms = [pow(g, 1 << bit, p) for bit in right_bits]

    # 计算目标值：target = h * g^(-x_known) mod p
    # 假设p是素数，用费马小定理求逆元；若p非素数，改用扩展欧几里得算法
    inv_g_xknown = pow(g, p-2 - x_known % (p-1), p)
    target = (h * inv_g_xknown) % p

    # 预计算左边所有可能的组合
    left_map = defaultdict(list)
    for mask in range(0, 1 << split_idx):
        current_val = 1
        for i in range(split_idx):
            if mask & (1 << i):
                current_val = (current_val * left_terms[i]) % p
        left_map[current_val].append(mask)

    # 遍历右边组合，查找匹配项
    for mask in range(0, 1 << (n - split_idx)):
        current_val = 1
        for i in range(n - split_idx):
            if mask & (1 << i):
                current_val = (current_val * right_terms[i]) % p
        # 计算需要匹配的左边值：needed = target * inv(current_val) mod p
        inv_current = pow(current_val, p-2, p)
        needed = (target * inv_current) % p
        if needed in left_map:
            # 拼接完整x并验证
            for left_mask in left_map[needed]:
                full_x = x_known
                # 还原左边缺失位
                for i in range(split_idx):
                    if left_mask & (1 << i):
                        full_x += 1 << left_bits[i]
                # 还原右边缺失位
                for i in range(n - split_idx):
                    if mask & (1 << i):
                        full_x += 1 << right_bits[i]
                # 验证结果正确性
                if pow(g, full_x, p) == h:
                    return full_x
    return None

如果暂时不想改算法，至少把每个缺失位对应的g^(2^bit)预计算好，枚举时只需要做乘法模p，而不是每次调用pow。比如：

# 预计算所有缺失位的基项
missing_terms = [pow(g, 1 << bit, p) for bit in missing_bit_positions]
# 枚举时直接组合这些项
for mask in range(0, 1 << 10):
    current_val = 1
    for i in range(10):
        if mask & (1 << i):
            current_val = (current_val * missing_terms[i]) % p
    # 验证current_val是否匹配目标值...

这样每次枚举的运算量从10次模幂变成10次模乘，速度会提升一大截。

如果还是想用暴力枚举，用numba把循环部分编译成机器码，能让Python的循环速度接近C的水平。比如给枚举函数加上@numba.njit装饰器：

import numba

@numba.njit
def brute_force_solve(h, g, p, x_known, missing_terms, missing_bit_positions, target):
    n = len(missing_terms)
    for mask in range(0, 1 << n):
        current_x = x_known
        current_val = 1
        for i in range(n):
            if mask & (1 << i):
                current_x += 1 << missing_bit_positions[i]
                current_val = (current_val * missing_terms[i]) % p
        if current_val == target:
            return current_x
    return None

注意numba对Python语法有一些限制，提前预计算好missing_terms和target再传入函数。

因为每个枚举任务都是独立的，可以用multiprocessing把任务拆分到多个CPU核心上，速度能接近核心数倍的提升。比如把1024个任务分成4份，每个进程处理256个：

from multiprocessing import Pool

def worker(args):
    start, end, x_known, missing_terms, missing_bit_positions, target, g, p = args
    for mask in range(start, end):
        current_x = x_known
        current_val = 1
        for i in range(len(missing_terms)):
            if mask & (1 << i):
                current_x += 1 << missing_bit_positions[i]
                current_val = (current_val * missing_terms[i]) % p
        if current_val == target:
            return current_x
    return None

if __name__ == "__main__":
    num_processes = 4
    total_tasks = 1 << 10
    task_ranges = [(i*total_tasks//num_processes, (i+1)*total_tasks//num_processes) for i in range(num_processes)]
    # 准备每个进程的参数
    task_args = [(start, end, x_known, missing_terms, missing_bit_positions, target, g, p) for start, end in task_ranges]
    with Pool(num_processes) as pool:
        results = pool.map(worker, task_args)
    # 从结果中提取有效x
    full_x = next(res for res in results if res is not None)

额外提示： #

• 一定要验证最终得到的x，避免哈希冲突或计算错误导致的假阳性。
• 如果p不是素数，求逆元时要改用扩展欧几里得算法pow(g, -1, p)（Python 3.8+支持）。

内容的提问来源于stack exchange，提问作者thunder