Algoritmos basados en lattices aplicados al cálculo del número de Humbert-Hermite en Z

Tesis (Magíster en Ciencias de la Informática) -- Prof. guía: Luis Salinas C., profs. correfs.: Héctor Allende, Horst von Brand

[Resumen del autor]

Este proyecto de tesis se enmarca en el ámbito de la computación científica aplicada a problemas algebraicos. Por lo tanto, involucra elementos de la ciencia de la computación como el diseño y análisis de algoritmos, optimización discreta multiobjetivo y computación paralela, y también, elementos matemáticos como son la teoría de formas cuadráticas definidas positivas, lattices, teoría de reducción, entre muchos otros. La relevancia de este proyecto radica en las múltiples aplicaciones que los algoritmos de lattices han alcanzado en diversas áreas de la ciencia, como teoría algorítmica de números, informática teórica y recientemente en criptografía. En este contexto, es una premisa de este proyecto expandir los horizontes de los algoritmos de lattices a un nuevo problema teórico, el cual podría ser un paso crucial en el futuro para el desarrollo de nuevas aplicaciones a la ingeniería. El problema que se aborda en esta tesis cimienta sus raíces en el conoc-ido problema de empaquetamiento de esferas, el cual ha atraído la atención de las mentes más brillantes desde comienzos del siglo XVII, como lo demuestra la famosa conjetura de Kepler{1611) y la controversia de Gregory-Newton (1694). La fascinante estructura y aplicaciones asociadas con este problema han contribuido al desarrollo de muchos campos de la matemática, entre los cuales destaca la Geometría de los Números, introducida por Minkowsky (1864) en su intento por estudiar las formas cuadráticas definidas positivas usando técnicas de la geometría. Esta línea de investigación elucidó el asombroso vínculo entre las formas cuadráticas definidas positivas y las lattices. En efecto, muchos resultados asociados con formas cuadráticas pueden ser expre<U+00AC>sados en el lenguaje de las lattices. Esta relación ha motivado un fuerte Ínteres en el estudio y caracterización de estos objetos matemáticos, siendo el resultado obtenido en 1982 por Lóvacs, Lenstra y Lenstra (el algorimo LLL) uno de los muchos grandes avances obtenidos hasta la fecha. En 1997 Baeza e Icaza estudiaron la generalización de la teoría de reducción de formas cuadráticas sobre cuerpos de números, siguiendo la línea de investigación desarrollada por Hum-bert a inicios de los años 40. Su estudio los condujo al desarrollo de una generalización del número de Hermite, el cual ha sido denominado número de Humbert-Hermite. El cálculo de esta cantidad se encuentra relacionado con el valor mínimo que el producto de una tupia de for<U+00AC>mas cuadráticas definidas positivas puede alcanzar, sobre los enteros algebraicos de un cuerpo de números de Índice finito sobre Q. En esta tesis se establecen y estudian las relaciones existentes entre el cálculo del número de Humbert-Hermite y el problema del vector más corto en una lattice (SVP). Esta conexión resulta plausible atendiendo la ya conocida relación entre cí problema del vector más corto en una lattice y el número de Hermite de una forma cuadrática definida positiva. Por otra parte, se utilizan las relaciones encontradas para formular e implementar un algoritmo capaz de calcular una versión simplificada del número de Humbcrt-Hermite. Específicamente, so cxtcndienden las ideas relacionadas con el algoritmo de enumeración de Schnorr y el método describa presentado por Ajtai. Kuniar y Sivakumar para enfrentar el cálculo de esta cantidad.

p. 103

2

CONSULTE EN LINEA A TRAVES DE REPOSITORIO INSTITUCIONAL