Factorisation de grands nombres
Je suis en train d'essayer de trouver de la complexité de la factorisation de grands nombres.
Qui est le meilleur algorithme et qui est la complexité de trouver un certain nombre de facteurs premiers? Supposons que la longueur du numéro n.
OriginalL'auteur user1391078 | 2012-05-12
Vous devez vous connecter pour publier un commentaire.
Le meilleur savoir algorithme de factorisation d'entiers de plus de 100 chiffres est Général champ numéro de tamis. C'est la complexité est expliqué sur la page vers laquelle le lien renvoie.
Wikipedia a un article intéressant sur d'autres algoritms: http://en.wikipedia.org/wiki/Integer_factorization
OriginalL'auteur Koen Peters
la complexité sera sqrt(n)log(n).Mais pour le n<=19^7 si vous utilisez tamis puis après tamis il peut être fait en log(n).
Vous pouvez voir ici -> http://codeforces.com/blog/entry/7262
OriginalL'auteur Abhishek kumar yadav