¿Algún método para resolver este sistema de ecuaciones?

Question

Tenemos m variables $ x_{1},x_{2},...,x_{m} $ que son elementos del campo $F_{p}$ y se nos dan m ecuaciones de la forma

$$\sum_{i=1}^{m} x_{i}^{n} = c_{n} \mod p \qquad for \: 1 \le n \le m$$

¿Alguien puede darme alguna pista sobre cómo resolver este sistema?

Answer 1

Dado que cualquier permutación de una solución es también una solución, intentaría determinar los valores de los polinomios simétricos elementales del $x_i$ s. Esos son los coeficientes $e_i$ del polinomio $$p(T)=\prod_{i=1}^{m}(T-x_i)=T^{m}+\sum_{i=1}^{m}(-1)^ie_iT^{m-i}.$$ La conexión entre el $e_i$ s y las sumas de potencia $c_n$ viene dado por las identidades Newton-(Girard) .

Advertencias:

1. Si $p\le m$ entonces Newton no lo hará todo, porque usar las identidades implicaría la división por $p$ pero $p=0$ en $\Bbb{F}_p$ .
2. Sólo se obtiene el polinomio $p(T)$ de esto. Necesitas otro método para encontrar los ceros de $p(T)$ en $\Bbb{F}_p$ . Esto es hasta cierto punto inevitable - de nuevo porque se puede permutar el $x_i$ s en el ocio. Encontrar con éxito $p(T)$ y sus treinta ceros te dan hasta $m!$ soluciones (en caso de que el $x_i$ ¡s sean todos distintos) para el sistema!

Habrá problemas a menos que $p>m$ . Esto es evidente ya en la ecuación $$ \sum_i x_i^p=\left(\sum_i x_i\right)^p. $$ Así que a menos que $c_p=c_1^p$ no habrá soluciones.