Let $K = \mathbb{Q}(\zeta_n)$. If it makes it easier, feel free to restrict to $n = p^k$, or $n = 2^k$ even. I want to find the factorization of any totally-split prime $p$ (smaller is better generically, but not of utmost importance) . It's well-known that: \begin{equation} p\text{ is totally split in }O_K\iff p\equiv 1 \mod n \end{equation} With this in mind, looking at the arithmetic sequence $\{n+1, 2n+1,\dots\}$, and appealing to Dirchlet's theorem on primes in arithmetic progressions is enough to find some $p$, and then I can factor it directly.
My issue is that this seems "wasteful" in a certain sense --- to find some small objects (the individual factors $p_i$), I have to find some large object, and factor it. Without getting into too many specifics, it's insufficient for my purposes. Is there any known way to find the $\mathfrak{p}_i$ factors (that are totally split) "directly"? By this, I mean without appealing to factorization of some large prime, or more specifically in poly-time (in $k$, when $n = p^k$)? Alternatively is there any known method for any number field that's poly-log in the degree?
One thought is that the galois group of $K$ acts transitively on prime decompositions, so it's enough to find a single $\mathfrak{p}_i$. Moreover, we should be able to identify when $\mathfrak{p}_i$ is totally split by checking if it's ramified (via $N(\mathfrak{p}_i)$ and $K$'s known discriminant) and checking that the inertial degree is 1. This suggests some strategy of enumerating small ideals, applying the above checks, and hoping we find one soon. While I don't know precisely how efficient this is, I have strong doubts that it's efficient enough for my purposes.
Is there any known method for finding a single factor in a totally-split prime in a number field efficiently?