Suppose that you are given a polynomial $p(x)$ as a black box (i.e. some oracle, to which you feed $x$ and it returns $p(x)$). It is known that the coefficients of $p(x)$ are all positive integers. How do you determine what $p(x)$ is in the quickest way possible?
(There are 2 metrics for quickness: the number of calls to the oracle and total number of operations. The relationship between the two is not given so we try to minimize both.)
Ask for $m=p(1)$. Then all coefficients of $p$ are $\le m$. Ask for $M=p(m+1)$. Expand $M$ in base $m+1$, done. - That's two oracle queries and $\deg p$ integer div/mod operations
Only $1$ input is needed to determine the polynomial: $\pi$. Since $\pi$ is transcendental, in principle we can figure out the polynomial from $f(\pi)$ (in a loose sense, none of the powers of $\pi$ can run into each other).
Note that this also works if we get rid of the positivity constraint.
One general solution is that you need $m+2$ queries, where $m$ is the degree of the polynomial. Here is a description how you find this polynomial that $$ p(x|m) = a_0+a_1x+\cdots+a_{m}x^{m} $$
done = false; $m = 0$; % initialization
while(~done) {
$x[m] = {\rm prng}(1)$; % prng is a random number generator
$y[m] = p(x[m])$; % get result from the black box
$poly = {\rm polySolver}(x,y,m)$; % determine coefs as $poly=[a_0,a_1,\cdots,a_m]$
if ($poly[m] == 0$) { % exit condition
done = true;}
else {
$m++$;}
}
The reason why the above code works is that you only need $m$ of equations to solve $m$ unknown variables (if they are not linearly dependent). The additional query happens when you need to confirm that the last found polynomial is correct. If the new found coefficient $a_m$ for term $x^{m}$ is zero, this means that the previous found polynomial is already able to predict this new data point. Thus, we find the polynomial.
Note: with the above settings, the algorithm is able to find polynomials with real-number coefficients, including integer-numbers as a special case.
For your interest, the polynomial blackbox problem is a well known "secret sharing" scheme, that allows you share a secret (commonly referred as to the value of $a_0$ in the polynomial) among $n$ people, so that the secret cannot be revealed unless $k$ of them agree. Simply speaking, say $n=3$ and $k = 2$, you then construct a degree 9 polynomial with your secret encoded in $a_0$. You then query $p(x)$ for 15 times, and give each person 5 results. In this way, none of them can solve the secret only by him/herself, but two of them is sufficient to find the secret.
