**Problem: **Alice chooses a secret polynomial $latex p(x)$ with nonnegative integer coefficients. Bob wants to discover this polynomial by querying Alice for the value of $latex p(x)$ for some integer $latex x$ of Bob’s choice. What is the minimal number of queries Bob needs to determine $latex p(x)$ exactly?

**Solution: **Two queries. The first is $latex p(1)$, and if we call $latex N = p(1) + 1$, then the second query is $latex p(N)$.

To someone who is familiar with polynomials, this may seem shocking, and I’ll explain why it works in a second. After all, it’s very easy to prove that if Bob gives Alice all of his queries at the same time (if the queries are not *adaptive*), then it’s impossible to discover what $latex p(x)$ is using fewer than $latex textup{deg}(p) + 1$ queries. This is due to a fact called *polynomial interpolation*, which we’ve seen on this blog before…

View original post 351 more words