How to find a cyclotomic polynomial of degree d that decompose into d irreducible polynomials in $Z_6$?

Question

More specifically, I need the degree $d$ to be around 1024. I can easily find the cyclotomic polynomial of degree 1024 that satisfies the above requirement in $Z_2$, i.e., $x^{1024}+1$, which is equal to $(x+1)^{1024} \bmod 2$. But I don't know either this type of cyclotomic polynomial exists or not in $Z_6$, nor do I know how to find it if it exists?

If this type of cyclotomic poly doesn't exist in $Z_6$, can I find a degree-$d$ cyclotomic polynomial that decomposes into $d$ irreducible polynomials in $Z_{p \times q}$ if $p$ and $q$ are two as small as possible primes? Or two as small as possible co-prime composites for that matter.

Thank you so much in advance.

Answer 1

Sorry, you are out of luck. Let $\phi_n$ denote the $n$-th cyclotomic polynomial. I will show that

(1) $\phi_n$ factors completely into linear factors modulo $p$ (a prime) if and only if $n$ is of the form $m p^k$ where $m$ divides $p-1$ and

(2) If $\phi_n$ factors completely into linear factors modulo $pq$ ($p$ and $q$ distinct primes) then $n$ divides $\max(p-1,q-1)$.

In particular, there are only finitely many such $n$ in case (2). If $p$ and $q$ are co-prime composites, then they are divisible by some pair $p'$ and $q'$ of distinct primes, so there are still only finitely many solutions.

Proof of (1): Let $n = m p^k$ with $p$ not dividing $m$. Then $\phi_n(x) = \phi_m(x^{p^k})/\phi_m(x^{p^{k-1}})$ so $\phi_n(x) \equiv \phi_m(x)^{(p-1) p^{k-1}} \bmod p$. Thus $\phi_n$ splits into linear factors if and only if $\phi_m$ does and we can restrict ourself to the case where $m$ is not divisible by $p$.

We know that $x^{p-1}-1 \equiv \prod_{j=1}^{p-1} (x-j) \bmod p$, so if $m|p-1$ then $\phi_m(x)$ is a products of linears modulo $p$.

In the reverse direction, suppose that $m$ does not divide $p-1$. Let $d = GCD(m,p-1)$, so $d<m$. We know that $x^m-1$ is squarefree modulo $p$ (since $p$ does not divide $m$), so we have $GCD(x^d-1, \phi_m(x))=1$ in $\mathbb{F}_p[x]$.

Now, suppose for the sake of contradiction that $\phi_m(x) \mod p$ had a linear factor, say $x-a$, and note that $a \neq 0$. Then $a^m \equiv 1 \bmod p$. We also know that $a^{p-1} \equiv 1 \bmod p$, so $a^d-1 \equiv 1 \bmod p$ and $x-a$ divides $x^d-1$. But we noted above that $GCD(x^d-1, \phi_m(x))=1$ in $\mathbb{F}_p[x]$, a contradiction. $\square$.

Proof of (2) If $\phi_n$ factors into linears modulo $pq$ then does so modulo $p$ and modulo $q$. So we want $n = m p^k$ with $m|(p-1)$ and $n = m' q^{k'}$ with $m'|q-1$. Without loss of generality, let $p<q$. If $k'>0$ then $q|n$ so $q|m$, but then $m$ cannot divide $q-1$. So, in fact, $k'=0$ and $n=m'$ divides $q-1$, as claimed. $\square$

We can make a more precise statement than (2): Taking $p<q$, we need $n$ to divide $q-1$ and to be of the form $p^k m$ with $m$ dividing $p-1$. This factorization will not be unique, for example, $\phi_4(x) = (x+8)(x-8) = (x+18)(x-18) \bmod 65$. (Note that $4$ divides $5-1$ and $13-1$.)