Example: How to guess polynomial $p$ if you know $p(2) = 11$ ? It is simple: just write 11 in binary format: 1011 and it gives coefficients: $p(x) = x^3+x+1$ . Well, of course, polynomial is not unique, because $2x^k$ and $x^{k+1}$ give the same value at p=2, so for example $2x^2+x+1, 4x+x+1$ also satisfy the condition, but their coefficients have greater absolute values !

Question 1: Assume we want to find $q(x)$ with integer coefficients, given its values at some set of primes $q(p_i)=y_i$ such that $q(x)$ has least possible coefficients . How should we do it ? Any suggestion/algorithm/software are welcome. (Least coefs means - least maximum of modules of coefficients).

Question 2: Can one help to guess the polynomial $p$ such that $p(3) = 221157, p(5) = 31511625$ with least possible integer coefficients ? (Least maximum of modules of coefficients). Does it exist ?

(Degree of polynom seems to be 10 or 11, it seems divisible by $x^3$, I have run a brute force search bounding absolute values of coefficients by 3, but no polynom satisfying conditions found, so I will increase bound on coefficients and will run search again, but execution time grows too fast with bound increase and it might be brute force is not a good choice).

Question 3: Does conditions like $q(p_i)=y_i $ imply some bounds on coefficients ? E.g. can we estimate that coefficients are higher that some bound ?