Modul penentu m

Apa algoritma efisien dikenal untuk menghitung penentu matriks bilangan bulat dengan koefisien dalam $\mathbb{Z}_m$ , cincin residu modulo $m$ . Angka $m$ mungkin bukan prima tetapi komposit (jadi perhitungan dilakukan dalam cincin, bukan bidang).

Sejauh yang saya tahu (baca di bawah), kebanyakan algoritma adalah modifikasi dari eliminasi Gaussian. Pertanyaannya adalah tentang efisiensi komputasi dari prosedur ini.

Jika kebetulan ada beberapa pendekatan yang berbeda, saya juga ingin tahu tentang itu.

Terima kasih sebelumnya.

Memperbarui:

Izinkan saya menjelaskan sumber pertanyaan ini. Asumsikan, $m$ adalah bilangan prima. Jadi $\mathbb{Z}_m$ adalah sebuah bidang. Dan dalam hal ini kita dapat melakukan semua perhitungan menggunakan angka kurang dari $m$ , jadi kami memiliki batas atas semua operasi pada angka: penambahan, perkalian dan inversi --- semua operasi yang diperlukan untuk menjalankan eliminasi Gaussian.

Di sisi lain kita tidak dapat melakukan inversi untuk beberapa angka jika $m$ bukan prima. Jadi kita perlu beberapa trik untuk menghitung determinan.

Dan sekarang saya ingin tahu trik apa yang diketahui untuk melakukan pekerjaan itu dan apakah trik tersebut dapat ditemukan di dalam dan di kertas-kertas buku.

Jika Anda mengetahui faktorisasi Anda dapat menghitung modulo setiap p e i i secara terpisah dan kemudian menggabungkan hasil menggunakan remaindering Cina. Jika e i = 1 , maka menghitung modulo p e i i mudah, karena ini adalah bidang. Untuk yang lebih besar e i , Anda dapat menggunakan Hensel angkat. $m = p_1^{e_1} \cdots p_n^{e_n}$$p_i^{e_i}$$e_i = 1$$p_i^{e_i}$$e_i$

Ada algoritma kombinatorial oleh Mahajan dan Vinay yang bekerja di atas cincin komutatif: http://cjtcs.cs.uchicago.edu/articles/1997/5/contents.html

Untuk mengatasi masalah ini ada algoritma deterministik cepat berdasarkan pada bentuk normal Smith yang kompleksitas kasus terburuknya dibatasi oleh biaya perkalian-matriks atas bilangan bulat modulo . Untuk setiap matriks A , algoritma mengeluarkan bentuk normal Smith, dari mana det ( A ) dapat dengan mudah dihitung.$m$$A$$\text{det}(A)$

Lebih konkret, mendefinisikan sehingga dua n × n matriks dengan koefisien diambil dari Z m dapat dikalikan dengan menggunakan O ( n ω ) dasar operasi aritmatika pada Z m (selain integer, perkalian, eksponensial, dll). Kemudian,$\omega$$n \times n$$\mathbb{Z}_m$$O(n^{\omega})$$\mathbb{Z}_m$

Diberikan matriks , terdapat algoritma deterministik yang menghitung det ( A ) menggunakan operasi aritmetika dasar O ( n ω ) selama Z$A\in \mathbb{Z}_m^{n \times n}$$\text{det}(A)$$O(n^{\omega})$$\mathbb{Z}_m$ [1] .

Ketika ini ditulis pada tahun 1996, tidak ada alternatif yang lebih cepat tanpa asimptotis (makalah ini menyebutkan keberadaan algoritma dengan ikatan yang sama tetapi saya tidak tahu yang mana, atau apakah mereka probabilistik).

Pembaruan (17 Juli 2013): fitur bonus yang bagus dari algoritma ini adalah bahwa ia berjalan dalam waktu polinomial untuk m komposit sewenang-wenang tanpa mengetahui faktorisasi prime-nuber dari m ! Ini bagus karena tidak ada algoritma efisien (klasik) yang diketahui untuk memfaktorkan (tentu saja, jika Anda memiliki komputer kuantum, maka Anda dapat menerapkan algoritma Shor ). Jika kamu$m$$m$ memang memiliki faktorisasi maka algoritma yang disarankan Markus tampaknya lebih mudah untuk diterapkan.

Catatan: dalam makalah, kompleksitas "operasi aritmatika dasar" adalah jika Anda menggunakan aritmatika integer standar, tetapi Anda dapat mencapai O ( M ( log m ) log log m ) dengan teknik yang lebih cepat. M ( t ) membatasi biaya untuk mengalikan dua bilangan bulat t- bit. Catatan saat ini untuk ω adalah 2.3727 .$O(\log^2 m)$$O(M(\log m)\log \log m)$$M(t)$$t$$\omega$