## Determining a polynomial

Let $p$ be a polnyomial with natural coefficients. An oracle can evaluate $p$ at any value you like. Can you determine all the coefficients by making two queries to the oracle?

Note: You are free to have an adaptive strategy, in that the second query can depend on the answer to the first.

Let the polynomial be $P(x) = \sum_i a_i x^i$. First evaluate $P(1)$, this would give you $q=\sum_i a_i$. Now evaluate $P(q)=\sum_i a_i q^i$, since each $a_i < q$ the number $a_n,\dots,a_0$ is a valid base $q$ number. Hence convert the number $P(q)$ into base $q$ format to recover the coefficients. I learned about this trick from a blog post of John D. Cook on the same topic.

compute p(1) and then p(p(1)+1)

0

0

0

0

0

0

0

0

0

0