使用 Python 高效查找原始根模 n？

Question

我正在使用以下代码在 Python 中查找 原根 模 n ：

代码：

 def gcd(a,b):
    while b != 0:
        a, b = b, a % b
    return a

def primRoots(modulo):
    roots = []
    required_set = set(num for num in range (1, modulo) if gcd(num, modulo) == 1)

    for g in range(1, modulo):
        actual_set = set(pow(g, powers) % modulo for powers in range (1, modulo))
        if required_set == actual_set:
            roots.append(g)
    return roots

if __name__ == "__main__":
    p = 17
    primitive_roots = primRoots(p)
    print(primitive_roots)

输出：

 [3, 5, 6, 7, 10, 11, 12, 14]

代码片段摘自： Diffie-Hellman (Github)

---

primRoots 方法能否在 内存使用 和 性能/效率方面得到简化或优化？

原文由 Erba Aitbayev 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

您可以在此处进行的一项快速更改（ 尚未有效优化）是使用列表和集合理解：

 def primRoots(modulo):
    coprime_set = {num for num in range(1, modulo) if gcd(num, modulo) == 1}
    return [g for g in range(1, modulo) if coprime_set == {pow(g, powers, modulo)
            for powers in range(1, modulo)}]

现在，您可以在此处进行的一项强大而有趣的算法更改是使用记忆优化您的 --- gcd 函数。或者更好的是，您可以简单地使用内置 gcd 函数形式 math Python-3.5+ 中的模块或 fractions 以前版本中的模块：—

 from functools import wraps
def cache_gcd(f):
    cache = {}

    @wraps(f)
    def wrapped(a, b):
        key = (a, b)
        try:
            result = cache[key]
        except KeyError:
            result = cache[key] = f(a, b)
        return result
    return wrapped

@cache_gcd
def gcd(a,b):
    while b != 0:
        a, b = b, a % b
    return a
# or just do the following (recommended)
# from math import gcd

然后：

 def primRoots(modulo):
    coprime_set = {num for num in range(1, modulo) if gcd(num, modulo) == 1}
    return [g for g in range(1, modulo) if coprime_set == {pow(g, powers, modulo)
            for powers in range(1, modulo)}]

如评论中所述，作为一种更 pythoinc 优化器的方式，您可以使用 fractions.gcd （或 Python-3.5+ math.gcd ）。

原文由 Mazdak 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

根据 Pete 的评论和 Kasramvd 的回答，我可以这样建议：

 from math import gcd as bltin_gcd

def primRoots(modulo):
    required_set = {num for num in range(1, modulo) if bltin_gcd(num, modulo) }
    return [g for g in range(1, modulo) if required_set == {pow(g, powers, modulo)
            for powers in range(1, modulo)}]

print(primRoots(17))

输出：

 [3, 5, 6, 7, 10, 11, 12, 14]

---

变化：

• 它现在使用 pow 方法的第三个参数作为模数。
• 切换到 math 中定义的 gcd 内置函数（对于 Python 3.5 ）以提高速度。

---

关于内置 gcd 的附加信息在这里： Co-primes checking

原文由 Erba Aitbayev 发布，翻译遵循 CC BY-SA 3.0 许可协议