Algoritmos probabilísticos para la búsqueda de soluciones racionales de sistemas polinomiales sobre cuerpos finitos

ANTONIO CAFURE; EDA CESARATTO; GUILLERMO MATERA

Mendoza

Congreso; LVII Reunión Anual de Comunicaciones Científicas; 2008

Unión Matemática Argentina

La búsqueda de soluciones racionales de sistemas polinomiales sobre cuerpos finitos es un problema clásico, con importantes aplicaciones en criptografía, entre otros campos. De hecho, en los últimos años se han propuesto y criptoanalizado varios esquemas criptográficos multivariados basados en dicho problema. En esta charla vamos a presentar una familia de algoritmos probabilísticos que calculan soluciones racionales de un sistema polinomial definido sobre un cuerpo finito. Vamos a analizar de qué manera la probabilidad de fracaso de los mismos se puede acotar superiormente a partir de estimaciones sobre la cantidad de puntos racionales de variedades algebraicas definidas sobre un cuerpo finito, en tanto que una interpretación adecuada de las técnicas algorítmicas subyacentes nos permite obtener estimaciones finas de dicha cantidad de puntos racionales. Vamos a presentar algoritmos eficientes para un sistema "general", esto es, un sistema que define una variedad absolutamente irreducible, y analizar posibles extensiones a situaciones más generales.