Facturando polinômios de baixo grau

8

Qual é o algoritmo mais rápido conhecido por fatorar polinômios com n variáveis ​​e grau total d ? Aqui, n está crescendo d é fixo. A maioria dos trabalhos parece considerar o caso quando d está crescendo e n é fixo. Estou interessado em resultados tanto em campos finitos quanto em racionais.

arnab
fonte

Respostas:

8

Deixe- ser um campo de característica 0 ou pelo menos d ( d - 1 ) + 1 , e p K [ x 1 , ... , x n ] ser um polinómio de grau total, no máximo, d . Se d é fixo en está crescendo, temos os seguintes limites de complexidade para a redução da fatoração de p à fatoração de um polinômio univariado com grau d : (A notação ˜ O ( )K0d(d1)+1pK[x1,,xn]ddnpdO~() ignora fatores logarítmicos.)

  1. Algoritmos determinísticos:

    • O~((n+dn)4)operações de campo , usando algoritmos de multiplicação ingênuos;
    • O~((n+2d2n1)dω)operações de campo , se houver algoritmos de multiplicação rápida, onde é um expoente admissível para álgebra linear.¹2<ω3
  2. Algoritmos probabilísticos:

    • O~((n+dn))operações de campo , se houver algoritmos de multiplicação rápida disponíveis.

Então, é preciso fatorar um polinômio univariado de grau . A complexidade dessa etapa não depende mais de ; portanto, os limites acima permanecem válidos para os algoritmos completos de fatoração. A única diferença está na característica positiva: como nenhum algoritmo determinístico de tempo polinomial é conhecido por fatorar um polinômio univariado, mesmo a redução determinística produz um algoritmo probabilístico. No entanto, se é realmente fixo e pequeno, pode-se substituir o algoritmo probabilístico de tempo polinomial por um algoritmo determinístico de tempo exponencial.dnd

Observe que o limite probabilístico é ideal até fatores logarítmicos, uma vez que é o tamanho da entrada.O~((n+dn))(n+dn)

Mais detalhes podem ser encontrados no artigo Algoritmos de fatoração polinomial multivariada densa e aprimorada de Grégoire Lecerf ( link sem paywall ).

Outra referência, especialmente para campos de pequena característica, é EL Kaltofen & G. Lecerf, Fatoração de polinômios multivariados ( link sem paywall ), capítulo 11.5 de GL Mullen e D. Panario, editores, Manual de campos finitos .

Result O resultado precisa assumir que .ω>2

Bruno
fonte
Muito Obrigado! Você conhece algum trabalho em campos muito pequenos, digamos GF (2)?
arnab
3
O limite que mencionei na minha resposta é dado por algoritmos que reduzem a fatoração multivariada a fatoração univariada. AFAIK, os limites mais conhecidos quando os resultados acima não se aplicam (ou seja, quando a característica é muito pequena) são dados por algoritmos que fazem uma redução multivariada → bivariada → univariada. Para obter mais informações, consulte a fatoração de polinômios multivariados por Kaltofen e Lecerf, capítulo 11.5 do Manual de campos finitos . Uma versão preliminar deste capítulo está aqui .
21413 Bruno