¿Cuál es el algoritmo de factorización de números final (en números primos)?

Answer 1

No existe tal algoritmo definitivo. No sabemos cuál es la mejor complejidad posible para la factorización (independientemente de P vs NP) y estamos bastante seguros de que aún no la hemos encontrado.

Creo que casi todos en el campo se sorprenderían mucho si los algoritmos actuales son tan buenos como es posible.

Más importante aún, tenemos diferentes algoritmos de factorización con diferentes características de rendimiento.

Tenemos un tamiz de campo de número general que actualmente es el algoritmo más rápido para factorizar números muy grandes en el peor de los casos. Funciona bien para cualquier número (las potencias principales requieren un caso especial adicional).

Sin embargo, tenemos muchos otros algoritmos de facorización. Tenemos un tamiz cuadrático que es más rápido para números de menos de 100 dígitos decimales.

Tenemos algoritmos que funcionan mejor cuando hay un factor primo pequeño. Tenemos algoritmos que funcionan mejor cuando tenemos dos factores primos similares en tamaño y muchos más algoritmos que funcionan mejor en números de alguna forma especial de interés.

Answer 2

Como ya dijo Meir Maor, no existe tal algoritmo. Recuperar primos inferiores, con un tamiz es una buena opción o tal vez un método recursivo ([matemática] \ operatorname {facrec} (p, \ text {current factor string = 1}) = \ begin {cases} \ text {si p es cadena de factor actual de retorno principal} \ times p \\ \ text {else return} \ operatorname {facrec} (\ frac {p} {\ xi}, \ text {cadena de factor actual + “} \ times \ xi \ text {“} \ end {cases} \ mid \ xi \ text {es el factor primo más pequeño de p} [/ math]), pero creo que hay números donde es más fácil demostrar que no hay primos que encontrar un primo Sin embargo, me gustaría agregar un algoritmo teórico: el algoritmo de Shor podría ser bastante rápido una vez que tengamos una computadora cuántica: