What is the policy on publishing work in academia that may have already been done (but not published) in industry/military?

It is fully acceptable to work on, and to publish, results on topics als researched in secret by companies or security agencies. From an academic point of view, there is nothing wrong with that, and neither from the point of view of stealing intellectual property. (But I'm not a lawyer!) Whether those companies or agencies would be unhappy with you publishing some great new technique for breaking cryptosystems - probably not, but unless you believe in conspiracy theories, this is likely not be an issue. (They might try to hire you, though.)

There have been precedents, e.g., on the best algorithms to factor numbers, or some cryptographic algorithms. (I'd have to dig out references for that.)

What can be published is up to the journal editors and reviewers, though in some instances (national security...) the government will step in and put an embargo on publishing.

But the same thing is largely true for such things as trade secret internal things in commerce. As long as you work independently, you can write your papers and submit them. But it is up to others whether they are published.

If something "seems" innovative since all "known" uses are actually unknown then publishers will proceed as usual.

It would, however, probably be a mistake if you try to publish something that you know because of some relationships or employment but that hasn't been revealed publicly. You will probably be talking to a lot of lawyers in that case. Edward Snowden is an extreme case, of course.

In this case, is it acceptable for me to publish this as my own research?

Absolutely, positively, yes.

And it will indeed be your own research.

There's just a single caveat: The above is true as long as you're just suspecting "Oh, those secret government crypto researchers must surely be considering this too." If you actually got tipped off about their findings, then it's a different story.

If I do publish, can I be in trouble for publishing work which these companies/military don't want the public to be aware of (but which I developed independently)?

Ethically/morally - there is nothing wrong with this at all. On the contrary, it is laudatory, and I encourage you to write up your findings as accessibly to lay readers as you can, and publish not just in some obscure conference, but put your paper up on open-access platforms, and make posts to HackerNews, SlashDot, Reddit, or wherever is relevant.

Materially - the closer your publication is to thwarting concrete, specific commercial/military/governmental initiatives - the more likely is it that there will be some consequences to your publishing your work. That doesn't mean it is actually likely; a paper on breaking cryptographic protocols or devising new ones is probably safe enough though. But if your publication will lead immediately to embarrassing information or criminal behavior being exposed, then you cannot discount the possibility. Just look at what governments are doing to whistle-blowers and journalists these days.