¿Cuál es la forma más eficiente de calcular factoriales módulo a primo?

20

¿Conoces algún algoritmo que calcule el factorial después del módulo de manera eficiente?

Por ejemplo, quiero programar:

for(i=0; i<5; i++)
  sum += factorial(p-i) % p;

Pero, pes un gran número (primo) para aplicar factorial directamente .(p108)

En Python, esta tarea es realmente fácil, pero realmente quiero saber cómo optimizar.

jonaprieto
fuente
66
Parece que el problema quiere que uses el teorema de Wilson. Para primer , (p-1)! = -1 \ mod p . Entonces, sin usar ningún lenguaje de programación: la respuesta es 100 . ¿Quizás le gustaría generalizar su problema? p(p1)!=1modp100
Aryabhata
55
¿Puedes decir el problema más claramente? ¿Quieres calcular (X!) (mod (X+1)), o el más general (X!) (mod Y)? Y supongo que factorial(100!)eso realmente no significa que desee aplicar la función factorial dos veces.
Keith Thompson el
1
Incluso si no tuviera el teorema de Wilson, sí tiene ese (mn)modp=(mmodp)(nmodp) , que al menos ayudaría a evitar problemas de desbordamiento.
Dave Clarke el
8
Tenga en cuenta que el teorema de Wilson se aplica solo cuando p es primo. Su pregunta no indica que p es primo, por lo que lo que ha escrito no es correcto.
Dave Clarke el

Respuestas:

11

(Esta respuesta fue inicialmente publicada por el autor de la pregunta jonaprieto dentro de la pregunta).

Recuerdo el teorema de Wilson y noté pequeñas cosas:

En el programa anterior, es mejor si escribo:

(p1)!1(modp)(p2)!(p1)!(p1)11(modp)(p3)!(p2)!(p2)1(p2)1(modp)(p4)!(p3)!(p3)1(p2)1(p3)1(modp) (p5)!(p4)!(p4)1(p2)1(p3)1(p4)1(modp)

Y puede encontrar porque , por lo que con el algoritmo Euclidiano extendido puede encontrar el valor de , ese es el módulo inverso(pi)1gcd(p,pi)=1(pi)1

También puede ver las mismas congruencias, como: entonces, la suma es igual: y si factorizas al principio los factoriales obtienes Y, voila, el módulo inverso es más eficiente que los factoriales.

(p5)!(p24)1(modp)(p4)!(p+6)1(modp)(p3)!(p2)1(modp)(p2)!1(modp)(p1)!1(modp)
(24)1+(6)1+(2)1
8(24)1(modp)
Gilles
fuente
Básicamente . ¡Ordenado! (pk)!(p+(k1)!(1)k)1(modp)
Thomas Ahle
Lo siento, pero cuando factorizo , obtengo:(24)1+61+(2)1
9(24)1=38
1

El ejemplo que está publicando está muy relacionado con el problema # 381 de Euler. Así que publicaré una respuesta que no resuelve el problema de Euler. Publicaré cómo puedes calcular factoriales módulo a primo.

Entonces: ¿Cómo calcular n! módulo p?

Observación rápida: Si n ≥ p, entonces n! tiene un factor p, por lo que el resultado es 0. Muy rápido. Y si ignoramos el requisito de que p debería ser un primo, ¡entonces sea q el factor primo más pequeño de p, yn! módulo p es 0 si n ≥ q. Tampoco hay muchas razones para exigir que p sea primordial para responder a su pregunta.

Ahora en tu ejemplo (n - i)! para 1 ≤ i ≤ 5 surgió. No tiene que calcular cinco factoriales: ¡Calcula (n - 5) !, multiplique por (n - 4) vaya a obtener (n - 4) !, multiplique por (n - 3) para obtener (n - 3)! etc. Esto reduce el trabajo en casi un factor 5. No resuelva el problema literalmente.

La pregunta es cómo calcular n! módulo m. La forma obvia es calcular n !, un número con aproximadamente n log n dígitos decimales, y calcular el módulo restante p. Eso es trabajo duro. Pregunta: ¿Cómo podemos obtener este resultado más rápido? Al no hacer lo obvio.

Sabemos que ((a * b * c) módulo p = (((a * b) módulo p) * c) módulo p.

Para calcular n !, normalmente comenzaríamos con x = 1, luego multiplicaríamos x por 1, 2, 3, ... n. Usando la fórmula del módulo, calculamos n! módulo p sin calcular n !, comenzando con x = 1, y luego para i = 1, 2, 3, .., n reemplazamos x con (x * i) módulo p.

Siempre tenemos x <p e i <n, por lo que solo necesitamos suficiente precisión para calcular x * p, ¡no la precisión mucho más alta para calcular n !. Entonces para calcular n! módulo p para p ≥ 2 tomamos los siguientes pasos:

Step 1: Find the smallest prime factor q of p. If n ≥ q then the result is 0.
Step 2: Let x = 1, then for 1 ≤ i ≤ n replace x with (x * i) modulo p, and x is the result. 

(Algunas respuestas mencionan el teorema de Wilson, que solo responde la pregunta en el caso muy especial del ejemplo dado, y es muy útil para resolver el problema de Euler # 381, pero en general no es útil para resolver la pregunta que se hizo).

gnasher729
fuente
-1

Este es mi uso de implementación del teorema de wilson:

La función factMOD es la que se debe llamar para calcular (n!)% MOD cuando MOD-n es poco contra n.

¿Alguien conoce otro enfoque eficiente cuando no es el caso (por ejemplo: n = 1e6 y MOD = 1e9 + 7)?

ll powmod(ll a, ll b){//a^b % MOD
  ll x=1,y=a;
  while(b){
    if(b&1){
      x*=y; if(x>=MOD)x%=MOD;
    }
    y*=y; if(y>=MOD)y%=MOD;
    b>>=1;
  }
  return x;
} 
ll InverseEuler(ll n){//modular inverse of n
  return powmod(n,MOD-2);
}
ll factMOD(ll n){ //n! % MOD efficient when MOD-n<n
   ll res=1,i;
   for(i=1; i<MOD-n; i++){
     res*=i;
     if(res>=MOD)res%=MOD;
   }
   res=InverseEuler(res);   
    if(!(n&1))
      res= -res +MOD;
  }
  return res%MOD;
}
JeanClaudeDaudin
fuente
1
El código no es realmente sobre el tema, aquí. Una descripción del algoritmo es mucho más útil porque no requiere que las personas entiendan el idioma en el que decidió escribir su código, y porque las implementaciones reales a menudo se optimizan de una manera que las hace más difíciles de entender. Y por favor haga sus preguntas como preguntas separadas, en lugar de en su respuesta. Stack Exchange es un sitio de preguntas y respuestas, no un panel de discusión, y las preguntas son difíciles de encontrar si están ocultas entre las respuestas. ¡Gracias!
David Richerby