En álgebra computacional , el algoritmo Faugère F4 , de Jean-Charles Faugère , calcula la base de Gröbner de un ideal de un anillo polinómico multivariante . El algoritmo utiliza los mismos principios matemáticos que el algoritmo de Buchberger , pero calcula muchas formas normales de una sola vez formando una matriz generalmente dispersa y utilizando álgebra lineal rápida para hacer las reducciones en paralelo.
El algoritmo F5 de Faugère calcula primero la base de Gröbner de un par de polinomios generadores del ideal. Luego utiliza esta base para reducir el tamaño de las matrices iniciales de generadores para la siguiente base más grande:
Si G prev es una base de Gröbner ya calculada ( f 2 , …, f m ) y queremos calcular una base de Gröbner de ( f 1 ) + G prev entonces construiremos matrices cuyas filas sean m f 1 tales que m sea un monomio no divisible por el término principal de un elemento de G prev .
Esta estrategia permite al algoritmo aplicar dos nuevos criterios basados en lo que Faugère llama firmas de polinomios. Gracias a estos criterios, el algoritmo puede calcular bases de Gröbner para una gran clase de sistemas polinómicos interesantes, llamados secuencias regulares , sin tener que simplificar nunca un solo polinomio a cero (la operación que consume más tiempo en los algoritmos que calculan bases de Gröbner). También es muy eficaz para una gran cantidad de secuencias no regulares.
Se implementa el algoritmo Faugère F4
Las versiones de estudio del algoritmo Faugère F5 se implementan en [ cita requerida ]
El problema hasta entonces intratable del "ciclo 10" fue resuelto por F5, [ cita requerida ] al igual que una serie de sistemas relacionados con la criptografía; por ejemplo, HFE y C * . [ cita requerida ]