Módulo determinante m

¿Cuáles son los algoritmos eficientes conocidos para calcular un determinante de una matriz entera con coeficientes en , el anillo de residuos módulo . El número puede no ser primo sino compuesto (por lo que los cálculos se realizan en anillo, no en un campo). m$\mathbb{Z}_m$$m$$m$

Hasta donde yo sé (lea a continuación), la mayoría de los algoritmos son modificaciones de la eliminación gaussiana. La pregunta es sobre la eficiencia computacional de estos procedimientos.

Si sucedió que hay un enfoque diferente, también tengo curiosidad al respecto.

Gracias por adelantado.

Actualizar:

Déjame explicarte la fuente de esta pregunta. Supongamos que es un número primo. Entonces es un campo. Y en este caso podemos realizar todos los cálculos utilizando números menores que , por lo que tenemos un buen límite superior en todas las operaciones en números: suma, multiplicación e inversión --- todas las operaciones necesarias para ejecutar la eliminación gaussiana.Z m$m$$\mathbb{Z}_m$$m$

Por otro lado, no podemos realizar inversiones para algunos números en caso de que no sea primo. Entonces necesitamos algunos trucos para calcular determinante.$m$

Y ahora tengo curiosidad por saber cuáles son los trucos conocidos para hacer el trabajo y si dichos trucos se pueden encontrar en documentos de libros.

Si conoce la factorización de puede calcular el módulo de cada p e i i por separado y luego combinar los resultados con el resto chino. Si e i = 1 , entonces calcular el módulo p e i i es fácil, ya que este es un campo. Para e i más grande , puede usar el levantamiento Hensel. $m = p_1^{e_1} \cdots p_n^{e_n}$$p_i^{e_i}$$e_i = 1$$p_i^{e_i}$$e_i$

Hay un algoritmo combinatorio de Mahajan y Vinay que funciona sobre anillos conmutativos: http://cjtcs.cs.uchicago.edu/articles/1997/5/contents.html

$m$$A$$\text{det}(A)$

$\omega$$n \times n$$\mathbb{Z}_m$$O(n^{\omega})$$\mathbb{Z}_m$

$A\in \mathbb{Z}_m^{n \times n}$$\text{det}(A)$$O(n^{\omega})$$\mathbb{Z}_m$

Cuando esto se escribió en 1996, no había una alternativa asintóticamente más rápida (el documento menciona la existencia previa de algoritmos con el mismo límite, pero no sé cuáles, o si son probabilísticos).

$m$$m$

$O(\log^2 m)$$O(M(\log m)\log \log m)$$M(t)$$t$$\omega$