Suponga que dado un polinomio de grado $d$ con coeficientes enteros:
$$ P(x) = \sum_{i=0}^{d}{a_i x^i} $$
Es allí una manera rápida de encontrar el más pequeño de raíz modulo $M$ donde $M$ es algún número compuesto con conocidos de la factorización? (O es que hay una razón para creer que no puede haber una manera rápida?)
Por "más pequeño de la raíz" me refiero a el entero más pequeño $x$ en $\{0, 1, 2, ..., M-1\}$ con $P(x) \equiv 0 \mod M$. Y por "rápido", me refiero a tiempo de ejecución que es el polinomio en $\log M$ e $d$.
Esta pregunta se me ocurrió después de leer acerca de Calderero del método. Encuentra las más pequeñas de la raíz, pero sólo si es menos de $M^{1/d}$. Y no utiliza ningún tipo de información acerca de $M$. Así que me preguntaba si usted podría hacerlo mejor si no sabian $M$'s factores.
Un ataque de fuerza bruta manera sería así: Supongamos que escribe $M$ como un producto de primer poderes, es decir,
$$M = \prod_{j=0}^{k}{{p_j}^{e_j}}$$
En primer lugar, encontrar las raíces de $P(x)$ modulo de cada ${p_j}^{e_j}$, a continuación, utilizar la CRT para levantar cada combinación de raíces hasta una raíz $\mod M$. A continuación, sólo tiene que elegir la más pequeña.
Pero si $M$ tiene un montón de factores, entonces termina con demasiadas combinaciones y es peor que el polinomio en $\log M$.
