Invers Modular melalui Fermat

Penambahan, penolakan dan pendaraban berfungsi dengan baik di bawah modulo, tetapi pembahagian biasa tidak. Anda tidak boleh membahagi begitu sahaja lalu mengambil baki. ⚠️

Penyelesaiannya ialah invers modulo: pembahagian dengan x menjadi pendaraban dengan invers x. Jadi, a / b modulo m bertukar menjadi a didarab dengan invers b.

Invers bagi x ialah nombor yang menghasilkan 1 apabila didarab dengan x di bawah modulo. Invers memainkan peranan 1/x dalam aritmetik biasa.

Invers wujud hanya apabila x tidak mempunyai faktor sepunya dengan m. Menggunakan modulo nombor perdana seperti 1e9+7 menjamin setiap x bukan sifar mempunyai invers.

Teorem kecil Fermat menyatakan bahawa bagi nombor perdana p, x berpangkat p tolak 1 adalah kongruen dengan 1, selagi x bukan gandaan p.

Asingkan satu faktor x, maka baki mestilah inversnya. Jadi, invers bagi x ialah x yang dinaikkan kepada kuasa p tolak 2, kemudian diambil modulo p.

Eksponen itu sangat besar, jadi gunakan pemangkatan pantas daripada pelajaran sebelumnya. Dalam Python, satu panggilan kepada pow melakukan semuanya untuk Anda.

Untuk mengira a dibahagi b di bawah modulo, darabkan a dengan invers bagi b. Bakinya tepat sama dengan hasil bahagi sebenar modulo p.

Tiada invers bagi 0 kerana tiada apa-apa yang didarab dengan sifar menghasilkan satu. Elakkan pembahagian dengan nilai yang menjadi sifar di bawah modulo.

Setiap invers Fermat ialah satu pemangkatan pantas, jadi kosnya ialah masa O(log p). Ini murah untuk beberapa pembahagian, tetapi terkumpul jika Anda melakukan berjuta-juta pembahagian.

Apabila Anda memerlukan banyak invers, kira terlebih dahulu semuanya dengan satu laluan linear yang bijak, bukannya menggunakan pow bagi setiap elemen. Anda akan bergantung pada teknik ini untuk nCr seterusnya.

Sekarang Anda boleh melakukan pembahagian di bawah modulo nombor perdana dengan mendarab menggunakan invers modulo, yang diperoleh sebagai x berpangkat p tolak 2 melalui pow. Jangan sesekali mencari invers bagi sifar. ✅