Apa cara paling efisien untuk menghitung faktorial modulo prima?

20

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

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

Jonaprieto
sumber
6
Sepertinya masalahnya ingin Anda menggunakan teorema Wilson. Untuk prime , (p-1)! = -1 \ mod p . Jadi tanpa menggunakan bahasa pemrograman apa pun: jawabannya adalah 100 . Mungkin Anda ingin menggeneralisasi masalah Anda? p100(p1)!=1modp100
Aryabhata
5
Bisakah Anda menyatakan masalahnya dengan lebih jelas? Apakah Anda ingin menghitung (X!) (mod (X+1)), atau lebih umum (X!) (mod Y)? Dan saya kira itu factorial(100!)tidak berarti Anda ingin menerapkan fungsi faktorial dua kali.
Keith Thompson
1
Bahkan jika Anda tidak memiliki teorema Wilson, Anda memiliki itu (mn)modp=(mmodp)(nmodp) , yang setidaknya akan membantu menghindari masalah overflow.
Dave Clarke
8
Perhatikan bahwa Teorema Wilson hanya berlaku ketika p prima. Pertanyaan Anda tidak menyatakan bahwa p adalah prima, jadi apa yang Anda tulis tidak benar.
Dave Clarke

Jawaban:

11

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

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

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 ) - 1(pi)1gcd(p,pi)=1(pi)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+(-2

(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
sumber
Jadi pada dasarnya . Rapi! (pk)!(p+(k1)!(1)k)1(modp)
Thomas Ahle
Maaf tetapi ketika saya memfaktisasi , saya mendapatkan:(24)1+61+(2)1
9(24)1=38
1

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

gnasher729
sumber
-1

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;
}
JeanClaudeDaudin
sumber
1
Kode tidak benar-benar sesuai topik, di sini. Deskripsi algoritma jauh lebih berguna karena tidak mengharuskan orang untuk memahami bahasa apa pun yang Anda putuskan untuk menulis kode Anda, dan karena implementasi yang sebenarnya sering dioptimalkan dengan cara yang membuat mereka lebih sulit untuk dipahami. Dan tolong ajukan pertanyaan Anda sebagai pertanyaan terpisah, bukan di jawaban Anda. Stack Exchange adalah situs tanya jawab, bukan papan diskusi, dan pertanyaan sulit ditemukan jika disembunyikan di antara jawaban. Terima kasih!
David Richerby