Encuentre el resto de un gran polinomio fijo cuando se divide por un pequeño polinomio desconocido

9

Supongamos que operamos en un campo finito. Se nos da un gran polinomio fijo p (x) (de, digamos, grado 1000) sobre este campo. Este polinomio se conoce de antemano y se nos permite hacer cálculos utilizando muchos recursos en la "fase inicial". Estos resultados pueden almacenarse en tablas de consulta razonablemente pequeñas.

Al final de la "fase inicial", se nos dará un pequeño polinomio desconocido q (x) (de, digamos, grado 5 o menos).

¿Existe una forma rápida de calcular p (x) mod q (x) dado que se nos permite hacer algunos cálculos complicados en la "fase inicial"? Una forma obvia es calcular p (x) mod q (x) para todos los valores posibles de q (x). ¿Hay una mejor manera de hacer esto?

paulwaters
fuente

Respuestas:

3

Los siguientes algoritmos funcionan bien si el campo subyacente tiene un orden muy pequeño .s

Supongamos que sabemos es irreducible, de grado fijo . Entonces, mod , sabemos que mantiene. Por lo tanto, basta precalcular .d q x s d = x p ( x )qdqxsd=xp(x)modxsdx

En general, puede descomponerse en un producto de polinomios irreducibles . En este caso, se aplica un argumento similar para calcular módulo cada separado, y luego juntar los resultados. Entonces, realmente necesitamos calcular para cada .q = q 1q r p q 1 , , q r p ( x )q(x)q=q1qrpq1,,qrd dp(x)modxsdxdd

David Harris
fuente
2

Creo que hay una manera bastante rápida de hacer esto. Deje que los coeficientes del polinomio aún desconocido sean , entonces donde es un número pequeño. Ahora comencemos a calcular donde , donde es grande y se conoce a . Esto lo hacemos reduciendo el grado usando igualdades como . Finalmente, lo que obtenemos es un polinomio de grado , cuyos coeficientes son polinomios de (ya queb i q = d i = 0 b i x i d pqbiq=i=0dbixidp = D i = 0 a i x i D a i a D x D = - a Dp(modq)p=i=0DaixiDai<d-1biaiqaDxD=aDbdi=1d1bdixDi<d1biaison conocidos). Estos polinomios podemos calcularlos rápidamente una vez que obtengamos .q

domotorp
fuente
-1

Vea excelentes comentarios sobre esta publicación a continuación. :)


Preprocesamiento; entrada: p(x)

  1. Factoriza como .p ( x ) = 1000 i = 0 ( x i - r i )p(x)p(x)=i=01000(xiri)

  2. Almacene esto como una tabla de raíces distintas y sus respectivas multiplicidades .r j m jTrjmj

Fase en línea; entrada: q(x)

  1. Factoriza como .q ( x ) = 5 i = 0 ( x i - r i )q(x)q(x)=i=05(xiri)

  2. Almacene esto como una lista de raíces distintas y sus respectivas multiplicidades .r j m jLrjmj

  3. Mientras que no está vacía, retire la siguiente raíz / multiplicidad de y cualquier términos semejantes en .L TLLT

  4. Lea de la tabla modificada y la salida. Tp(x)modq(x)T


Otros comentarios:

  • Obviamente, desea ordenar la tabla y acceder a ella con búsqueda binaria (o un árbol).T
  • (Sea el grado de . Si desea que la salida esté en representación de coeficiente, puede hacer un montón de FFT al final para obtener tiempo.p ( x ) p ( x ) mod q ( x ) ˜ O ( d )dp(x)p(x)modq(x)O~(d)
  • Dependiendo de cómo lo formalice, probablemente pueda calcular previamente muchas de las diversas formas en que recombinaría los términos en antemano (estilo de programación dinámica), de modo que la mayoría (o todas) de las multiplicaciones son solo búsquedas. El costo dominante es entonces el número de búsquedas, o aproximadamente . Si , esto es solo un puñado de operaciones aritméticas concretas.O ( log d ) d = 1000TO(logd)d=1000
Daniel Apon
fuente
2
¿En qué campo está factorizando p? ¿Qué tan grande espera que sea esta representación en términos del campo original? Y cuando dice leer de la tabla modificada y la salida, ¿qué quiere decir?
David Eppstein el
2
Esto solo funcionaría si está operando en un campo donde y dividen. Pero esto parece depender de ; en particular, no puede calcular previamente las raíces para solo. Además, calcular las raíces de en un campo tan grande llevará tiempo (al menos); Esto no es mejor que el ingenuo algoritmo. q q p q | p |pqqpq|p|
David Harris