Fast way to find the smallest root $\mod M$ of a polynomial Suppose you're given a polynomial of degree $d$ with integer coefficients:
$$
P(x) = \sum_{i=0}^{d}{a_i x^i}
$$
Is there a fast way to find the smallest root modulo $M$, where $M$ is some composite number with known factorization?  (Or is there a reason to believe that there can't be a fast way?)
By "smallest root" I mean the smallest integer $x$ in $\{0, 1, 2, ..., M-1\}$ with $P(x) \equiv 0 \mod M$.  And by "fast" I mean running time that is polynomial in $\log M$ and $d$.
This question occurred to me after reading about Coppersmith's method.  It finds the smallest root, but only if it's less than $M^{1/d}$.  And it doesn't use any information about $M$.  So I wondered if you could do better if you DID know $M$'s factors.
A brute-force way would go like this: Suppose you write $M$ as a product of prime powers, i.e.
$$M = \prod_{j=0}^{k}{{p_j}^{e_j}}$$
First find the roots of $P(x)$ modulo each ${p_j}^{e_j}$, then use CRT to lift every combination of roots up to a root $\mod M$.  Then just pick the smallest one.
But if $M$ has lots of little factors, then you end up with too many combinations and it's worse than polynomial in $\log M$.

It's an old result of Adelman and Manders "NP-complete decision problems for quadratic polynomials" (1976) that solving the equation $ax^2 + by = c$ for $x,y$ in the natural numbers is NP-complete.  The key word here is natural, because this requires not only that $x^2 \equiv c \pmod {b}$ but also that $0 < x \le \sqrt{c/a}$.  It's easy to solve the modular square root problem, but (for general composite $c$) it's hard to determine whether there exists a modular square root below a given bound.  This shows that your problem is also NP-hard: if one could compute the least positive root of polynomials mod $M$ then it would be trivial to decide if there exists one below a given bound.
There's some helpful discussion on the Adelman-Manders paper at:
https://mathoverflow.net/questions/72628/number-theory-and-np-complete
