2
$\begingroup$

This is for an algorithm I'm working on. Perhaps we can work together!

We can consider the integers modulo a prime $p$. They form a field with arithmetic operations modulo $p$. I'd like to find the variables that satisfy the $n$ equations ($n < p$) of the form:

$\left(\displaystyle\sum_{k=0}^{n-1}{c_k(z_k)^m}\right)\equiv v + m w \bmod{p}$

for each $m$ such that $0\le m < n$. Here $c_k$, $z_k$, $v$, $m$ and $w$ are all integers, but $v$, $w$ and $m$ must be nonzero. Only $n$ is given; we're free to assign variables as we like, with $v$, $w$, and $m$ the slight exceptions. Hopefully this simplifies the problem.

What's the quickest way to solve this problem?

AN EASIER VARIATION

I'd be happy for a quick solution to this easier variation instead. The problem is to find solutions to the modified equation where the sum is taken for $N$ $c_k$s and $z_k$s where $N > n-1$:

$\left(\displaystyle\sum_{k=0}^{N}{c_k(z_k)^m}\right)\equiv v + m w \bmod{p}$

In this variation, there are more variables for the same equivalence, and so it is (much) less constrained.

Any help or suggestions are very much appreciated.

  • 0
    That's similar to what I was thinking of. I think I'm making progress by using columns for only the $c_k$'s and for the righthand side. Here I've really expanded the righthand side of the equivalence; I have a column for $v\cdot p$, $v$, then $v_1\cdot p$, $v_1$, $v_2\cdot p$, $v_2$,... The $v_i$'s are really there to seperate each equation and to make sure that they can easily be worked modulo $p$. This seems to be working well...2011-04-13

0 Answers 0