  Any ideal in a number field can be factored into a product of prime ideals.
In this paper we study the prime ideal shortest vector problem (SVP) in the
ring $ \Z[x]/(x^{2^n} + 1) $, a popular choice in the design of ideal lattice
based cryptosystems. We show that a majority of rational primes lie under prime
ideals admitting a polynomial time algorithm for SVP. Although the shortest
vector problem of ideal lattices underpins the security of Ring-LWE
cryptosystem, this work does not break Ring-LWE, since the security reduction
is from the worst case ideal SVP to the average case Ring-LWE, and it is
one-way.
