En términos simples, ¿por qué es difícil factorizar el producto de dos números primos grandes?

Answer 1

Imagínese tratando de factorizar esto:

934857438934857438931234567888764345677654465789999876432213568900988765422367899865433467889999887765434568877887444677786655766647457533685854848455432345676543. en su computadora personal.

Esto ni siquiera es tan grande, en comparación con las grandes claves RSA. Ni siquiera es producto de dos factores primos, golpeé el teclado un poco. Pero puedes ver mi punto.

Su computadora tiene que probar números que matemáticamente puedan ser un factor, pero a medida que el número aumenta, también lo hace el número de números posibles.

Ejemplo:
Factoriza el número 27.

Yo: Comenzaré exactamente a la mitad de eso (no cómo lo haría una computadora, pero el ejemplo demuestra muy bien el problema). Ok, 14. Subiré y bajaré al mismo tiempo para aumentar mis posibilidades de hacerlo bien.

14- no es un factor

15-no es un factor y 13- no es un factor (ambos probaron esta iteración, ambos fallaron)

16-no es un factor y 12-no es un factor (ambos probaron esta iteración, ambos fallaron)

Y así sucesivamente hasta llegar a 9 o 3.

Ahora intenta aplicar ese método al número en la parte superior. Buena suerte. Hay muchas más iteraciones para ejecutar esta vez.

Sugiero que te rindas (a menos que tengas una computadora)

Answer 2

Sí, lleva demasiado tiempo, tiempo en cientos de años o más ( según el número, los números más pequeños no toman tanto tiempo ). El producto de dos grandes números primos también se conoce como semiprimes. Es relativamente fácil construir [1] tal número que tomaría más tiempo que la edad conocida del universo para ser factorizado en las computadoras actuales usando algoritmos actuales. Y existe una complejidad de hardware y software para administrar tales números.

Esto condujo al RSA Factoring Challenge por parte de RSA Laboratories el 18 de marzo de 1991 para alentar la investigación en la teoría de números de cómputo y la práctica difícil de factorizar enteros grandes y descifrar claves RSA utilizadas en criptografía.

A continuación se muestra la lista abreviada de los números RSA (semiprimes que son parte del desafío de Factoring RSA) que se factorizó por primera vez, el último número más grande factorizado y el número RSA más grande de la lista. Para obtener una lista completa, consulte RSA Factoring Challenge – Wikipedia

El mayor número factorizado hasta ahora bajo el desafío RSA es RSA-768 [2] [3] como se muestra a continuación.

El tiempo de CPU empleado para encontrar estos factores mediante una colección de computadoras paralelas ascendió aproximadamente al equivalente de casi 2000 años de computación en una computadora de un solo núcleo AMD Opteron de 2.2 GHz.

Ahora imagine factorizar RSA-2048 [4]

Una analogía para entender el problema de la factorización sería imaginar transportar una enorme roca imaginaria dos veces más grande que la construcción del estado del imperio, que solo se puede romper en dos piezas de ajuste y no más debido a sus propiedades materiales.

Si pudiéramos romper la roca imaginaria en más de 2 piezas, podríamos transportar las piezas más pequeñas una por una. Sin embargo, transferir la pieza del tamaño de Empire State Building requiere muchos más recursos y tiempo.

Notas al pie

[1] Factor primo – Wikipedia

[2] Números RSA – Wikipedia

[3] http://eprint.iacr.org/2010/006.pdf

[4] Números RSA – Wikipedia

Answer 3

Supongamos que tenemos un número N. Si hemos dado una factorización en primos [matemática] p_1, p_2,…., P_r [/ matemática], entonces es relativamente fácil comprobar que sí es una factorización: solo calcula el producto de los números primos y verifique si es igual a N.

Sin embargo, crear los primos en sí es a priori no trivial, ya que cualquier número entre 2 y [math] \ sqrt {N} [/ math] es a priori un divisor. Este es un ejemplo de un problema P = NP. Podemos comprobar fácilmente que una solución propuesta es correcta, pero encontrarla es difícil.

Tenga en cuenta que a veces los problemas P = NP son solucionables. Por ejemplo, si tenemos un sistema lineal [matemática] Ax = y [/ matemática], entonces es fácil verificar que una x propuesta sea una solución. Tampoco es muy difícil resolver realmente el sistema, usar Gauss pivot o una técnica similar. Dado que el problema P = NP no está resuelto, en el sentido más general, no sabemos por qué es difícil factorizar un producto de dos números primos grandes.

Pero la intuición es bastante clara. Si el número N es producto de decir solo primos en [matemática] 2, 3, 5, 7, 11, 13, 17 [/ matemática], entonces el problema es bastante fácil de resolver: solo considere cada primo por turno. Por lo tanto, cuando tenemos dos números primos grandes, es la peor situación ya que los números primos pueden ser realmente grandes. Dichos números se denominan Semiprime.

Answer 4

Desafío. Dime qué es 19 * 61. Fácil verdad? Ahora dime los dos números que cuando se multiplican dan 1541. Eso es mucho más difícil porque hay muchos cálculos que debes realizar y todos menos 2 darán como resultado la respuesta correcta de 67 y 23. Sin embargo, cuando multiplicas es una serie de sumas que Llevar a responder fácilmente. Es decir, 67 x 23 = (3 × 7) + (3 × 60) + (20 × 70) + (20 × 60). Eso se compara fácilmente con multar los factores de 1541. Es fácil de multiplicar y difícil de factorizar.

