Chichi - 3 years ago 579
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?

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
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download