37
$\begingroup$

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

$\endgroup$
9

3 Answers 3

Reset to default
64
$\begingroup$

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

$\endgroup$
6
  • 6
    $\begingroup$ This is awesome. $\endgroup$
    – gt6989b
    Jul 17, 2013 at 22:18
  • 6
    $\begingroup$ 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. $\endgroup$
    – Ben Millwood
    Jul 17, 2013 at 22:28
  • $\begingroup$ 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.) $\endgroup$
    – Steven Stadnicki
    Jul 17, 2013 at 22:44
  • 1
    $\begingroup$ do you think you could possibly expand on why this works a bit for people (me) who don't see it right away? $\endgroup$
    – Tim
    Jul 18, 2013 at 0:15
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Jack M
    Jul 18, 2013 at 0:47
18
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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$? $\endgroup$
    – gt6989b
    Jan 23, 2015 at 20:01
  • 5
    $\begingroup$ @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. $\endgroup$
    – Peter Woolfitt
    Jan 23, 2015 at 20:05
  • $\begingroup$ I see the idea. But how would one practically determine the coefficients given the value on the output, especially in a computerized setting? $\endgroup$
    – gt6989b
    Jan 23, 2015 at 20:12
  • $\begingroup$ 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. $\endgroup$
    – Peter Woolfitt
    Jan 23, 2015 at 21:16
  • 2
    $\begingroup$ :-) A hi from one theoretician to another -- in theory beautiful but practically absolutely useless :-) +1 $\endgroup$
    – gt6989b
    Jan 26, 2015 at 20:35
0
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Steven Stadnicki
    Jul 17, 2013 at 23:40
  • 3
    $\begingroup$ 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 ... $\endgroup$
    – Hagen von Eitzen
    Jul 18, 2013 at 16:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .