# Cyclotomic Polynomials and Primitive Roots of Unity

I want to print the primitive root of unity $\zeta_m$ associated with the $m'th$ cyclotomic polynomial $\phi_m(x)$ where m is a power of two. I want to print the primitive root of this polynomial over $\mathbb{Z}_p$ with $p$ prime.

I tried the following as an example, with $p = 12206081$ and $m = 16384$. However this prints all the totient(16384) roots rather than just the primitive root.

x = PolynomialRing(GF(12206081), 'x').gen()
n = euler_phi(16384)
f = x^n + 1
print(f.roots())

edit retag close merge delete

Sort by ยป oldest newest most voted

Here is a sample code that iterates over the roots of cyclotomic polynomial until it finds a primitive one:

p = 12206081
F = GF(p)
m = 16384
P = prime_divisors(m)
prim_root = next(r for r in cyclotomic_polynomial(m).roots(F,multiplicities=False) if all(r^(m//p)!=F.one() for p in P))


A faster way is just to take a primitive root modulo $p$ and raise it to the power $(p-1)/m$:

p = 12206081
m = 16384
assert (p-1)%m == 0
prim_root = Mod(primitive_root(p),p)^((p-1)//m)

more