¿Por qué se considera difícil factorizar enteros grandes?

Leí en alguna parte que el algoritmo más eficiente encontró puede calcular los factores en tiempo, pero el código que he escrito es O ( n ) o posiblemente O ( n log n ) dependiendo de qué tan rápida sea la división y el módulo. Estoy bastante seguro de que he entendido mal algo en alguna parte, pero no estoy seguro de dónde. Esto es lo que escribí en forma de pseudocódigo.$O(\exp((64/9 \cdot b)^{1/3} \cdot (\log b)^{2/3})$$O(n)$$O(n \log n)$

function factor(number) -> list
    factors = new list
    if number < 0
        factors.append(-1)
        number = -number
    i = 2
    while i <= number
        while number % i == 0
            factors.append(i)
            number /= i
        i++
    return factors

Está confundiendo el número con el número de bits necesarios para representar n . Aquí b = el número de bits necesarios para representar n (entonces b ≈ lg n ). Esto hace una diferencia enorme. Un algoritmo de tiempo O ( n ) es un algoritmo de tiempo O ( 2 b ) , exponencial en el número de bits. En comparación, el algoritmo "eficiente" que encontró tiene un tiempo de ejecución subexponencial en b .$n$$n$$b =$$n$$b \approx \lg n$$O(n)$$O(2^b)$$b$

Ejemplo: considere (2 millones). Entonces b = 21 bits son suficientes para representar el número n . Por lo tanto, un algoritmo que es O ( 2 b 1 / 3 ) será mucho más rápido que un algoritmo que es O ( 2 b ) . Un algoritmo O ( n ) cae en la última categoría, es decir, muy lento.$n = 2,000,000$$b=21$$n$$O(2^{b^{1/3}})$$O(2^b)$$O(n)$

Ver https://en.wikipedia.org/wiki/Integer_factorization

Tiene aproximadamente dos preguntas aquí, una general y una específica sobre su código. el específico se maneja en la otra respuesta. La pregunta general en el título sobre la complejidad de la factorización es muy profunda. desafortunadamente no hay evidencia científica sólida de que el factoring esté fuera de P aparte de (la mayoría de las veces circunstanciales) "muchos expertos lo han intentado y fallado" y algunos expertos conjeturan que está dentro de P; Es considerado como uno de los problemas abiertos más importantes (y muy difíciles de resolver) de la teoría de la complejidad. Después de décadas de "ataque pesado", los mejores algoritmos son exponenciales. la complejidad de factorización es uno de los "pocos problemas excepcionales" que se sabe que se encuentra "entre" P y NP completos, pero hasta ahora no se ha clasificado como ninguno.

Como se señaló, la complejidad no fue un gran problema hasta que se utilizó ("aproximadamente") en los criptosistemas RSA a mediados de la década de 1980, donde la seguridad criptográfica depende de la suposición. (otros dos puntos de datos relacionados "no exactamente alentadores": se demostró que el algoritmo Shors para la factorización cuántica del tiempo P y las pruebas de primalidad estaban en P a principios de la década de 2000 en el famoso / famoso algoritmo AKS ). Un posible resultado positivo sería que está en tiempo cuasipolinomial , que es más débil que NP completo (suponiendo que P ≠ NP y NP completo tiene un límite inferior exponencial de tiempo ) pero aún técnicamente "duro".

No he encontrado una gran encuesta sobre este tema clave hasta ahora. sin embargo ver también

• Factorizar puede ser más fácil de lo que piensas / Cohn

• Factorización de enteros de evidencia en P / mathoverflow (mencionando que Sarnak piensa que está en P, y la respuesta de Cohn también)

• "Mundos Impagliazzos, una visión personal de la complejidad promedio de los casos / Impagliazzo. Habla de supuestos / conjeturas teóricas de la complejidad en general relacionadas con la criptografía (por ejemplo, factorización). Muchas / la mayoría de las claves (por ejemplo, P vs NP, etc.) todavía están abiertas después de décadas.