Cyclotomic Polynomials and Primitive Roots of Unity

asked 2023-11-28 23:11:59 +0100

Rohit
1

updated 2023-11-29 00:59:40 +0100

6560 ●9 ●47 ●155

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 flag offensive close merge delete

add a comment

1 Answer

Sort by » oldest newest most voted

answered 2023-11-29 15:38:25 +0100

Max Alekseyev

6560 ●9 ●47 ●155

updated 2023-11-29 16:29:27 +0100

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)

edit flag offensive delete link

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2023-11-28 23:10:54 +0100

Seen: 369 times

Last updated: Nov 29 '23

Cyclotomic Polynomials and Primitive Roots of Unity edit

1 Answer