Predicción de sucesiones pseudoaleatorias y descripción de digrafos de Cayley mediante retículas enteras

Resumen

La tesis estudia dos problemas en el campo de la Teoría de la Comunicación: la predicción de generadores de números pseudoaleatorios y el encaminamiento en grafos circulantes, Como herramienta matemática, se utilizan las retículas enteras en ambas partes. El primer capítulo recoge la definición de retícula como subgrupo discreto del grupo aditivo de los vectores con componentes reales y resultados conocidos sobre problemas computacionales asociados (SVP y CVP) y Geometría de los Números. Se expone también la construcción que asocia un ideal binomial a cada retícula entera. El segundo capítulo presenta varios resultados de predicción de la sucesión de valores que define un generador de números pseudoaleatorios. A partir de un generador específico, se define un algoritmo que, partiendo de aproximaciones de varios valores consecutivos, devuelve los valores exactos. Esto permite la obtención de los parámetros que gobiernan el generador y la reproducción de la sucesión. Estos algoritmos requieren conocer el espacio de númros que produce el generador, y en algunos casos, una parte de sus parámetros. Se demuestra que los métodos propuestos devuelven el resultado correcto con alta probabilidad, suponiendo que la calidad de las aproximaciones utilizadas es superior a una cota dada. En la mayoría de los casos, esta cota coincide con los resultados experimentales obtenidos de la impletación en lenguaje C++ de los algoritmos. En el tercer capítulo se relacionan los caminos de un grafo circulante con las retículas enteras, interviniendo la norma L1 como medida de la longitud de los caminos. Se utilizan ideales monomiales para estudiar la generalización de los diagramas de mínima distancia a digrafos de grado arbitrario y se muestra como calcular estos ideales mediante el cálculo de bases de Gröbner de retículas enteras. El problema del encaminamiento, que puede verse como un problema de programación entera, se estudia desde la perspectiva de los diagramas de mínima distancia asociados a un orden monomial. También se presentan algoritmos específicos para el encaminamiento en grafos de grado dos. En el cuarto capítulo se resumen las tareas de programación llevadas a cabo como complemento del material anterior: la implementación de los algoritmos del segundo capítulo y el programa Circule, que permite el dibujo interactivo de digrafos circulantes y diagramas de mínima distancia asociados.