Los algoritmos F4 y F5 de Faugère

En álgebra computacional , el algoritmo F4 de Faugère , creado por Jean-Charles Faugère , calcula la base de Gröbner de un ideal de un anillo de polinomios multivariados . El algoritmo utiliza los mismos principios matemáticos que el algoritmo de Buchberger , pero calcula varias formas normales de una sola vez mediante la formación de una matriz generalmente dispersa y el uso de álgebra lineal rápida para realizar las reducciones en paralelo.

El algoritmo Faugère F5 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 ₂ , …, f _m ) y queremos calcular una base de Gröbner de ( f ₁ )  + G _prev entonces construiremos matrices cuyas filas sean m f ₁ 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 denomina signaturas de polinomios. Gracias a estos criterios, el algoritmo puede calcular bases de Gröbner para una amplia clase de sistemas polinómicos interesantes, llamados secuencias regulares , sin necesidad de simplificar ningún polinomio a cero, la operación que consume más tiempo en los algoritmos de cálculo de bases de Gröbner. Además, resulta muy eficaz para un gran número de secuencias no regulares.

El algoritmo Faugère F4 está implementado.

• en FGb , la propia implementación de Faugère, que incluye interfaces para usarla desde C/C++ o Maple ,
• en el sistema de álgebra computacional Maple , como la opción method=fgb de la función Groebner[gbasis]
• en el sistema de álgebra computacional Magma ,
• en el sistema de álgebra computacional SageMath ,

Las versiones de estudio del algoritmo Faugère F5 se implementan en

• el sistema de álgebra computacional SINGULAR ; ^{[ 1 ]}
• el sistema de álgebra computacional SageMath .
• en el paquete de Python SymPy . ^{[ 2 ]}

El problema del "10 cíclico", que antes era intratable, fue resuelto por F5, al igual que varios sistemas relacionados con la criptografía; por ejemplo, HFE y C ^* .

• Faugère, J.-C. (junio de 1999). "Un nuevo algoritmo eficiente para calcular bases de Gröbner (F ₄ )" (PDF) . Journal of Pure and Applied Algebra . 139 (1): 61– 88. doi : 10.1016/S0022-4049(99)00005-5 . ISSN 0022-4049 . 
• Faugère, J.-C. (julio de 2002). «Un nuevo algoritmo eficiente para calcular bases de Gröbner sin reducción a cero ( _F5 ) ». Actas del simposio internacional de 2002 sobre computación simbólica y algebraica (PDF) . ACM Press. págs. 75-83 . CiteSeerX 10.1.1.188.651 . doi : 10.1145/780506.780516 . ISBN   978-1-58113-484-1. S2CID 15833106 . 
• Revisión del algoritmo F5 de Till Stegers Faugère ( enlace alternativo ). Diplom-Mathematiker Thesis, asesor Johannes Buchmann, Technische Universität Darmstadt, septiembre de 2005 (revisado el 27 de abril de 2007). Muchas referencias, incluidos enlaces a implementaciones disponibles.

• Página principal de Faugère (incluye reimpresiones en PDF de artículos adicionales)
• Introducción al algoritmo F4.