Quel est le moyen le plus efficace pour calculer les factorielles modulo un nombre premier?

Connaissez-vous un algorithme qui calcule efficacement la factorielle après module?

Par exemple, je veux programmer:

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

Mais, pest un grand nombre (premier) pour appliquer directement factorielle .$(p \leq 10^ 8)$

En Python, cette tâche est vraiment facile, mais je veux vraiment savoir comment optimiser.

(Cette réponse a été initialement publiée par le demandeur Jonaprieto à l'intérieur de la question.)

Je me souviens du théorème de Wilson et j'ai remarqué de petites choses:

Dans le programme ci-dessus, il vaut mieux écrire:

$$\begin{align} (p-1)! &\equiv -1 &\pmod p\\ (p-2)! &\equiv (p-1)! (p-1)^ {-1} \equiv \bf{1} &\pmod p\\ (p-3)! &\equiv (p-2)! (p-2)^ {-1} \equiv \bf{(p-2)^{-1}} &\pmod p\\ (p-4)! &\equiv (p-3)! (p-3)^ {-1} \equiv \bf{(p-2)^{-1}} \bf{(p-3)^{-1}} &\pmod p\\ \ (p-5)! &\equiv (p-4)! (p-4)^ {-1} \equiv \bf{(p-2)^{-1}} \bf{(p-3)^{-1}}\bf{(p-4)^{-1}} &\pmod p\\ \end{align}$$

Et vous pouvez trouver parce que , donc avec l' algorithme euclidien étendu, vous pouvez trouver la valeur de , qui est le module inverse. pgcd ( p , p - i ) = 1 ( p - i ) - $(p-i)^{-1}$$\operatorname{gcd}(p, p-i) = 1$$(p-i)^{-1}$

Vous pouvez aussi voir les mêmes congruences, comme: donc, la somme est égale: et si vous factorisez au début les factorielles vous obtenez Et, le tour est joué, le module inverse est plus efficace que les factorielles. (-24)-1+(6)-1+(-2)-18⋅(-24)-

$$\begin{align*} (p-5)! &\equiv (p-24)^{-1}&\pmod p\\ (p-4)! &\equiv (p+6)^{-1}&\pmod p\\ (p-3)! &\equiv (p-2)^{-1} &\pmod p\\ (p-2)! &\equiv 1&\pmod p\\ (p-1)! &\equiv -1&\pmod p\\ \end{align*}$$ $$(-24)^{-1}+(6)^{-1} +(-2)^{-1}$$ $$8\cdot (-24)^{-1} \pmod p$$

L'exemple que vous publiez est étroitement lié au problème Euler n ° 381. Je vais donc poster une réponse qui ne résout pas le problème d'Euler. Je posterai comment vous pouvez calculer un factoriel modulo un nombre premier.

Donc: Comment calculer n! modulo p?

Observation rapide: si n ≥ p, alors n! a un facteur p, donc le résultat est 0. Très rapide. Et si nous ignorons l'exigence que p soit un nombre premier, alors q soit le plus petit facteur premier de p, et n! modulo p vaut 0 si n ≥ q. Il n'y a pas non plus beaucoup de raisons d'exiger que p soit un nombre premier pour répondre à votre question.

Maintenant dans votre exemple (n - i)! pour 1 ≤ i ≤ 5 est venu. Vous n'avez pas à calculer cinq factorielles: vous calculez (n - 5) !, multipliez par (n - 4) allez chercher (n - 4) !, multipliez par (n - 3) pour obtenir (n - 3)! etc. Cela réduit le travail de près d'un facteur 5. Ne résolvez pas le problème littéralement.

La question est de savoir comment calculer n! modulo m. La façon la plus évidente est de calculer n !, un nombre avec approximativement n log n chiffres décimaux, et de calculer le reste modulo p. C'est un travail difficile. Question: Comment pouvons-nous obtenir ce résultat plus rapidement? En ne faisant pas la chose évidente.

Nous savons que ((a * b * c) modulo p = ((((a * b) modulo p) * c) modulo p.

Pour calculer n !, nous commencerions normalement par x = 1, puis multiplierions x par 1, 2, 3, ... n. En utilisant la formule modulo, nous calculons n! modulo p sans calculer n !, en commençant par x = 1, puis pour i = 1, 2, 3, .., n on remplace x par (x * i) modulo p.

Nous avons toujours x <p et i <n, nous n'avons donc besoin que de suffisamment de précision pour calculer x * p, et non d'une précision beaucoup plus élevée pour calculer n !. Donc, pour calculer n! modulo p pour p ≥ 2 nous prenons les mesures suivantes:

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. 

(Certaines réponses mentionnent le théorème de Wilson, qui ne répond à la question que dans le cas très particulier de l'exemple donné, et est très utile pour résoudre le problème d'Euler # 381, mais en général n'est pas utile pour résoudre la question qui a été posée).

Ceci est mon utilisation de mise en œuvre du théorème de Wilson:

La fonction factMOD est celle à appeler pour calculer (n!)% MOD lorsque MOD-n est peu contre n.

Est-ce que quelqu'un connaît une autre approche efficace quand ce n'est pas le cas (par exemple: n = 1e6 et 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;
}