Así que hemos establecido que factorizar es mucho más difícil que multiplicar. Bueno, ahora imagínese si un número muy grande dice que 16 dígitos necesitan ser factorizados. Bueno, eso significa que potencialmente necesitarías hacer decenas de millones de cálculos para encontrar la respuesta. Esta es la razón por la cual encontrar el producto de un semi primo, el producto de 2 números primos es increíblemente difícil. Hay muchos cálculos que no dan respuesta. Normalmente, necesitaría hacer hasta la raíz cuadrada de un número, número de cálculos Ie para 679, necesitaría hacer hasta cálculos de raíz cuadrada 679 para encontrar la respuesta necesaria. Estamos adivinando y eliminando de manera sistemática los posibles factores que tardan más cuanto más grande es el semi prime. Entonces sí, lleva mucho tiempo y eso sí, el problema. Es fácil en un sentido y difícil en el otro.

Espero que esto ayude y haya respondido su pregunta. ¡No olvides que puedes votar!

Answer 5

Sí, eso es básicamente lo que queremos decir cuando decimos que factorizar números grandes es difícil. Tenemos métodos para hacerlo, pero incluso los métodos realmente inteligentes son terriblemente ineficientes. (El método de fuerza bruta obvio es muchas veces peor). Verificar billones y billones de casos simplemente no es práctico, incluso para supercomputadoras muy poderosas.

Answer 6

Hay muchos números posibles que podrían ser factores de un número muy grande. Verificar cada uno de ellos lleva mucho tiempo. Los diversos algoritmos de factorización que se han ideado equivalen a formas de verificar un subconjunto más pequeño de los números posibles, pero el mejor de ellos ideado hasta la fecha todavía implica mucho trabajo para un gran número sin factores pequeños.

Answer 7

Es trivial especificar un proceso para factorizar el producto de 2 números primos grandes. El proceso será computacionalmente costoso dependiendo de la magnitud de los números primos.

Es intelectualmente difícil especificar un proceso eficiente .

Esto es cierto para muchos problemas importantes para los que esperamos encontrar algoritmos eficientes en una variedad de campos de la ciencia, las ciencias sociales, la ingeniería, la computación, etc.

Answer 8

Es difícil porque no hay un algoritmo conocido que lo haga rápido. Esa es la única razón.

Siempre se avanza pero el progreso es lento. Los algoritmos se vuelven un poco más rápidos, por lo que utilizamos números que son un poco más grandes para el cifrado.

Si se descubre un algoritmo rápido, ya no llamaríamos difícil a la factorización, pero esto aún no ha sucedido. Entonces sí, simplemente lleva demasiado tiempo. Sabemos exactamente cómo hacerlo.

Answer 9

Estoy trabajando en un algoritmo prometedor para factorizar un producto de dos primos muy grandes (utilizados como claves en software de cifrado como RSA) y mi opinión sobre esto es que debes pensar en formas muy innovadoras para crear algoritmos de alto rendimiento. En mi caso, me alejé de un enfoque de módulo / teoría de grupo / teoría de números elementales, para tratar principalmente con números reales (no enteros) y el teorema del punto fijo en un contexto inusual: aplicado a funciones caóticas, no continuas. Puede leer acerca de mi algoritmo (todavía en progreso, creo que he factorizado números como 395,909,818,831 de manera muy eficiente), en Factoring Massive Numbers: Machine Learning Approach – Why and How.

Answer 10

¿Cuál es la factorización de 15? eso es fácil, ¿verdad? 3 * 5.

para que sirve 91 no es 91 primo? ¿Qué pasa si te digo que no es así? ¿entonces que es? bueno, tienes que adivinar y verificar: no hay una matemática inteligente que puedas hacer para encontrar la factorización del producto de dos números primos grandes.

Answer 11

Actualmente no existe un algoritmo para computadora no cuántica que resuelva la factorización de enteros en tiempo polinómico, el mejor (GNFS) es sub-exponencial. No sabemos si realmente existe un algoritmo de tiempo polinómico para hacerlo (en cualquier caso, no se demostró que no existe).

Entonces, a menos que tenga un mainframe realmente rudo, la tarea de factorizar semiprimes suficientemente grandes se vuelve ardua.

Answer 12

Es difícil porque nadie ha encontrado una manera fácil de hacerlo. Sin embargo, eso no significa que no exista una manera fácil, tal vez haya una forma que no hayamos descubierto. Se han encontrado mejoras, pero sigue siendo un proceso muy lento.

Como no se ha demostrado que no se esconda una manera fácil en alguna parte, existe la preocupación de que se pueda encontrar una manera. Y eso es un problema porque algunos sistemas de cifrado dependen de que la factorización sea difícil. Si alguien encuentra un atajo importante para factorizar, algunos algoritmos de cifrado importantes serán repentinamente inútiles. Pero las personas han estado buscando una manera fácil durante milenios y aún no han encontrado una.

Answer 13

En términos simples, debe preguntarse por qué factorizar el producto de dos números primos es difícil en comparación con qué. Compara la multiplicación con la factorización. La producción del producto de dos grandes números primos es relativamente fácil, ya que tenemos procedimientos bien definidos para hacerlo. Factorizar tal producto es relativamente más difícil ya que tenemos procedimientos menos bien definidos para hacerlo.