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(d−1)+1p∈K[x1,…,xn]ddnpdO~(⋅) ignora fatores logarítmicos.)
Algoritmos determinísticos:
- O~((n+dn)4)operações de campo , usando algoritmos de multiplicação ingênuos;
- O~((n+2d−2n−1)dω)operações de campo , se houver algoritmos de multiplicação rápida, onde é um expoente admissível para álgebra linear.¹2<ω≤3
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