Finding polynomials with their values at points

If all the coefficients are non-negative integers and if we know the max of all the coefficients, then it is easy to find the coefficients with just ${one\ point}$ of choice. Let's say the max is $M$. Then evaluate the polynomial at $M+1$. The output will be equal to the decimal number system representation of a number whose base $M+1$ number has digits as the coefficients of the polynomial. So, given the output, just get the base $M+1$ representation.

So, even if have just an upper bound (can be very lose upper bound), just set that as $M$ and proceed as above.

As Gerry Myerson points out in the comments, if you do not have an upper bound, you can use $M = p(1)$. Then only two evaluations will be required to determine the coefficients.

With two points you can only uniquely determine $p(x)$ if it has degree one. In general if $p(x)$ has degree $n$, you will need the computer give $(n+1)$ outputs, each for a different input.

For example if $p(x)$ has degree 2 and you input $0$ and $1$ and get outputs $a$ and $b$ respectively, there are an infinite number of parabolas which pass through these points. Here are some:

$p(x) = (b-a)x^2+a$

$p(x) = bx^2-ax+a$

$p(x) = 2bx^2-(b+a)x+a$

$p(x) = -3ax^2+(b+2a)x+a$

No. You would a minimum of $n$ points, where $n$ is the dimension of the polynomial. For instance, let's try to find a cubic polynomial $p$ where $p(0)=0$ and $p(1)=1$. Notice that $p_1(x)=x^3-x^2+1$ and $p_2(x)=x^3-x+1$ both satisfy the given criteria.