J'ai développé un programme en Pascal pour générer de grands nombres premiers. Après de nombreux essais, j'ai réussi (j'espère) à mettre en œuvre une exponentiation modulaire en utilisant l'algorithme d'exponentiation de Montgomery. Il est bien plus rapide que right-to-left binary method de mes tests. J'ai utilisé des algorithmes du Handbook of Applied Cryptography chapter 14, parce que j'ai utilisé http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm pour vérifier les erreurs et c'est essentiellement la seule calculatrice en ligne pour les grands nombres.Exponentiation modulaire relativement lente en Pascal
L'exponentiation modulaire de nombres à 100 chiffres (base, exp, mod) prend environ 300ms par rapport à la version javascript. Cela semble lent. J'ai essayé d'utiliser le profilage de mon code et j'ai corrigé quelques goulots d'étranglement mais il est encore assez lent par rapport à l'implémentation javascript. Le profilage montre que la plupart des appels sont utilisés pour la multiplication de base (fonction vynasob) et la soustraction (fonction odecti), mais je ne vois pas comment ils peuvent être accélérés. Est-ce parce que je représente les nombres en tant que base 10 dans le tableau? Je ne pense pas que c'est vraiment un problème. Voici mon code https://github.com/Honzaik/PPrime/blob/master/pprime.lpr Si quelqu'un était de ce genre et a parcouru si vous trouvez des trucs bizarres qui pourraient aider. Le code est malheureusement en tchèque. Mais les fonctions importantes sont:
isPrime = Rabin-Miller
montExp = Montgomery Exponentiation
montMult = Montgomery Multiplication
secti = addition
odecti = subtraction
vynasob = multiplication
vydel = division
modulus = modulus
Comme je l'ai dit, je représente des nombres comme tableau dans la base 10. par exemple 10587 = [7,8,5,0,1]
Merci pour vos réponses
note de côté, vous devriez augmenter la base au maximum possible – Sopel
Pourquoi multiplier Montgomery? Pour de tels nombres relativement petits (100 chiffres est petit, dans ce contexte), une simple exponentiation binaire est beaucoup plus facile. Et en effet, la base 2^32 serait un peu mieux. –
@Sopel j'ai pensé à ça. je vais l'essayer! – honzaik