Ich habe Programm in Pascal entwickelt, um große Primzahlen zu erzeugen. Nach vielen Versuchen habe ich erfolgreich (hoffe ich) die modulare Potenzierung mit dem Montgomery-Exponentierungsalgorithmus implementiert. Es ist viel schneller als right-to-left binary method von meinen Tests. Ich habe Algorithmen aus der Handbook of Applied Cryptography chapter 14 verwendet, weil ich http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm für die Überprüfung von Fehlern verwendet habe und es ist im Grunde der einzige Online-Rechner für große Zahlen.Modulare Exponentiation relativ langsam in Pascal
Modulare Exponentiation von 100-stelligen Zahlen (Basis, Exp, Mod) dauert etwa 300ms im Vergleich zu selbst die Javascript-Version. Das fühlt sich langsam an. Ich habe versucht, meinen Code zu profilieren und ein paar Engpässe behoben, aber es ist immer noch ziemlich langsam imo im Vergleich zu der Javascript-Implementierung. Profiling zeigt, dass die meisten Aufrufe für die Grundmultiplikation (Vynasob-Funktion) und Subtraktion (Odecti-Funktion) verwendet werden, aber ich sehe nicht, wie diese schneller gemacht werden können. Liegt es daran, dass ich Zahlen als Basis 10 in Array darstelle? Ich denke nicht, dass es so ein Problem ist. Hier ist mein Code https://github.com/Honzaik/PPrime/blob/master/pprime.lpr Wenn jemand diese Art war und magerte durch, wenn Sie einige seltsame Sachen finden, die helfen könnten. Der Code ist in Tschechisch leider tho. Aber die wichtigen Funktionen sind:
isPrime = Rabin-Miller
montExp = Montgomery Exponentiation
montMult = Montgomery Multiplication
secti = addition
odecti = subtraction
vynasob = multiplication
vydel = division
modulus = modulus
Wie gesagt, ich vertrete Zahlen als Array in der Basis 10 zB 10587 = [7,8,5,0,1]
Vielen Dank für Ihre Antworten
Randnotiz, sollten Sie die Basis auf maximal möglich erhöhen – Sopel
Warum Montgomery Multiplikation? Für solche relativ kleinen Zahlen (100 Ziffern sind in diesem Zusammenhang klein) ist eine einfache binäre Exponentiation viel einfacher. Und tatsächlich wäre Base 2^32 ein wenig besser. –
@Sopel Ich dachte darüber nach. Ich werde es ausprobieren! – honzaik