Determinant modulo m

Jakie są znane skuteczne algorytmy do obliczania wyznacznikiem macierzy współczynników całkowitą o $\mathbb{Z}_m$ , pierścień reszt modulo $m$ . Liczba $m$ może nie być liczbą pierwszą, lecz złożoną (więc obliczenia są wykonywane w pierścieniu, a nie w polu).

O ile mi wiadomo (czytaj poniżej), większość algorytmów jest modyfikacjami eliminacji Gaussa. Pytanie dotyczy wydajności obliczeniowej tych procedur.

Jeśli zdarzyło się, że istnieje jakieś inne podejście, jestem również ciekawy.

Z góry dziękuję.

Aktualizacja:

Pozwól, że wyjaśnię źródło tego pytania. Załóżmy, że $m$ jest liczbą pierwszą. Więc $\mathbb{Z}_m$ jest polem. W tym przypadku możemy wykonać wszystkie obliczenia przy użyciu liczb mniejszych niż $m$ , więc mamy pewną górną granicę dla wszystkich operacji na liczbach: dodawanie, mnożenie i inwersja --- wszystkie potrzebne operacje, aby uruchomić eliminację Gaussa.

Z drugiej strony nie możemy wykonać inwersję dla niektórych numerów w przypadku $m$ nie na sile. Potrzebujemy więc kilku sztuczek, aby obliczyć wyznacznik.

A teraz jestem ciekawy, jakie są znane sztuczki do wykonania tej pracy i czy można je znaleźć w książkach.

Jeśli znasz faktoryzacji można obliczyć modulo każdy p e ja i oddzielnie, a następnie połączyć wyniki przy użyciu chińskiego remaindering. Jeśli e i = 1 , to obliczenie modułu p e i i jest łatwe, ponieważ jest to pole. W przypadku większych e i można użyć podnoszenia Hensel. $m = p_1^{e_1} \cdots p_n^{e_n}$$p_i^{e_i}$$e_i = 1$$p_i^{e_i}$$e_i$

Istnieje algorytm kombinatoryczny Mahajana i Vinaya, który działa na pierścieniach komutacyjnych: http://cjtcs.cs.uchicago.edu/articles/1997/5/contents.html

Aby rozwiązać ten problem istnieje szybki algorytm deterministyczny na podstawie Smith normalnych form , których najgorszym przypadku złożoność jest górna ograniczona przez koszt mnożenia macierzy-w ciągu liczb całkowitych modulo . Dla dowolnej macierzy A algorytm generuje swoją normalną postać Smitha, z której można łatwo obliczyć det ( A ) .$m$$A$$\text{det}(A)$

Mówiąc konkretniej, zdefiniuj , aby dwie macierze n × n o współczynnikach wziętych z Z m można było pomnożyć za pomocą podstawowych operacji arytmetycznych O ( n ω ) na Z m (dodawanie liczb całkowitych, mnożenie, potęgowanie itp.). Następnie,$\omega$$n \times n$$\mathbb{Z}_m$$O(n^{\omega})$$\mathbb{Z}_m$

Biorąc pod uwagę macierz , istnieje algorytm deterministyczny, który oblicza det ( A ) przy użyciu O ( n ω ) podstawowych operacji arytmetycznych na Z m [1] .$A\in \mathbb{Z}_m^{n \times n}$$\text{det}(A)$$O(n^{\omega})$$\mathbb{Z}_m$

Kiedy napisano to w 1996 r., Nie było asymptotycznie szybszej alternatywy (w artykule wspomniano o wcześniejszym istnieniu algorytmów o tym samym wiązaniu, ale nie wiem, które z nich, czy są one probabilistyczne).

Aktualizacja (17 lipca 2013 r.): Miłą zaletą tego algorytmu jest to, że działa on w czasie wielomianowym dla dowolnego złożonego nie znając faktoryzacji liczby pierwszorzędowej m ! Jest to dobre, ponieważ nie istnieją znane wydajne (klasyczne) algorytmy faktoringu (oczywiście, jeśli masz komputer kwantowy, możesz zastosować algorytm Shora ). Jeśli zrobić mają wtedy algorytm faktoryzacji Markus zasugerował wydaje sposób prostsze do wykonania.$m$$m$

Uwagi: w artykule złożoność „podstawowych operacji arytmetycznych” wynosi jeśli używasz standardowej arytmetyki liczb całkowitych, ale możesz osiągnąć O ( M ( log m ) log log m ) za pomocą szybszych technik. M ( t ) ogranicza koszt pomnożenia dwóch liczb całkowitych t- bitowych. Obecny rekord dla ω wynosi 2,3727 .$O(\log^2 m)$$O(M(\log m)\log \log m)$$M(t)$$t$$\omega$