# Quickest way to determine a polynomial with positive integer coefficients

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.)

-
Must $x$ be a positive integer? May I feed $x=0$? $x=-1$? $x=\sqrt 2$? $x=\pi$? –  Hagen von Eitzen Jul 17 '13 at 21:55
@HagenvonEitzen I assume you can feed any $x$ of your choice –  gt6989b Jul 17 '13 at 22:17
This question also appears in a post by Gjergji Zaimi in this thread (and is answered there in the comments). –  Mike F Sep 5 '13 at 3:22

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

-
This is awesome. –  gt6989b Jul 17 '13 at 22:18
Instinctively I felt this couldn't work, because you're only getting two values from $p$, and in general there will be lots of polynomials that go through those two points. But you're fine, because crucially the argument of the second query depends on the result of the first. –  Ben Millwood Jul 17 '13 at 22:28
Also, all the work can be done in time polynomial in the degree $d$ and maximum coefficient $H$, using numbers of size no more than roughly $O(d(\lg d+\lg H))$ bits give or take. ($m$ in Hagen's algorithm is of size $\approx O(dH)$ , and so $M$ will be of size $O(Hm^d)$, which has $\lg M\approx d\lg m+\lg H = d(\lg d+\lg H)+\lg H$ bits.) –  Steven Stadnicki Jul 17 '13 at 22:44
do you think you could possibly expand on why this works a bit for people (me) who don't see it right away? –  Tim Jul 18 '13 at 0:15
@Tim Given any two natural numbers $N$ and $b$, there is a unique base-$b$ expression equaling $N$. In other words, there is a unique polynomial $p$ with natural coefficients $\leq b$ such that $p(b) = N$. –  Jack M Jul 18 '13 at 0:47

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}$$

1. done = false; $m = 0$; % initialization
2. while(~done) {
3. $x[m] = {\rm prng}(1)$; % prng is a random number generator
4. $y[m] = p(x[m])$; % get result from the black box
5. $poly = {\rm polySolver}(x,y,m)$; % determine coefs as $poly=[a_0,a_1,\cdots,a_m]$
6. if ($poly[m] == 0$) { % exit condition
7. done = true;}
8. else {
9. $m++$;}
10. }

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.

-
That you need that many queries in the case where coefficients are arbitrary reals (and don't you mean $m+1$ queries?) doesn't speak to the specific case of positive integer coefficients asked by the questioner. –  Steven Stadnicki Jul 17 '13 at 23:40
The degree is of the polynomial unknown. Without further condition on the coefficients (such as here: nonnegative integers) your emthod never knows when it is done ... –  Hagen von Eitzen Jul 18 '13 at 16:14