Sucesiones de recurrencia sobre cuerpos finitos y sus aplicaciones

Abstract

Nuestro objetivo es encontrar una forma de obtener sucesiones pseudoaleatorias y para ello vamos a utilizar como herramienta las sucesiones de recurrencia lineal sobre cuerpos finitos. Estas sucesiones son periódicas y uno de los problemas será conseguir un periodo lo mayor posible. Describiremos el polinomio característico y veremos la importancia de la elección de los primeros términos. Después, definiremos el orden de un polinomio y utilizaremos las funciones generatrices como método de representación y caracterización. Estudiaremos también una serie de combinado res para construir sucesiones con periodo grande a partir de otras con periodos más pequeños. Puesto que la sucesión que obtenemos a partir de uno de estos combinadores vuelve a ser de recurrencia lineal, vamos a demostrar el algoritmo de Berlekamp-Massey, gracias al cual, conociendo un número adecuado de términos de la sucesión, obtenemos el polinomio mínimo. Finalmente, describiremos la distribución de bits y veremos algunas aplicaciones.