Chichi 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

in Python:


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:
return roots

if __name__ == "__main__":
p = 17
primitive_roots = primRoots(p)


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

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

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

Answer Source

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 = {}

    def wrapped(a, b):
        key = (a, b)
            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:

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