Computación de símbolos binomiales modulo m

Question

Al mismo tiempo procrastinando, decidí jugar con computing binomiales símbolos modulo $m$, $$\binom{n}{r} \equiv q \pmod{m}, 0 \leq q

Pregunta: ¿Se puede mejorar este algoritmo para calcular $q$? Si esto se ha hecho, ¿qué es una referencia?

Answer 1

Al $m$ es el prime la respuesta es dada por Lucas teorema. El problema se reduce al cálculo de los dígitos de $n$ $r$ base $p$ que se puede hacer en tiempo de $O(\log n)$ (hay también una constante de aquí, dependiendo de $m$).

El problema se reduce al caso de que $m$ es una fuente primaria de energía por el teorema del resto Chino. La respuesta en este caso es al parecer conocido, pero no estoy familiarizado con él; consulte este documento / sitio web por parte de Granville.