How well can we do with this variable assignment problem? Given in this problem is a set of values $0 \le c_{a,b} &lt; n$, where $0 \le a &lt; n$ and $0 \le b &lt; n$.

The problem is to find the following sum as quickly as possible:

$$\sum_{a,b}{c_{a,b}x^a y^b} \bmod n$$

Here $x$ and $y$ are also assumed to be integers modulo $n$.

I'd like to know what the best method/approach is to solving this problem, and what kinds of worst-case behavior we can expect to get the sum.

Are there any similar problems whose solutions may help with this?

SOME NAIVE IDEAS

There are $n^2$ different constants and only $n$ different possible assignments for each $c_{a,b}$, so it seems that grouping some of the coefficients together is the best way to go.  However, beyond simple ideas, I'm not sure what will work best.  I'm hoping I can get some good suggestions.

MOTIVATION

My motivation for tackling this particular problem is that its solution may help improve the bounds of #3-SAT by some small degree.  However, the relation between the two is fairly complicated.
Assuming that the $c_{a,b}$ values appears in a nicely ordered way, you can use Horner's rule to evaluate the polynomial in $O(n^2)$ arithmetic operations. As mentioned by frogeyedpeas, you can't expect beating $n^2$ because it is the size of the input.

Note that if you are interested by the number of bit operations then you need to multiply this by the elementary cost of multiplication (for numbers of the size considered in your problem).

It you want to beat the $n^2$ bound, you need the $c_{a,b}$ to be represented in a more compact/structured way.