Il y a donc quelques applications de la théorie des nombres où nous devons faire des modulo avec de grands nombres, et nous pouvons choisir le module. Il y a deux groupes qui peuvent obtenir d'énormes optimisations: Fermat et Mersenne.Fermat vs Mersenne comme module
Appelons donc une séquence N bits un fragment. N n'est souvent pas un multiple de la taille des mots. Pour Fermat, nous avons M = 2^N + 1, donc 2^N = -1 mod M, donc nous prenons les morceaux du dividende et alternativement en ajoutant et en soustrayant.
Pour Mersenne, nous avons M = 2^N-1, donc 2^N = 1 mod M, donc nous somme les morceaux du dividende.
Dans les deux cas, nous finirons probablement avec un nombre qui prend 2 morceaux. Nous pouvons appliquer à nouveau cet algorithme si nécessaire et enfin faire un algorithme modulo général. Fermat rendra le résultat plus petit en moyenne en raison de l'addition et de la soustraction alternées. Un résultat négatif n'est pas un calcul coûteux, il suffit de suivre le signe et de le corriger dans l'étape finale du modulo. Mais je pense que la soustraction de bignum est un peu plus lente que l'addition de bignum. Mersenne résume tous les morceaux, donc le résultat est un peu plus grand, mais cela peut être résolu avec une deuxième itération de l'algorithme à côté de sans coût supplémentaire.
Donc, à la fin, qui est plus rapide?
Schönhage–Strassen uses Fermat. Il pourrait y avoir d'autres facteurs autres que les performances qui font Fermat mieux que Mersenne - ou peut-être il est tout droit vers le haut plus vite.