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

发布时间：2020-12-20 12:11:25 所属栏目：Python 来源：网络整理

导读：我正在使用以下代码在 Python中查找 primitive roots模数：码： def gcd(a,b): while b != 0: a,b = b,a % b return adef primRoots(modulo): roots = [] required_set = set(num for num in range (1,modulo) if gcd(num,modulo) == 1) for g in range(1,m

我正在使用以下代码在 Python中查找 primitive roots模数：

码：

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

解决方法

您可以在此处进行的一项快速更改(尚未有效优化)是使用列表和设置理解：

def primRoots(modulo):
    coprime_set = {num for num in range(1,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 function.或者更好的是,您可以在Python-3.5中使用内置的gcd函数形式数学模块或在以前的版本中使用分数模块：

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

正如评论中所提到的,作为更多pythoinc优化器方法,您可以使用fractions.gcd(或Python-3.5 math.gcd).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!