Índice Algoritmo de cálculo solución errónea

Question

Queremos ser capaces de calcular logaritmos discretos con base $a = 89$ en $\mathbb{Z}^*_p$ para $p = 1235789.$ Elegimos la base del factor $B = {1, 2, 3, 5, 7, 11, 13, 17, 19, 23}$ . Con el primer paso del algoritmo de cálculo de índices obtengo este sistema de ecuaciones lineales.

\begin{bmatrix}0&3& 0& 2& 0& 0& 2 & 0 & 0 & 1 & 100058\\ 1&1&1&0&0&0&1&0&0&3&100131\\0&4&3&0 & 0 & 1 & 0 & 0 & 1 & 0 & 100152 \\ 1 & 6 & 3 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 100232\\ 1 &2 &3 & 0 & 1 & 2 & 1 & 0 & 0 & 0 & 100343 \\ 1 & 2 & 7 & 0 & 1 & 0 & 1 &0 & 0 & 0 & 100360\\ 1 & 5 & 2 & 1 & 2 & 0 & 0 &1 & 0 & 0 & 100385\\ 1 & 6 & 2 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 100401\\ 0 & 0 & 4 & 0 & 3 & 0 & 0 & 1 & 0 & 0 & 100412\\ 0 & 0 & 5 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 100428 \end{bmatrix}

Luego uso la eliminación de Gauss para resolver las ecuaciones.

\begin{bmatrix} 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& -494241/70\\ 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 250358/35\\ 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 250358/35\\ 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& -1749/10\\ 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 498777/35\\ 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 1000837/70\\ 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 2015443/70\\ 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1016657/35\\ 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 2504791/70\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 747756/35\\\end{bmatrix}

Tengo problemas para entender por qué mi solución de ecuaciones lineales no es correcta?

Edición: ¿Cuál es la forma correcta de utilizar la eliminación de guass con $\mod p - 1$ ?

Answer 1

Para el cálculo de índices, hay que hacer álgebra lineal mod $p - 1$ . Así que no se pueden utilizar los métodos ordinarios del álgebra lineal para los números reales, ya que cosas como la división no funcionarán correctamente.

Resulta que se puede hacer álgebra lineal en cualquier campo, porque un campo admite la suma, la resta, la multiplicación y la división (multiplicación por la inversa). Por desgracia, los enteros mod $p - 1$ no son un campo. Sólo los enteros módulo de un primo son un campo, pero $p - 1$ no es primo (a menos que $p = 3$ ). Por lo tanto, debe convertir su problema en un módulo $p - 1$ en uno o más problemas de módulo de primos.

Para ello, el factor

$$ p - 1 = \prod_{i} q_i^{e_i}, $$

donde el $q_i$ son primos y distintos. A continuación, resuelva el sistema módulo de cada uno de los $q_i$ , levantar estas soluciones a $q_i^{e_i}$ y finalmente utilizar el Teorema del Resto Chino para obtener una solución módulo $p - 1$ .