Scope of a function to generate list of primitive roots of a given number

[Devesh Sawant]

I was using Sympy 1.7 and playing around topics in number theory, specifically properties of primitive roots of a given number.

In the midst of checking whether a root of p is also a root of p^2 , I had to generate a list of primitive roots.

I came up with a straightforward implementation to calculate it.

def all_primitive_roots(n):
    phi_n, relatively_prime = totient(n), [a for a in range(2,n) if igcd(a, n) == 1]
    if n == 1:
        return None
    elif n <= 4:
        return [n-1]

    return list(filter(lambda x: n_order(x,n) == phi_n, relatively_prime))

There definitely seems to be ways to optimize this. Also, there doesn't seem to be a function in Sympy for this. I think there can be uses for such a function there. Any pointers on this?

[S.Y. Lee]

Although we already have primitive_root and is_primitive_root, it can be added because there is no way to generate every primitive roots under n straightforward way

https://reference.wolfram.com/language/ref/PrimitiveRootList.html

But I'd appreciate more research on this such that it can use better algorithm than simply trying out all the candidates