¿Por qué las semiprimes tardan tanto tiempo en factorizarse?

Answer 1

Aquí hay dos preguntas: ¿por qué es difícil factorizar y por qué los semiprimes son particularmente difíciles de factorizar?

“Por qué es X difícil” es a menudo una pregunta difícil de responder; en cierto sentido, la mejor respuesta es la tautológica “porque no conocemos una manera fácil de hacerlo”. No hay una razón obvia para que un algoritmo de factorización muy rápido no pueda existir, pero décadas de investigación no han producido uno. La factorización es un problema inverso, y uno en el que partes importantes del número (los dígitos medios) dependen de la totalidad de sus factores, por lo que los enfoques simplistas no funcionan, pero por lo que sabemos, podría haber un enfoque muy rápido pero complicado. .

Los semiprimes son particularmente difíciles de factorizar en comparación con otros números del mismo tamaño, principalmente porque sus factores pueden ser mayores. Los criptógrafos eligen semiprimes [math] n [/ math] cuyos factores están dentro de un orden de magnitud de [math] \ sqrt {n} [/ math], pero si [math] n [/ math] tiene 3 factores, entonces al menos uno de ellos es como máximo [math] \ sqrt [3] {n} [/ math]. Y, por supuesto, si [math] n [/ math] tiene solo un factor primo, entonces ya está factorizado.

Sin embargo, el tiempo de ejecución del algoritmo más rápido para factorizar números grandes, el Tamiz de campo de número general, depende solo de la longitud de [math] n [/ math]. Por lo tanto, puede ser, pero no he investigado esto, que el producto de tres números primos sea tan difícil de factorizar como un semiprime de la misma longitud.

Answer 2

Si es un factor pequeño, no importa cuán grande sea el semiprime, no tardará mucho en encontrarlo. Eso representa, digamos, el 99% de ellos. También es extremadamente fácil encontrar un factor de cualquier tamaño utilizando el método de la diferencia de dos cuadrados si esos cuadrados no son demasiado grandes para encontrarlos. Eso deja los factores de gran magnitud del tipo “simétrico” que no son vulnerables a trucos como la diferencia de cuadrados. Un semiprime de gran magnitud se vuelve problemático solo por la gran cantidad de números que deben ser tamizados. Debe pensar no en el número escrito como un número, sino en los números contables que contiene. Cuando agrega dos dígitos a un número, aumenta la raíz cuadrada en un orden de magnitud, es decir, 10 veces más grande. El tamaño de los semiprimes utilizados en el cifrado es fácil de escribir pero casi imposible de imaginar. RSA-2048 tiene 617 dígitos decimales. Considere que las partículas en el universo están en los e80 y que un googol tiene 100 dígitos. Ahora considere multiplicar ese googol 517 veces por 10 ([matemáticas] 10 ^ {517} [/ matemáticas]). Sin algún truco desconocido, factorizarlo está más allá de cualquier poder computacional clásico.