Mais um blog inútil.

Há quase 3 anos, bloguei sobre este assunto, e dei uma lista mais ou menos completa sobre as aplicações de factorização existentes.

O que mudou de há 3 anos para cá? Não muito.

A única aplicação que sofreu alterações significativas foi o msieve. Muito pela positiva. Foi-lhe acrescentado um módulo para SNFS/GNFS; embora a escolha de polinómios e o 'siever' não se comparem com os do Franke/Kleinjung (incluídos no GGNFS), o pós-processamento das relações é de longe superior ao do GGNFS. Note-se, no entanto, que para a raiz quadrada final o algoritmo utilizado pelo GGNFS (Montgomery/Nguyen) é bastante superior ao quase brute-forcing do msieve. Na prática não faz grande diferença excepto para números demasiado grandes para factorizar sem ter altos clusters.

A codebase do msieve também foi recentemente integrada no GGNFS; provavelmente daqui a algum tempo vamos ter apenas uma ferramenta para factorizar números, a partir destas duas.

Quero também mencionar as ferramentas "profissionais" para factorizar números. Completas só temos 2, talvez 3:

- Franke/Kleinjung

- CWI Suite

- Aoki et al.

A primeira é, tanto quanto sabemos, a melhor. Foi com ela que foram batidos todos os últimos recordes, e usa os truques todos da moda algorítmicos e tem código MPI especializado para correr em sistemas _grandes_.

A suite da CWI foi durante muito tempo a melhor, e tem código original de muitos dos gajos que desenvolveram a NFS, mas está montes de desactualizada em termos de código.

Nunca consegui olhar para as sores da suite do Aoki, mas supostamente estaria ao nível da primeira; ninguém sabe. Japs...

Para concluir, as aplicações opensores têm evoluído muito recentemente e estão ao nível das melhores neste momento. Excepto quando estamos a trabalhar com clusters/grids, onde não existe quase paralelização nenhuma (o msieve torna a solução da matriz threaded, mas podia ser muito melhor...)

Note-se que estou aqui a tratar de factorização de números "difíceis", isto é, que só têm 2 factores e ambos grandes. Para factorizar números "normais" recomendo o GMP-ECM, que para números com múltiplos factores pequenos é muito superior (o tempo médio do ECM depende do tamanho dos factores e não do número, ao contrário do NFS).