Advertencia de respuesta larga: (Esto está copiado de un ensayo que escribí)
Factorizando números primos.
Los números primos son un enigma fascinante que desconcertó a algunas de las mejores mentes desde los albores del pensamiento humano. Gauss solía pasar el tiempo (un cuarto de hora inactivo en sus propias palabras) contando lo que él llamó chiliads de números primos, bloques de mil en su cabeza buscando números primos. Informó que llegó a cientos de miles sin llegar a un millón. Para el resto de los mortales, determinar la distribución de los números primos es un problema significativamente más difícil. Afortunadamente, no estamos limitados a nuestros cerebros con su memoria de trabajo bastante limitada, utilizamos computadoras para procesar estas operaciones hoy en día. Alfred North Whitehead dijo una vez que “la civilización avanza al extender el número de operaciones importantes que podemos realizar sin pensar en ellas”. Según ese criterio, la civilización se duplica aproximadamente cada dieciocho meses. Esto se conoce como la ley de Moore. Esto es una gran ayuda para el campo de las matemáticas, con mejores procesadores y unidades centrales de procesamiento, podemos hacer cálculos cada vez más complejos en menos tiempo. Un ejemplo de esto es la prueba del teorema de los cuatro colores que dependía de las computadoras para forzar esencialmente la fuerza bruta de un cierto conjunto de mapas que luego se utilizó, ya que cualquier contraejemplo contendría uno de estos mapas y, por lo tanto, sería una contradicción. En su mayor parte, las personas no intentan factorizar manualmente los números en números primos, principalmente porque los números que nos interesan generalmente tienen 1024 o 2048 bits, lo que hace que sea imposible hacerlo sin computadoras. Sin embargo, eso no quiere decir que las computadoras sean un deus ex machina mágico. Todavía tenemos que escribir programas e implementar software. Como veremos, esta es la parte difícil, pero primero debemos desviarnos brevemente de las propiedades de los números primos.
Los números primos son números con solo 1 y en sí mismos para un factor, 1 no es un número primo. Suena engañosamente simple. Sin embargo, el matemático ha estado estudiando números primos durante los últimos dos mil años. Los números primos siguen siendo un tema de interés en áreas de las matemáticas como la teoría de números … etc. Dos de los primeros teoremas sobre números primos provienen de Euclides en sus elementos. La primera es que cualquier número puede factorizarse en números primos. Esto se llama el teorema fundamental de la aritmética. Sin embargo, esto es solo un teorema de existencia. Nos dice que para cualquier número compuesto, existen factores de números primos, pero no nos da una fórmula para calcular dichos factores primos. Sin embargo, esto permite al lector tener una idea de lo que tiene de especial los números primos. Los números primos son el equivalente matemático de las partículas subatómicas a la física de partículas, o los genes a la biología evolutiva. Son como unidades básicas de enteros. Esto es lo que los hace de enorme interés para los matemáticos. Euclides también demostró que hay N casos de números primos, lo que significa que hay una cantidad infinita de ellos. La prueba es la siguiente, tome una lista finita de números primos, P es el producto de todos los números primos, mientras que Q = P + 1. O Q es primo o no es primo. Si es así, cualquier lista finita de primos siempre tendría más primos. La segunda opción significaría que el número sería un número compuesto, lo que implica que tiene un factor primo p, que luego se dividiría en P ya que es el producto de los primos listados. Como p se divide en P y Q, se dividiría en la diferencia entre P y Q, que es solo uno. Pero no hay un número primo que se divida en 1, por lo tanto, p no puede estar en la lista y hay un número primo no listado más. QED, hay primos infinitos. Sin embargo, este teorema no ha impedido que los aficionados e investigadores busquen números primos cada vez más grandes. Actualmente, el número primo más grande conocido es 2 ^ 57.885.161 – 1. Observe de nuevo que este es un teorema de existencia, lo que significa que nos dice que mientras hay primos infinitos, no nos dice dónde en 
los números primos son, con qué frecuencia hay números primos, etc. Estas son las preguntas realmente interesantes. La distribución precisa de los números primos sigue siendo una de las preguntas abiertas de las matemáticas. Hay una serie de conjeturas famosas relacionadas con la búsqueda de patrones en números primos. Los primos gemelos son números primos que están separados por dos números. La conjetura del primo gemelo pregunta si hay infinitos primos gemelos. Esto no está resuelto. (Aunque los resultados recientes de Yitang Zhang mostraron que incluso cuando los números primos gemelos se vuelven cada vez más raros a medida que aumenta el número, existe una brecha límite de 70 millones como máximo, otros matemáticos han reducido el número aún más. Enlace: [1311.4600] Pequeño brechas entre números primos) La conjetura de Goldbach es igualmente famosa. Establece que cada número par mayor que dos debe ser la suma de dos números primos. Esta es otra conjetura no probada. Quizás la más famosa es la hipótesis de Riemann, postulada por primera vez por Bertrand Riemann. Es uno de los siete problemas del Milenio por el que el instituto Clay ofrece un millón de dólares, sin mencionar la fama inmortal que se obtendría por resolverlo. Algunos otros resultados notables en relación con los números primos son el teorema de los números primos, el teorema de Green-Tao, etc. El teorema de los números primos establece que el número primo se vuelve cada vez más raro a medida que el número aumenta pero no desaparece, es una declaración de aproximadamente cuantos primos hay donde, siendo n log n. El tamiz de Eratóstenes es el primer algoritmo que tenemos para calcular números primos, aunque superado por mucho tiempo. El pequeño teorema de Fermat fue otro gran avance en esta área.
Todo esto es algo bastante abstruso. Pero los números primos son muy importantes, no solo porque los matemáticos están fascinados con los patrones y todo lo relacionado con los números primos. Lo cual en sí mismo debería proporcionar suficientes razones para estudiar números primos. La razón clave por la que los números primos conciernen a muchas personas fuera de la torre de marfil de la academia es que se usan en esquemas de cifrado modernos. Cada vez que alguien se conecta y realiza una transacción financiera, los números primos los protegen de que sus crackers y otras personas malintencionadas lean sus datos. Este es el motivo práctico detrás de esta cuestión de factorizar números primos. Si bien la mayoría de los matemáticos cree que los esquemas de cifrado modernos, como RSA, son seguros en el sentido de que las computadoras más poderosas del mundo tomarían un tiempo más largo que la edad actual del universo para forzar estos hash a fuerza bruta, esto no se ha demostrado. Por supuesto, si el atacante está dispuesto a ejercer ese tipo de recursos, hay vectores mucho más fáciles de explotar. Dado que este no es el momento ni el lugar para entrar en eso, asumimos que las políticas de seguridad adecuadas se han codificado y configurado de manera confiable. En teoría, nadie debería ser capaz de romper el cifrado ofrecido al tener números primos enormes que ninguna computadora puede tener en cuenta en un tiempo razonable. Entonces, ¿cómo funciona esto? Este es el tema del resto del ensayo.
La respuesta simple es que factorizar es una función unidireccional. Esto solo significa que es mucho más fácil tomar dos números primos grandes y multiplicarlos en lugar de ir hacia atrás, es decir, si a alguien se le dan los resultados y luego se le pide que encuentre los números primos utilizados para multiplicarlo. Este número se llama semiprime. Nadie ha encontrado una manera eficiente de hacer esto. Los algoritmos existentes no son suficientes para resolver el problema en tiempo polinómico. Esto es válido si los números primos tienen una longitud determinada, 2000 bits y se eligen aleatoriamente. La advertencia es que dos números no deben estar demasiado cerca, para evitar ser factorizados usando el método de factorización de Fermat. Si estas condiciones no se cumplen, hay casos especiales en los que existen métodos más eficientes para factorizar números primos. Además, esto es cierto para factorizar enteros en general, sin embargo, se usan números primos porque ofrecen una solución única. Tanto los números enteros como los números primos son problemas difíciles en este sentido. Hasta el día de hoy, uno de los factores más importantes fue parte del desafío RSA. El desafío RSA fue creado por los laboratorios RSA para inspirar a las personas a realizar una investigación activa en esta área. RSA-768 se resolvió en 2009 mediante un proyecto de investigación colaborativo que se ejecuta en cientos de máquinas. Sin embargo, esto tenía solo 768 bits y 232 dígitos, mucho más débil que los primos actualmente en uso en esquemas de cifrado. Cuanto mayor es el número primo utilizado, más difícil es factorizar, y esta dificultad aumenta exponencialmente. Sin embargo, existen algunos algoritmos interesantes que representan los métodos actuales más modernos. El tamiz de campo de número general es actualmente la forma más eficiente que tenemos de factorizar números de más de 100 dígitos. Hay algunos tamices de campo con números especiales que se utilizan para fines especiales. De cierto interés son las pruebas de primalidad diseñadas para probar si un número es primo o no. Estos tienden a ser problemas más fáciles en términos de potencia informática, que se ejecutan fácilmente en tiempo polinómico. Algunos pueden probar si un número es primo o no, mientras que otros pueden decir si un número es un número compuesto o no. En resumen, hay algunos métodos matemáticos interesantes que son el foco de la investigación y el trabajo activos.
Y ahora si podemos explorar una escena muy hipotética. Si tuviéramos una computadora cuántica, que son básicamente computadoras que explotan ciertas características de la mecánica cuántica para aumentar radicalmente la cantidad de potencia computacional que tenemos. A un nivel muy elemental, la computadora moderna funciona con bits, 0 y 1 ‘. Por supuesto, en un nivel, todas las computadoras son computadoras “cuánticas”, las computadoras actuales no están exentas de la ley de la física. Sin embargo, esto no es lo que se entiende por computadoras cuánticas. Estas computadoras se basan en la superposición de estados cuánticos y propiedades como el enredo cuántico. Dependen de qubits en lugar de bits, lo que significa que pueden tomar valores entre uno y cero a diferencia de las computadoras contemporáneas. A partir de 2013, no existe tal computadora más allá de modelos muy primitivos que ni siquiera coinciden con las computadoras que tenemos ahora. Por supuesto, gran parte de esta investigación probablemente se clasifica debido al potencial de realizar criptoanálisis, por lo que la advertencia es hasta donde sabemos. En pocas palabras, cuando está completamente desarrollado, una de estas computadoras puede hacer proezas computacionales que las computadoras clásicas ni siquiera pueden hacer. Para una computadora cuántica, factorizar primos sería ridículamente fácil. Una computadora cuántica puede estar en 2 * n cantidad de estados simultáneamente, mientras que una computadora clásica puede estar en uno de estos estados a la vez. De hecho, ya existe un algoritmo capaz de factorizar un número primo en tiempo polinómico, el algoritmo de Shor para una página cuántica en la computadora. También es posible resolver problemas de registro discreto, el otro método utilizado para el cifrado. De hecho, ya se ha hecho una versión prototipo de esto. En 2001, en IBM, un grupo usó una computadora cuántica con solo 7 qubits para factorizar 15 en 3 y 5. Uno puede imaginar fácilmente lo que una máquina similar puede hacer con muchos más qubits. El récord actual para esto es una factorización de 21. En resumen, una computadora cuántica madura sería el golpe de gracia para nuestros esquemas de cifrado actuales y casi cualquier otra cosa que encontremos que necesitamos fuerza bruta para resolver. Sin embargo, construir una computadora cuántica está lleno de dificultades, principalmente debido a la necesidad de evitar que ocurra la decoherencia. Los estimados de tiempo actuales para esta tecnología son de al menos 30-50 años más y tendrán mucha más aplicación que simplemente factorizar primos.
Para resumir este ensayo, los factores primos de factorización son difíciles porque carecemos de un algoritmo eficiente para factorizar semi-primos grandes dada la potencia computacional limitante que poseemos. Esto podría cambiar en el futuro si algún intrépido matemático o informático puede encontrarnos un algoritmo mejor o si hay un cambio de paradigma en la cantidad de poder computacional que tenemos, muy probablemente a través del desarrollo de computadoras cuánticas, en cuyo caso podemos implementar Shor’s algoritmo.
Por último, para obtener una visión más profunda sobre esta cuestión, uno puede mirar el problema P vs NP en informática y matemáticas. Parte de los factores primos de factorización es encontrar formas y algoritmos eficientes para que las computadoras trabajen. La informática ha encontrado formas de clasificar ciertas formas de resolver problemas, cuán complicados son, cuánto tiempo lleva resolverlos … etc. El problema P vs NP fue presentado por primera vez en un documento por Stephen Cook y ahora es uno de los más importantes. Pregunta importante en informática. Esto se puede ver por su inclusión en los problemas de los siete milenios con el premio correspondiente de un millón de dólares. Dicho en términos simples, pregunta: si una computadora puede verificar rápidamente que la solución a un problema es correcta, ¿puede resolverlo rápidamente? Hay una aplicación obvia para el problema en cuestión, si se le da un semiprime y los dos números primos, una computadora puede verificar rápidamente si el semiprime es el producto de los dos números primos. Pero, ¿puede resolver el problema de factorización tan rápido o a una velocidad comparable? La respuesta parece ser no, pero no tenemos una prueba matemática de lo que la mayoría de la gente sospecha. P aquí significa tiempo polinomial, significa la clase de preguntas que tienen soluciones que se pueden encontrar en tiempo polinomial. NP aquí representa la clase de problemas que no son posibles de resolver en el tiempo polinómico, pero si se les da la respuesta, podrían verificarse en el tiempo polinómico. El campo que estudia esto se llama teoría de la complejidad computacional. Los cuellos de botella son la cantidad de tiempo que la computadora tiene para resolver problemas y la cantidad de memoria que tiene. Actualmente, la mayoría de los investigadores creen que P no es igual a NP, sin embargo, esto es matemática. Las opiniones no importan, solo las pruebas sí. Sin embargo, si P es igual a NP, entonces lo que esto significa para los problemas completos de NP es que son solucionables en tiempo polinómico. La factorización de enteros (aquí números primos) no es NP completa y es NP y co-NP. Estas cosas se llaman clases de complejidad y son parte de la teoría de la complejidad computacional. Básicamente son formas de decir cuán difícil es un problema. Tenga en cuenta que esto no se centra en ningún algoritmo en particular, sino en todos los algoritmos posibles. Desde este punto de vista, la “dureza” de factorizar en números primos es solo una aplicación específica de un problema mucho más general. En la actualidad, la respuesta más precisa que podemos dar depende de dos factores, la cantidad de potencia informática y el mejor algoritmo disponible, los cuales están sujetos a cambios. Si algún genio resuelve el problema P vs NP, entonces tendríamos una respuesta concreta a la pregunta junto con muchos otros problemas computacionales. Personalmente, el autor espera lo mejor de todos los mundos posibles donde tendríamos computadoras cuánticas y también la prueba correcta o la prueba del problema P vs NP. “La esperanza brota eternamente en el seno humano” – Papa.
