Chichi Chichi - 1 month ago 17
Python Question

Efficient finding primitive roots modulo n using Python?

I'm using the following code for finding primitive roots modulo

n
in Python:

Code:

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)


Output:

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


Code fragment extracted from here: Diffie-Hellman (Github)




Question: can the
primRoots
method be simplified or optimized in terms of memory usage and performance/efficiency?

Answer

One quick change is using list and set comprehensions:

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

Another one would be memoization on gcd function:

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

For refusing of doing all the process for all duplicates:

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