Qual é o algoritmo de factorização prime mais rápido até à data?

A resposta é: depende. Assuma que você're deu uma entrada arbitrária que não't tem alguma forma especial. O algoritmo mais eficiente é uma receita que utiliza algoritmos individuais de factoring. Estas são todas as possibilidades:

Para entradas muito pequenas, use a divisão experimental por primes (ou uma roda para se aproximar sem ter que ter ou gerar primes). Isto funciona melhor a ~1M, dependendo das implementações. Algumas divisões trial são sempre uma boa idéia para remover pequenos fatores.

Pollard Rho funciona muito bem. Como a entrada fica maior (por exemplo > 2^32 mas menos de 2^64), SQUFOF normalmente funciona mais rápido.

Após maior que 2^64, Pollard Rho ainda pode valer um pouco de tempo para encontrar fatores pequenos, mas P-1 e ECM melhor quando se procura mais fundo.

Peneira Quadrática normalmente é melhor começar em algum lugar na faixa de 30-40 dígitos e continuar até 95-105 dígitos.

Após isso, NFS (GNFS) é o algoritmo mais eficiente.

=================================================

Nota que além de pequenas entradas, o método mais eficiente é' não apenas para escolher uma delas e executá-la, mas para passar por uma seqüência. Precisamos também de um teste de primalidade eficiente, que é outro tópico. Por exemplo, dado um número arbitrário de 150 dígitos, a melhor coisa a fazer não é apenas começar a executar o NFS. Devemos remover pequenos divisores -- primeiro por divisão de teste (talvez com um GCD rápido, ou árvore restante, ou apenas um teste de divisibilidade), depois usando os algoritmos que são eficientes para encontrar pequenos divisores: Pollard Rho, P-1, e ECM. Estes encontrarão de forma eficiente pequenos divisores (no caso do ECM's pode ser "pequeno" com mais de 20 dígitos!). Por que se preocupar com o Rho e P-1 se o ECM é mais eficiente a longo prazo? Porque uma pequena tiragem de Rho ou P-1 é normalmente mais rápida que o ECM se os divisores forem pequenos. Algumas pessoas não se importam com essa otimização e irão direto para o ECM (observando que como você executa ECM em termos de tamanho e número de curvas acaba sendo uma discussão similar), e as implementações são importantes.

Após você'execute "enough" P-1 / ECM, e o número que você ainda tem que processar é composto, então você escolhe QS ou NFS.

Para o caso sub-128-bit, eu posso dar o exemplo do fator GNU de Grandlund e Möller's. Ele faz divisão experimental por pequenos primes seguidos por Pollard Rho ou SQUFOF. Perl/ntheory é mais complicado, usando mais algoritmos e mais otimização para pequenos inputs.

Para inputs maiores, yafu é um programa de factoring de última geração. Ele começa com a divisão experimental, faz um pequeno Pollard Rho, depois começa a misturar P-1 e ECM em uma seqüência de tamanhos e curvas que funcionam bem em média, depois escolhe QS ou NFS com base no tamanho de entrada restante e no ponto de cruzamento medido para a máquina. Isto basicamente segue o que eu descrevi.