BSGS&&扩展BSGS

BSGS算法是一种用于求解离散对数问题的算法，可以有效地处理大型的数值计算。以下是BSGS算法的实现代码（使用Python语言）： ```python def bsgs(g, h, p): """ BSGS算法求解离散对数问题 :param g: 原根 :param h: 待求的模p下的离散对数 :param p: 模数 :return: 模p下的离散对数x，使得g^x ≡ h (mod p) """ n = int(p ** 0.5) + 1 # 分块大小 # 构建小的哈希表 table = {pow(g, i, p): i for i in range(n)} # 预处理g^n gn = pow(g, n, p) # 枚举y，计算g^(-ny)，并在哈希表中查找 for j in range(n): y = pow(gn, j, p) z = (h * pow(y, p - 2, p)) % p if z in table: return (j * n + table[z]) % p return None ``` 其中，g为原根，h为待求的模p下的离散对数，p为模数。函数首先计算出分块大小n，然后构建小的哈希表，预处理g^n，枚举y，计算g^(-ny)，并在哈希表中查找，直到找到符合条件的值为止。如果没有找到，则返回None。 需要注意的是，该算法的时间复杂度为O(√p)，空间复杂度为O(√p)。因此，当p较大时，算法的执行效率比较低，需要进行优化。