 Quote by AKG
Or maybe a better one to do is this: first evaluate p(1), that's the sum of all the coefficients. Then pick a prime P > p(1), and evaluate p(P). Then if you consider p(P) mod P², p(P) mod P³, ..., p(P) mod Pd or something you can recover the coefficients.
|
That's essentially it, but there's still some extra math required if you pick a prime. Instead, let [tex]n=\lceil \log_{10} p(1) \rceil[/tex]. Then evaluate [tex]p(10^n)[/tex]. The k-th coefficient can be recovered by simply reading off the k-th block of n digits.
Example:
p(x) = 99 x^2 + 23.
p(1) = 99+23 = 122.
n = 3
p(1000) = 99 (1000)^2 + 23 = 099, 000, 023