En álgebra informática , el algoritmo Faugère F4 , de Jean-Charles Faugère , calcula la base de Gröbner de un ideal de un anillo polinómico multivariado . 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 usando álgebra lineal rápida para realizar las reducciones en paralelo.
El algoritmo Faugère F5 primero calcula la base de Gröbner de un par de polinomios generadores del ideal. Luego usa esta base para reducir el tamaño de las matrices iniciales de los 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 una monomio no divisible por el término principal de un elemento de G anterior .
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 polinomiales interesantes, llamados secuencias regulares , sin siquiera simplificar 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 necesaria ]
El problema del "10 cíclico", que antes era intratable, fue resuelto por F5, [ cita necesaria ] al igual que varios sistemas relacionados con la criptografía; por ejemplo HFE y C * . [ cita necesaria ]