1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Am I right --- you do not care of the fact that $\mathbb Z_6$ is not factorial? $\endgroup$ May 15, 2019 at 6:23
  • $\begingroup$ Sorry, I don't know that much about the theory of cyclotomic poly. Just happen to use it in a project. Would you please let me know why this matters? Does it imply this type of cyclotomic poly doesn't exist in $\mathbb{Z}_6$? Thanks. $\endgroup$
    – user67451
    May 15, 2019 at 6:42
  • $\begingroup$ Can I find a $d$-degree cyclotomic poly that decomposes into $d$ irreducible polys in $\mathbb{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. $\endgroup$
    – user67451
    May 15, 2019 at 6:59

1 Answer 1

4
$\begingroup$

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$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.