“Efficiently” has multiple meanings. In the context of P and NP, “efficiently” just means in P - it says nothing about how hard the algorithm would actually be to implement, nor how expensive the computation actually would be. O(n^100) is in P, but it’s thoroughly impractical in practice, even for the NSA.

Indeed, the authors who proved that primality testing was in P did so with, IIRC, an O(n^12) algorithm (with n being the number of bits), which is not much use in practice. Although, in that case the result was already widely suspected to be true, and fast, randomized (non-deterministic but highly accurate) polynomial-time algorithms were already known.