Hace más de 2000 años, Euclid mostró que cada número tiene exactamente una factorización principal, que podemos pensar como una clave secreta.
Resulta que la factorización principal es un problema fundamentalmente duro.
Aclaremos, lo que queremos decir con facilidad y dificultad, mediante la introducción de lo que se denomina complejidad del tiempo.
Todos hemos multiplicado los números antes y cada uno de nosotros tiene nuestras propias reglas para hacerlo con el fin de acelerar las cosas.
Si programamos una computadora para multiplicar los números, puede hacerlo mucho más rápido que cualquier otro humano.
Aquí es un gráfico que muestra el tiempo necesario para que un ordenador multiplique dos números.
Y, por supuesto, el tiempo necesario para encontrar la respuesta aumenta a medida que los números son más grandes.
Tenga en cuenta que el tiempo de cálculo se mantiene bien bajo un segundo, incluso con números bastante grandes.
Por lo tanto, es fácil de realizar. Ahora comparemos esto con la factorización principal.
Si alguien te dijo que encuenteras la factorización principal de 589, notará que el problema se siente más difícil.
No importa cuál sea su estrategia, necesitará un poco de prueba y error hasta que encuentre un número, que divide de forma pareja 589.
Después de un poco de lucha, encontrarás 19x31 es la factorización principal.
Si te dijeron que encontrara la primera factorización de 437,231, probablemente te rendirías y recibirías un ordenador para ayudarte.
Esto funciona bien para los números pequeños, pero si tratamos de tener un factor más grande y más grande hay un efecto fugiente.
El tiempo necesario para realizar los cálculos aumenta rápidamente, ya que hay más pasos implicados.
A medida que los números crecen, el ordenador necesita minutos, y luego horas,
y, eventualmente, requerirá cientos o miles de años para tener un gran número de números.
Por lo tanto, decimos que se trata de un problema difícil, debido a esta tasa de crecimiento del tiempo necesario para resolverlo.
Así que la factorización es lo que Cock usó para construir la solución de la puerta trampa.
Paso 1: Imagina que Alice haya generado de forma aleatoria un número primo de más de 150 dígitos, llame a este P1.
A continuación, un segundo número primo aleatorio aproximadamente del mismo tamaño, llame a este P2.
A continuación, multiplique estos dos primarios juntos para obtener un número compuesto N, que tiene más de 300 dígitos de longitud.
Este paso de multiplicación tardará menos de un segundo, incluso podría hacerlo en el navegador web.
Luego toma la factorización de N, P1xP2, y la esconde.
Ahora, si le da a N a alguien más, ellos tendrán que tener un ordenador funcionando durante años para encontrar la solución.
Paso 2: Cocks necesitaba encontrar una función que dependa de conocer la factorización de N.
Para ello, volvió a trabajar en 1760 por el matemático suizo Leonard Euler.