Autor
El problema de multiplicar 2 números es un problema de tipo en P (con números de longitud n se necesitan al menos n operaciones, o sea un polinomio. El problema de hallar un factor de un número es un problema NP, porque una solución sugerida puede verificarse en tiempo polinómico. Sin embargo, no se sabe si este problema está en P.
La factorización de un primo es que dado un entero encontrar su factorización en números primos, cada entero tiene una factorización de primos únicos. Multiplicando dos números primoses muy fácil, pero factorizar el producto de dos (o más) números primos es mucho más difícil (a día de hoy).
Un número grande no tiene porque ser más difícil que factorizar que un número pequeño, pero un número cuyos factores primos son grandes si es más difícil de factorizar que uno pequeño (en la mayoría de los casos).
Cualquier par de primos grandes no vale para construir tu sistema de clave pública, debe cumplir una serie de condiciones.
La factorización es en lo que algunos criptosistemas de clave pública basan su seguridad, incluso el algoritmo RSA. La seguridad de RSA depende del problema de la factorización siendo difícil, y se está a la espera de encontrar un método de factorización fácil.
Esto significa que se puede ir hacia un lado (multiplicar dos números primos) pero la operación contraria no es posible (factorizar ese número en los primos). Esto permite (utilizando la trampa que ofrece el teorema de euler) construir un sistema en que lo cifrado con un número(clave pública) sólo puede descifrarse poseyendo el otro número (la clave privada).
Quiero puntualizar algo de los números primos que se dijo en otro post, en el cuál se afirmo que hayar hayar si un número es primo tiene complejidad lineal (siendo x el número de cifras de ese número)
Cita de: thedoctor77
si tienes un numero de 2 cifras pasara exactamente 100 de 3 1000 de 4 10000, eso es LINEAL!!!!!!!!!!!!! por favor no digas estupideces, tio eres un ignorante de la vida, no tienes ni idea de codigo ni cotes ni nada solo te dedicas a generar un conficto tras otro con ideas absudas.
Esto no es lineal, una función lineal es una recta, la diferencia entre n y n+1 es la misma para todo n, en este caso no tenemos una recta tenemos la función 10^n que no es una función lineal (la pendiente no es la misma en todo punto) puesto que la diferencia a nivel de operaciones entre un número de 3 cifras y uno de 4 (10000-1000) no es la misma que entre uno de 2 cifras y uno de 1 cifra (1000-100). Fue un lapsus también mío y acabé diciendo también que eso era lineal (quizás por los insultos y porque para alguien parecía que había dicho la mayor aberración de algo elemental 
, y no quiero generar conflicto con esto)Cuando se trata de encontrar números primos grandes, el tema se complica, pues para un número de 20 dígitos tendríamos 10²° operaciones, y más para números codificados en 128 bits.
Salu2
En línea
