Factorización de enteros con hipérbolas modulares

Mostrar todas las versiones(3)

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 equivalen...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Di Mauro Aparicio, Juan Pablo
Otros Autores:	Scolnik, Hugo Daniel
Formato:	Tesis doctoral publishedVersion
Lenguaje:	Español
Publicado:	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2020
Acceso en línea:	https://hdl.handle.net/20.500.12110/tesis_n6745_DiMauroAparicio
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	tesis:tesis_n6745_DiMauroAparicio
record_format	dspace
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language	Español
orig_language_str_mv	spa
description	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]
author2	Scolnik, Hugo Daniel
author_facet	Scolnik, Hugo Daniel Di Mauro Aparicio, Juan Pablo
format	Tesis doctoral Tesis doctoral publishedVersion
author	Di Mauro Aparicio, Juan Pablo
spellingShingle	Di Mauro Aparicio, Juan Pablo Factorización de enteros con hipérbolas modulares
author_sort	Di Mauro Aparicio, Juan Pablo
title	Factorización de enteros con hipérbolas modulares
title_short	Factorización de enteros con hipérbolas modulares
title_full	Factorización de enteros con hipérbolas modulares
title_fullStr	Factorización de enteros con hipérbolas modulares
title_full_unstemmed	Factorización de enteros con hipérbolas modulares
title_sort	factorización de enteros con hipérbolas modulares
publisher	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate	2020
url	https://hdl.handle.net/20.500.12110/tesis_n6745_DiMauroAparicio
work_keys_str_mv	AT dimauroapariciojuanpablo factorizaciondeenterosconhiperbolasmodulares
_version_	1782023423843631104
spelling	tesis:tesis_n6745_DiMauroAparicio2023-10-02T20:21:35Z Factorización de enteros con hipérbolas modulares Di Mauro Aparicio, Juan Pablo Scolnik, Hugo Daniel 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] 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. Fil: Di Mauro Aparicio, Juan Pablo. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2020-04-14 info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion application/pdf spa info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/tesis_n6745_DiMauroAparicio

Factorización de enteros con hipérbolas modulares

Ejemplares similares