Textos básicos‎ > ‎

Estimaciones de dificultad

Historia de la estimación de la dificultad de factorización[1]

El problema de factorizar enteros ha fascinado a los matemáticos desde hace mucho tiempo, existe una famosa cita de Gauss fundamental sobre esta problemática. Un estimado concreto de lo difícil que esto era para 1874, fue anunciado por W. Stanley Jevons, un economista y lógico ingles. El conjeturó [Jevons] que nadie podría nunca conocer los factores del número entero de diez cifras (10D): 8616460799. Sin embargo, alrededor de 1925 Bancroft Brown demostró que él estaba equivocado. En un manuscrito no publicado, una copia del cual fue amablemente suministrada por John Brillhart, Brown explicó como el obtuvo la factorización:

8616460799 = 96079 x 89681

En 1967, John Brillhart y John Selfridge dijeron “… en general nada más que frustración se puede esperar de un ataque a un número de 25 dígitos o más con las velocidades disponibles en las computadoras modernas.” Pero en 1970 sus estimaciones fueron desechadas debido a un nuevo método de factorización obtenido por Mike Morrison y  Jhon Brillhart para factorizar un entero de 39D. En 1976, Richard Guy dijo “Me sorprenderé si alguien obtiene los factores para un número de  de tamaño 1080 sin forma especial durante la presente centuria.” El mostró mucha cautela pocos años después. Cuando la selección del número para desafío RSA de 129D, por la estimación de Ron Rivest que la factorización de ese entero requeriría de más de “40 cuatrillones de años” sobre una computadora más rápida que las existentes en su época. Sin embargo en 1994, este  desafío fue factorizado.



[1] Odlyzko, A.M. The future of integer factorization. AT&T Bell Laboratories Murray Hill, Julio 1995 (Apéndice A).

Comments