Black box of $f(x)$ means I can evaluate the polynomial $f(x)$ at any point.

  • Input: A black box of monic polynomial $f(x) \in\mathbb{Z}^+[x]$ of degree $d$.

  • Output: The $d$ coefficients of polynomial $f(x)$.

My algorithm: let

$$f(x) = x^{d} + a_{d-1} x^{d-1} + \cdots + a_1 x + a_0$$

Evaluate polynomial $\mathcal{f(x)}$ at $d$ many points using the black box and get a system of linear equations. Now I can solve the system of linear equations to get the desired coefficients.

However, in this case, I need $\mathcal{O(d)}$ many queries to the black box. I want to minimize the number of queries. Is there any way to reduce the number of queries to just two or three?

  • 2
    $\begingroup$ You keep changing the question. Perhaps you should first decide on your question and only then ask it. Otherwise it can be somewhat frustrating for the answerer. $\endgroup$ Oct 13, 2017 at 12:40
  • 2
    $\begingroup$ What does $\mathbb{Z}^+$ means? $\endgroup$
    – md5
    Oct 13, 2017 at 12:44
  • 1
    $\begingroup$ set of positive integers $\endgroup$
    – Complexity
    Oct 13, 2017 at 12:45
  • 1
    $\begingroup$ BTW for your algorithm, the coefficients can be computed in $O(n^2)$ instead of $O(n^3)$ with Lagrange's closed formula. $\endgroup$
    – md5
    Oct 13, 2017 at 12:49
  • 2
    $\begingroup$ Exact same question, worded differently: math.stackexchange.com/questions/446130/… $\endgroup$
    – Nayuki
    Oct 14, 2017 at 0:38

1 Answer 1


You can determine the polynomial using two queries. First query the polynomial at $x=1$ to get an upper bound $M$ on the value of the coefficients. Now query the polynomial at $x > M$ of your choice and read off the coefficients from the base $x$ expansion.

Curiously, if you allow the coefficients to be negative then you cannot do better than $d$ queries. Indeed, I can always answer your $d-1$ queries $x_1,\ldots,x_{d-1}$ by zero, and this does not fix the value of the polynomial since all polynomials of the form $(x-x_1)\cdots(x-x_{d-1})(x-x_d)$ are consistent with my answers.

  • $\begingroup$ For negatives I think 2's complement kind of trick may work. $\endgroup$
    – Complexity
    Oct 13, 2017 at 12:48
  • 4
    $\begingroup$ Not without an upper bound on the magnitude of the coefficients. This is what my proof shows. $\endgroup$ Oct 13, 2017 at 12:49
  • $\begingroup$ Sorry I did not get this part " I can always answer your $d-1$ queries $x_1,\ldots,x_{d-1}$ by zero " $\endgroup$
    – Complexity
    Oct 13, 2017 at 13:09
  • 6
    $\begingroup$ This is an adversary argument. Your algorithm asks the black box for the value of $f$ at $d-1$ places, and it always answers zero. I show that this is not enough for you to deduce the value of $f$. $\endgroup$ Oct 13, 2017 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.