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.
