title: Roots of a polynomial mod a prime
body: <p>I'm looking for a speedy algorithm to find the roots of a univariate polynomial in a prime finite field. </p>
  
  <p>That is, if <code>f = a<sub>0</sub> + a<sub>1</sub>x + a<sub>2</sub>x<sup>2</sup> + ... + a<sub>n</sub>x<sup>n</sup></code>  (n > 0) then an algorithm that finds all <code>r &lt; p</code> satisfying <code>f(r) = 0 mod p</code>, for a given prime p. </p>
  
  <p>I found Chiens search algorithm <a href="https://en.wikipedia.org/wiki/Chien_search" rel="noreferrer">https://en.wikipedia.org/wiki/Chien_search</a> but I can't imagine this being that fast for primes greater than 20 bits. Does anyone have experience with Chien's search algorithm or know a faster way? Is there a sympy module for this?  </p>