Any method to solve this system of equation?

Question

We have m variables $ x_{1},x_{2},...,x_{m} $ which are elements of field $F_{p}$ and we are given m equations of the form

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

Can anyone give me some hint how to go about solving this system?

Answer 1

Because any permutation of a solution is also a solution, I would try to determine the values of the elementary symmetric polynomials of the $x_i$s. Those are the coefficients $e_i$ of the polynomial $$p(T)=\prod_{i=1}^{m}(T-x_i)=T^{m}+\sum_{i=1}^{m}(-1)^ie_iT^{m-i}.$$ The connection between the $e_i$s and the power sums $c_n$ is given by the Newton-(Girard) identities.

Caveats:

1. If $p\le m$, then Newton won't do all of it, because using the identities would involve division by $p$, but $p=0$ in $\Bbb{F}_p$.
2. You only get the polynomial $p(T)$ out of this. You need another method for finding the zeros of $p(T)$ in $\Bbb{F}_p$. This is to some extent unavoidable - again because you can permute the $x_i$s at leisure. Successfully finding $p(T)$ and its thirty zeros gives you up to $m!$ solutions (should the $x_i$s all be distinct) for the system!

There will be trouble unless $p>m$. This is apparent already in the equation $$ \sum_i x_i^p=\left(\sum_i x_i\right)^p. $$ So unless $c_p=c_1^p$ there will be no solutions.