# How to choose a prime p s.t. n-th cyclotomic polynomial splits into as much as possible irreducible polynomials while p is almost constant size?

The reason I ask this question is that cyclotomic polynomial is critical to the construction of lattice-based cryptography. In most of the existing lattice-based cryptographic schemes, $$n$$ is usually chosen to be the power of 2, and according to Corollary 1.2 of Short, Invertible Elements in Partially Splitting Cyclotomic Rings and Applications to Lattice-Based Zero-Knowledge Proofs'' (https://eprint.iacr.org/2017/523.pdf), $$p$$ is equal to $$2k+1 \mod 4k$$, where $$k$$ is the number of irreducible polynomials $$X^n+1$$ can split into in $$\mathbb{Z}_p[X]$$. In other words, the size of $$p$$ seems to depend on the size of $$k$$ in this case.

I wonder what would happen in the general case of cyclotomic polynomial where $$n$$ is not necessarily the power of 2. According to Wikipedia (https://en.wikipedia.org/wiki/Cyclotomic_polynomial#Cyclotomic_polynomials_over_a_finite_field_and_over_p-adic_integers, sorry this is the best source I can find regarding this topic), the cyclotomic polynomial $${\displaystyle \Phi _{n}}$$ factorizes into $${\displaystyle {\frac {\varphi (n)}{d}}}$$ irreducible polynomials of degree $$d$$, where $${\displaystyle \varphi (n)}$$ is Euler's totient function and $$d$$ is the multiplicative order of $$p \mod n$$. I wonder if I choose $$d$$ to be, say $$\sqrt{\varphi (n)}$$, which means the number of resulting split polynomials would be around $$\sqrt{\varphi (n)}$$ while $$p$$ should satisfy $$p^{\sqrt{\varphi (n)}}=1\bmod n$$. Can I say with high probability there exists a $$p$$ of size $$O(|\log_{\sqrt{\varphi (n)}}(n)|)$$ such that $$p^{\sqrt{\varphi (n)}}=1\bmod n$$ holds? As a result, I can claim the conclusion mentioned in the title holds. For practical purpose, $$d$$ doesn't have to be $$\sqrt{\varphi (n)}$$, it could well be $$\varphi (n)^{\frac{1}{k}}$$, where $$k$$ is an integer that is $$\geq 2$$. In which case, $$p^{\varphi (n)^{\frac{1}{k}}}=1 \bmod n$$ still needs to hold. Can I argue in this general case, there still exists a parameter choice such that the size of $$p$$ is $$O(|\log_{\varphi (n)^{\frac{1}{k}}}(n)|)$$ for the above condition to hold?

This seems to hold when $$n$$ is a certain prime. For instance, one could see when $$n=5$$ and $$d=4$$, $$p$$ can be either 2 or 3. But still, I don't know how I could generalize from this special case to specify the condition under which the above conclusion holds? Thank you so much in advance.

• $\sqrt{\phi(n)}$ is unlikely to be an integer, so choosing $d$ to be $\sqrt{\phi(n)}$ is a non-starter. $d$ must be a divisor of $\phi(n)$, so you may not have many choices available for $d$, and maybe none of any particular order of magnitude. E.g., $\phi(n)$ could be twice a prime. Apr 29, 2019 at 12:38
• How could p be that small? Shouldn’t p be on the order of n^{1/\sqrt{\phi(n)}}? Apr 30, 2019 at 9:29