Let $N$ be a positive integer. Thanks to the Miller-Rabin test and the work of Agrawal, Kayal and Saxena, these days people have much much faster algorithms for testing whether $N$ is prime or composite than they do for explicitly finding its factorisation.

If you stand at a sufficient distance, the key idea behind both Miller-Rabin and AKS (and every other primality test I've seen) is to work with the ring of residues modulo $N$, and use clever tricks to see whether it has the algebraic properties that it would have if $N$ were prime. Miller-Rabin looks to see if the roots of $1$ behave how Fermat says they should in that ring; AKS tries to verify a certain polynomial identity in it.

Are there any other properties of $N$'s factorisation that can be checked in less time than it takes to actually find that factorisation, using similar ideas? For example, is it reasonable to ask for an algorithm which takes a composite $N$ and says something useful about how many prime factors it has? This question is related to the number of square roots of $1$ in the residue ring, so might conceivably be effectively detectable by some devilishly clever trick. Similarly, the distribution of residue classes of the prime factors modulo small integers is closely related to the number of roots of unity of small orders.

Or is it simply the case that, once you know that the ring is not a field, you just have so little control over it that no good trickery is known?

I read on a webpage about squarefree integers that no such rapid algorithm is known which tests for repeated prime factors, but that doesn't seem to render the general question invalid (though, if nobody can suggest any positive results in this direction, it would lead us to guess that it's hard, perhaps).

1more comment