Was ist der effizienteste Weg, um Fakultäten modulo einer Primzahl zu berechnen?

20

Kennen Sie einen Algorithmus, der die Fakultät nach dem Modul effizient berechnet?

Zum Beispiel möchte ich programmieren:

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

Ist paber eine große Zahl (Primzahl), um Fakultät direkt anzuwenden (p108) .

In Python ist diese Aufgabe wirklich einfach, aber ich möchte wirklich wissen, wie man optimiert.

Jonaprieto
quelle
6
Es scheint, als würde das Problem Sie veranlassen, den Satz von Wilson zu verwenden. Für prime p , (p1)!=1modp . Also ohne Programmiersprache: Die Antwort ist100 . Vielleicht möchten Sie Ihr Problem verallgemeinern?
Aryabhata
5
Können Sie das Problem klarer darlegen? Möchten Sie berechnen (X!) (mod (X+1)), oder die allgemeinere (X!) (mod Y)? Und ich nehme an, das factorial(100!)heißt nicht, dass Sie die Fakultätsfunktion zweimal anwenden möchten.
Keith Thompson
1
Selbst wenn Sie nicht Wilsons Theorem hatten, haben Sie das , was zumindest helfen würde, Überlaufprobleme zu vermeiden. (mn)modp=(mmodp)(nmodp)
Dave Clarke
8
Beachten Sie, dass der Satz von Wilson nur gilt, wenn p Primzahl ist. Ihre Frage besagt nicht, dass eine Primzahl ist, was Sie also geschrieben haben, ist nicht korrekt. p
Dave Clarke
10
Das kommt
mir

Antworten:

11

(Diese Antwort wurde ursprünglich vom Fragesteller jonaprieto in der Frage gepostet .)

Ich erinnere mich an Wilsons Theorem und bemerkte kleine Dinge:

Im obigen Programm ist es besser, wenn ich schreibe:

(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)

Und Sie können weil gcd ( p , p - i ) = 1 ist. Mit dem erweiterten Euklidian-Algorithmus können Sie also den Wert von ( p - i ) - 1 finden , dh den inversen Modul.(pi)1gcd(p,pi)=1(pi)1

Sie können die gleichen Kongruenzen wie folgt anzeigen:

(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)
And, voila, inverse modulus is more efficient than factorials.
Gilles
quelle
So basically (pk)!(p+(k1)!(1)k)1(modp). Neat!
Thomas Ahle
Sorry but when I factorize (24)1+61+(2)1, I get :
9(24)1=38
1

The example that you are posting is very closely related to Euler problem #381. So I will post an answer that doesn't solve the Euler problem. I will post how you can calculate factorials modulo a prime.

So: How to calculate n! modulo p?

Quick observation: If n ≥ p, then n! has a factor p, so the result is 0. Very quick. And if we ignore the requirement that p should be a prime then let q be the smallest prime factor of p, and n! modulo p is 0 if n ≥ q. There's also not much reason to require that p is a prime to answer your question.

Now in your example (n - i)! for 1 ≤ i ≤ 5 came up. You don't have to calculate five factorials: You calculate (n - 5)!, multiply by (n - 4) go get (n - 4)!, multiply by (n - 3) to get (n - 3)! etc. This reduces the work by almost a factor 5. Don't solve the problem literally.

The question is how to calculate n! modulo m. The obvious way is to calculate n!, a number with roughly n log n decimal digits, and calculate the remainder modulo p. That's hard work. Question: How can we get this result quicker? By not doing the obvious thing.

We know that ((a * b * c) modulo p = (((a * b) modulo p) * c) modulo p.

To calculate n!, we would normally start with x = 1, then multiply x by 1, 2, 3, ... n. Using the modulo formula, we calculate n! modulo p without calculating n!, by starting with x = 1, and then for i = 1, 2, 3, .., n we replace x with (x * i) modulo p.

We always have x < p and i < n, so we only need enough precision to calculate x * p, not the much higher precision to calculate n!. So to calculate n! modulo p for p ≥ 2 we take the following steps:

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. 

(Some answers mention Wilson's theorem, which only answers the question in the very special case of the example given, and is very useful to solve Euler problem #381, but in general isn't useful to solve the question that was asked).

gnasher729
quelle
-1

Dies ist meine Implementierungsanwendung des Wilson-Theorems:

Die factMOD-Funktion ist diejenige, die aufgerufen wird, um (n!)% MOD zu berechnen, wenn MOD-n gegen n klein ist.

Kennt jemand einen anderen effizienten Ansatz, wenn dies nicht der Fall ist (z. B .: n = 1e6 und 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
quelle
1
Code ist hier nicht wirklich thematisch. Eine Beschreibung des Algorithmus ist viel nützlicher, da die Benutzer nicht die Sprache verstehen müssen, in der Sie Ihren Code geschrieben haben, und weil die tatsächlichen Implementierungen häufig so optimiert sind, dass sie schwerer zu verstehen sind. Und bitte stellen Sie Ihre Fragen als separate Fragen und nicht als Antwort. Stack Exchange ist eine Frage-und-Antwort-Site, kein Diskussionsforum, und Fragen sind schwer zu finden, wenn sie in den Antworten versteckt sind. Vielen Dank!
David Richerby