Registro:
| Documento: | Tesis Doctoral |
| Título: | Factorización de enteros con hipérbolas modulares |
| Autor: | Di Mauro Aparicio, Juan Pablo |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Filiación: | Universidad de Buenos Aires - CONICET. Instituto de Investigación en Ciencias de la Computación (ICC)
|
| Publicación en la Web: | 2022-03-29 |
| Fecha de defensa: | 2020-04-14 |
| Fecha en portada: | 2019 |
| Grado Obtenido: | Doctorado |
| Título Obtenido: | Doctor de la Universidad de Buenos Aires en el área de Ciencias de la Computación |
| Director: | Scolnik, Hugo Daniel |
| Consejero: | Marenco, Javier Leonardo |
| Jurado: | Pacetti, Ariel Martín; Moreira, Carlos; Weissbein, Ariel |
| Idioma: | Español |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/tesis_n6745_DiMauroAparicio |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n6745_DiMauroAparicio.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n6745_DiMauroAparicio |
| Ubicación: | Dep.COM 006745 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Di Mauro Aparicio, Juan Pablo. (2019). Factorización de enteros con hipérbolas modulares. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/tesis_n6745_DiMauroAparicio |
Resumen:
El problema de la factorización de enteros ha cobrado una importancia capital en las últimas tres décadas, en gran parte debido al uso extendido del criptosistema RSA[20]. La cuestión es teórica y prácticamente relevante. Un ejemplo inmediato del primer caso es la pregunta: ¿quebrar RSA es equivalente a resolver el problema de factorización de enteros en tiempo polinomial?[1],[5]. En lo que respecta a cuestiones prácticas, numerosos algoritmos para factorizar (de aquí en adelante se hablará de factorización de enteros), han sido propuestos en los últimos treinta años (o más). No obstante pasaron más de quince desde el avance significativo más reciente, la invención de la criba del cuerpo de números (NFS, [17]). Aun así, utilizando NFS en el año 2009, la factorización de un número de 768 bits representativo del problema requirió el esfuerzo conjunto de varias instituciones y una cantidad enorme de tiempo y procesamiento (sólo la elección del polinomio a utilizar en el algoritmo tomó 3 meses en 80 procesadores [16]). Pueden encontrarse, por una parte, algoritmos determinísticos o estocásticos cuya complejidad no puede ser demostrada rigurosamente. Por otra, algoritmos cuya cota para el tiempo de ejecución es lo suficientemente ajustada y ha sido probada rigurosamente, pero con desempeño peor que los del primer grupo. El algoritmo rho de Pollard [19], la criba cuadrática ([7], sección 6.1) y la criba del cuerpo de números [17] son ejemplos del primer tipo, mientras que el algoritmo de Strassen ([7] sección 5.5) lo es del segundo y hasta el momento, el de menor complejidad en su clase. Sin embargo, ninguno de ellos está acotado polinomialmente y aun no se conoce un algoritmo de factorización en tiempo polinomial en el paradigma computacional clásico [25]. Teniendo en cuenta ese panorama y que muchos algoritmos subexponenciales fueron secuelas de métodos exponenciales, es que se justifica el estudio y desarrollo de nuevos procedimientos para la factorización de enteros, aun cuando sean exponenciales (pero de una complejidad moderada). Adicionalmente, muchos algoritmos comparten un antecedente común debido a Fermat: la relación entre los factores de un entero n y las soluciones a la ecuación diofántica n+x^2 = y^2. Este trabajo retoma esa idea inicial. Está basado en la observación hecha por H. Scolnik de que existen soluciones modulares únicas y fácilmente calculables de n+x^2 ≡ y^2 mód c para algunos enteros c, lo que posteriormente llevó al mismo autor a definir targets para un entero [24]: un target para n es una terna de enteros (a, b, c) con 0 ≤ a, b < c que satisface n + a ≡ b mód c y tanto a como b son residuos cuadráticos de c. A propósito de ello, no es evidente cómo podrían ser de utilidad los targets para factorizar un entero. Más aun, es necesario saber cuántos targets hay para un c fijo y el crecimiento del número de ellos en relación a c. Como puede verse al principio del capítulo 3, la reducción en la magnitud de las incógnitas que se consigue utilizando targets, se ve contrarrestada por el incremento en la cantidad de targets posibles y por eso es necesario profundizar sobre este tema para conseguir un procedimiento para factorizar, con complejidad aceptable. El aporte fundamental de este trabajo es, en primer lugar la construcción de una teoría necesaria para targets y su relación con las hipérbolas modulares, estudiadas por Shparlinski [27]. (Como nota histórica, ambos conceptos se habían desarrollado de forma independiente hasta el momento.) Los resultados obtenidos al respecto son de interés en sí mismos y en relación con los desarrollos previos (por ejemplo, puede verse en [22] y en [13] otros usos de las hipérbolas modulares en la factorización de enteros). Como consecuencia de lo anterior, y segunda contribución, presentamos un algoritmo determinista para factorizar enteros utilizando distancias entre puntos de una hipérbola modular (o targets según la secció ). Proponemos también variantes para su implementación y por ́ultimo, analizamos su complejidad. Suponiendo que la parte x de la solución a la ecuación de Fermat sea menor en valor absoluto que n^1− [fórmula aproximada, revisar la misma en el original], el tiempo de ejecución del algoritmo de factorización con targets es de O (2^−m n^1− M) [fórmula aproximada, revisar la misma en el original] con M y m dependiendo de log n. En la sección 2.4, teorema 8 puede encontrarse una referencia sintética sobre el algoritmo y su tiempo de ejecución. Por ejemplo, cuando = 0,57 (|x| < n^0,43) para n de 1024 bits, la cantidad elemental de operaciones es alrededor de O(n^1/3M). Aunque el tiempo de ejecución del algoritmo del capítulo 3 es exponencial y similar a otros existentes, su desarrollo aporta un enfoque nuevo al problema y muestra la utilidad de las hipérbolas modulares en un problema computacional concreto. Los algoritmos fueron programados en Python, usando una librería para enteros grandes. Los resultados de los experimentos numéricos se resumen en la sección 3.4 y como puede verse, el cálculo teórico de la complejidad es ratificado en la ejecución. ***[fórmulas aproximadas, revisar las mismas en el original]
Abstract:
Motivated by the RSA cryptosystem, we treat here the problem of integer factorization. In the first part a brief survey of some actual algorithms is presented. In the second, we develop the theory needed for a new algorithm of integer factorization. For a composite n and an odd c with c not dividing n, the number of solutions to the equation n + a ≡ b mód c with a, b quadratic residues modulus c is calculated. We establish a direct relation with those modular solutions and the distances between points of a modular hyperbola. Furthermore, for certain composite moduli c, an asymptotic formula for quotients between the number of solutions and c is provided. Finally, an algorithm for integer factorization using such solutions and of complexity approximate to O (n^1/3) is presented. In the final part, we provide some numerical examples.
Citación:
---------- APA ----------
Di Mauro Aparicio, Juan Pablo. (2019). Factorización de enteros con hipérbolas modulares. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n6745_DiMauroAparicio
---------- CHICAGO ----------
Di Mauro Aparicio, Juan Pablo. "Factorización de enteros con hipérbolas modulares". Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2019.https://hdl.handle.net/20.500.12110/tesis_n6745_DiMauroAparicio
Estadísticas:
Descargas totales desde :
Descargas mensuales
https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n6745_DiMauroAparicio.pdf
