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

Question

我正在使用以下代码查找 primitive roots 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)}]

现在，您可以在此处进行的一项强大而有趣的算法更改是优化您的 gcd function使用 memoization .或者更好的是，您可以简单地使用内置的 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)。