Chichi - 1 year ago 357

Python Question

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

`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]`

`primRoots`

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

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