Trova un polinomio in due o tre domande

Question

Black Box di $ f (x) $ significa che posso valutare il polinomio $ f (x) $ in qualsiasi momento.

• Ingresso: Una scatola nera di polinomio monico $ f (x) in mathbb {z}^+[x] $ di grado $ d $.

• Produzione: I coefficienti $ D $ di Polinomio $ F (x) $.

Il mio algoritmo: permettere

$$ f (x) = x^{d} + a_ {d-1} x^{d-1} + CDOTS + A_1 X + A_0 $$

Valuta il polinomio $ mathcal {f (x)} $ a $ d $ molti punti usando la scatola nera e ottieni un sistema di equazioni lineari. Ora posso risolvere il sistema di equazioni lineari per ottenere i coefficienti desiderati.

Tuttavia, in questo caso, ho bisogno di $ mathcal {o (d)} $ molte domande sulla scatola nera. voglio ridurre al minimo il numero di domande. Esiste un modo per ridurre il numero di domande a solo due o tre?