# 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$? Commented Jul 17, 2013 at 21:55
• @HagenvonEitzen I assume you can feed any $x$ of your choice Commented Jul 17, 2013 at 22:17
• This question also appears in a post by Gjergji Zaimi in this thread (and is answered there in the comments). Commented Sep 5, 2013 at 3:22
• Commented Aug 23, 2016 at 13:56
• Commented Nov 23, 2018 at 20:50

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. Commented Jul 17, 2013 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. Commented Jul 17, 2013 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.) Commented Jul 17, 2013 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
Commented Jul 18, 2013 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$. Commented Jul 18, 2013 at 0:47

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.

• I don't understand. Suppose you call the function and you now know $f(\pi) = 0$. What does that tell you about the coefficients or the degree of $f$? Commented Jan 23, 2015 at 20:01
• @gt6989b It tells you that $f$ must be the $0$ polynomial. This is in fact the perfect example to illustrate the point. Since $\pi$ is transcendental, it is not a root of any nonzero polynomial with integer coefficients. Commented Jan 23, 2015 at 20:05
• I see the idea. But how would one practically determine the coefficients given the value on the output, especially in a computerized setting? Commented Jan 23, 2015 at 20:12
• Well, actually computing this would be very difficult, but the point is that all the information of a polynomial with integer coefficients is contained in this output - if you guess the correct answer, you can certainly verify it. Commented Jan 23, 2015 at 21:16
• :-) A hi from one theoretician to another -- in theory beautiful but practically absolutely useless :-) +1 Commented Jan 26, 2015 at 20:35

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.

• 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. Commented Jul 17, 2013 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 ... Commented Jul 18, 2013 at 16:14