Randomized algorithm to determine if a polynomial over $\mathbb{Z}/p$ is irreducible

Question

Is there an efficient (possibly randomized) algorithm to determine if a given polynomial $p(x) \in \mathbb{Z}/p\mathbb{Z}[n]$ is irreducible?

Answer 1

Here is the algorithm that works, and it appears to be significantly faster than factoring. This comes from the Handbook of Applied Cryptography, whose notes can be found online here: http://cacr.uwaterloo.ca/hac/