Es n! mod p factible en la sub O(n) tiempo?

Question

Lo pregunto porque puedo usar Lucas Teorema para hallar n elegir k mod p, pero no saben de un equivalente de permutaciones (n permutar k mod p).

Answer 1

Si $k\geq p$, entonces la respuesta es cero y hemos terminado. De otra manera:

Deje $M=\lfloor \sqrt{k}\rfloor$.

1. Definir un polinomio: $f(x)=x(x+1)\dotsm (x+M-1)$.
2. Hay un divide y vencerás algoritmo para evaluar $f(x)$ simultáneamente en $M$ puntos (véase el Moderno sistema de Álgebra / Joachim von zur Gathen, Jürgen Gerhard).
3. Vamos a evaluar en $n-k+1, n-k+1+M,n-k+1+2M,\dotsc,n-k+1+(M-1)M$.
4. Vamos a obtener los valores de $f(n-k+1), f(n-k+1+M),f(n-k+1+2M),\dotsc,f(n-k+1+(M-1)M)$.
5. Ahora solo multiplicar todos los valores para obtener $f(n-k+1)\cdot f(n-k+1+M) \cdot f(n-k+1+2M)\dotsm f(n-k+1+(M-1)M)$.
6. Si $\sqrt{k}$ es un número entero, entonces estamos hecho. Por otra parte, necesitamos a a $M$ más de multiplicaciones.

La complejidad es acerca de $O(\sqrt{p})$ algunas veces logarítmica factores, así que es mejor que el $O(p)$ ingenuos solución. (el botteleck con el logarítmica de los factores es en el Paso 3).