Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
1  
I'm not sure I understand correctly. If we can choose everything except $n$ freely, why can't we just choose $c_k=v=w=0$? – joriki Apr 12 '11 at 23:24
    
Oops, sorry - that's the trivial case. I'll edit the question... – Matt Groff Apr 12 '11 at 23:27
    
According to my calculations, the total number of satisfying assignments is 1,725 for $n=2, p=5$ and 7,273 for $n=2, p=7$ and 55,341 for $n=2,p=11$. The amount of satisfying assignments should grow exponentially with $n$. – Matt Groff Apr 12 '11 at 23:42
    
I thought I saw a linear algebra method to solving equations like these, outside of modular arithmetic. A similar method would have columns for each $c_k v_j$ over the "domain" of $k$ and $j$, which I tried, but I can't quite get the variables to work in this solution. It would give plenty of freedom in the form of parameters, but I still don't know how to deal with the powers. – Matt Groff Apr 12 '11 at 23:58
    
Do you mean this? en.wikipedia.org/wiki/Vandermonde_matrix – joriki Apr 13 '11 at 0:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.