Forma más rápida de determinar un polinomio con coeficientes enteros positivos

Question

Suponga que dado un polinomio $p(x)$ como una caja negra (es decir, oracle, a la que alimentar $x$ y vuelve $p(x)$). Es conocido que los coeficientes de $p(x)$ son todos los enteros positivos. ¿Cómo determinar cuál $p(x)$ es de la manera más rápida posible?

(Hay 2 indicadores para la rapidez: el número de llamadas a la de oracle y número total de operaciones. La relación entre los dos no se da de manera tratamos de minimizar tanto.)

Answer 1

Pida $m=p(1)$. A continuación, todos los coeficientes de $p$$\le m$. Pida $M=p(m+1)$. Expandir $M$ base $m+1$, hecho. Dos de oracle consultas y $\deg p$ entero div/mod operaciones

Answer 2

Sólo $1$ entrada es necesaria para determinar el polinomio: $\pi$. Desde $\pi$ es trascendental, en principio, podemos calcular el polinomio de $f(\pi)$ (en un sentido riguroso, ninguno de los poderes de la $\pi$ puede ejecutar en cada uno de los otros).

Tenga en cuenta que esto también funciona si nos deshacemos de la positividad de la restricción.

Answer 3

Una solución general es que usted necesita $m+2$ de las consultas, donde $m$ es el grado del polinomio. Aquí está una descripción de cómo se encuentra este polinomio que $$ p(x|m) = a_0+a_1x+\cdots+a_{m}x^{m} $$

1. hecho = false; $m = 0$; % inicialización
2. mientras que(~done) {
3. $x[m] = {\rm prng}(1)$; % prng es un generador de números aleatorios
4. $y[m] = p(x[m])$; % obtiene el resultado de la caja negra
5. $poly = {\rm polySolver}(x,y,m)$; % determinar coefs como $poly=[a_0,a_1,\cdots,a_m]$
6. si ($poly[m] == 0$) { % condición de salida
7. terminado = true;}
8. else {
9. $m++$;}
10. }

La razón por la que el código anterior funciona es que sólo necesita $m$ de las ecuaciones para resolver $m$ variables desconocidas (si no son linealmente dependientes). La consulta adicional que sucede cuando usted necesita para confirmar que la última encontrado polinomio es correcta. Si el nuevo coeficiente de $a_m$ por plazo $x^{m}$ es cero, esto significa que el anterior polinomio es ya capaz de predecir este nuevo punto de datos. Por lo tanto, nos encontramos con el polinomio.

Nota: con la configuración anterior, el algoritmo es capaz de encontrar polinomios con real-número de coeficientes, incluyendo enteros-números como un caso especial.

Por su interés, el polinomio blackbox problema es un conocido "secreto compartido" el esquema, que permite compartir un secreto (comúnmente referido como el valor de $a_0$ en el polinomio) entre $n$ de la gente, de modo que el secreto no puede ser revelado a menos $k$ de ellos está de acuerdo. Simplemente hablando, decir $n=3$$k = 2$, entonces la construcción de un grado 9 polinomio con su secreto codificado en $a_0$. Se consulta a continuación, $p(x)$ 15 veces, y dar a cada persona 5 resultados. De esta manera, ninguno de ellos puede resolver el secreto sólo por él/ella mismo / a, pero dos de ellos es suficiente para encontrar el secreto.