使用Python有效地发现原始根模数？

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方法可以在内存使用和性能 /效率方面进行简化或优化吗？

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)}]

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

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）。

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方法的3-rd参数作为模数.
• 切换到gcd内置函数math(在Python中定义3.5)以提高速度.

有关内置gcd的更多信息,请访问: 联合质量检查