Apa cara paling efisien untuk menghitung faktorial modulo prima?

Apakah Anda tahu algoritma yang menghitung faktorial setelah modulus secara efisien?

Misalnya, saya ingin memprogram:

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

Tetapi, padalah angka besar (prima) untuk menerapkan faktorial secara langsung .$(p \leq 10^ 8)$

Dengan Python, tugas ini sangat mudah, tetapi saya benar-benar ingin tahu cara mengoptimalkan.

(Jawaban ini awalnya diposting oleh penanya jonaprieto di dalam pertanyaan.)

Saya ingat teorema Wilson , dan saya memperhatikan hal-hal kecil:

Dalam program di atas, lebih baik jika saya menulis:

$$\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}$$

Dan Anda dapat menemukan karena , jadi dengan algoritma Euclidian yang diperluas, Anda dapat menemukan nilai , yaitu modulus kebalikan. gcd ( p , p - i ) = 1 ( p - i ) - $(p-i)^{-1}$$\operatorname{gcd}(p, p-i) = 1$$(p-i)^{-1}$

Anda juga dapat melihat kongruensi yang sama, seperti: jadi, jumlahnya sama: dan jika Anda membuat faktor pada awalnya faktorial Anda mendapatkan Dan, voila, invers modulus lebih efisien daripada faktorial. (-24)-1+(6)-1+(-

$$\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$$

Contoh yang Anda posting sangat terkait dengan masalah Euler # 381. Jadi saya akan mengirim jawaban yang tidak memecahkan masalah Euler. Saya akan memposting bagaimana Anda dapat menghitung faktorial modulo prima.

Jadi: Bagaimana cara menghitung n! modulo p?

Pengamatan cepat: Jika n ≥ p, maka n! memiliki faktor p, jadi hasilnya 0. Sangat cepat. Dan jika kita mengabaikan persyaratan bahwa p harus menjadi prima maka biarkan q menjadi faktor prima terkecil dari p, dan n! modulo p adalah 0 jika n ≥ q. Tidak ada banyak alasan untuk meminta p sebagai jawaban utama untuk menjawab pertanyaan Anda.

Sekarang dalam contoh Anda (n - i)! untuk 1 ≤ i ≤ 5 muncul. Anda tidak harus menghitung lima faktorial: Anda menghitung (n - 5) !, dikalikan dengan (n - 4), dapatkan (n - 4)!, Kalikan dengan (n - 3) untuk mendapatkan (n - 3)! dll. Ini mengurangi pekerjaan hampir faktor 5. Jangan memecahkan masalah secara harfiah.

Pertanyaannya adalah bagaimana cara menghitung n! modulo m. Cara yang jelas adalah menghitung n !, suatu angka dengan kira-kira n log dan angka desimal, dan menghitung modulo p sisanya. Itu kerja keras. Pertanyaan: Bagaimana kita bisa mendapatkan hasil ini lebih cepat? Dengan tidak melakukan hal yang jelas.

Kita tahu bahwa ((a * b * c) modulo p = (((a * b) modulo p) * c) modulo p.

Untuk menghitung n !, kita biasanya mulai dengan x = 1, lalu kalikan x dengan 1, 2, 3, ... n. Menggunakan rumus modulo, kami menghitung n! modulo p tanpa menghitung n !, dengan memulai dengan x = 1, dan kemudian untuk i = 1, 2, 3, .., n kita ganti x dengan (x * i) modulo p.

Kami selalu memiliki x <p dan i <n, jadi kami hanya membutuhkan cukup presisi untuk menghitung x * p, bukan presisi yang jauh lebih tinggi untuk menghitung n !. Jadi untuk menghitung n! modulo p untuk p ≥ 2 kita mengambil langkah-langkah berikut:

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. 

(Beberapa jawaban menyebutkan teorema Wilson, yang hanya menjawab pertanyaan dalam kasus yang sangat khusus dari contoh yang diberikan, dan sangat berguna untuk menyelesaikan masalah Euler # 381, tetapi secara umum tidak berguna untuk menyelesaikan pertanyaan yang diajukan).

Ini adalah implementasi penerapan teorema wilson saya:

Fungsi factMOD adalah fungsi untuk memanggil untuk menghitung (n!)% MOD ketika MOD-n sedikit terhadap n.

Apakah ada yang tahu pendekatan efisien lain ketika itu tidak terjadi (mis: n = 1e6 dan 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;
}