Modular exponentiation relatively slow in Pascal

2
votes

I have been developing program in Pascal for generating large primes. After many tries I have successfully (I hope) implemented modular exponentiation using the Montgomery exponentiation algorithm. It is way faster than right-to-left binary method from my tests. I used algorithms from the Handbook of Applied Cryptography chapter 14, because I used http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm for checking mistakes and it is basically the only online calculator for big numbers.

Modular exponentiation of like 100 digit numbers (base,exp,mod) takes roughly 300ms compared to even the javascript version. This feels slow. I have tried using profiling my code and fixed a couple of bottlenecks but it is still pretty slow imo compared to the javascript implementation. Profiling shows that most of the calls are used for basic multiplication (vynasob function) and subtraction (odecti function), but I dont see how those can be made faster. Is it because I represent numbers as base 10 in array? I dont think it is that much of a problem. Here is my code https://github.com/Honzaik/PPrime/blob/master/pprime.lpr If someone was that kind and skimmed through if you find some weird stuff that might help. The code is in Czech sadly tho. But the important functions are:

isPrime = Rabin-Miller

montExp = Montgomery Exponentiation

montMult = Montgomery Multiplication

secti = addition

odecti = subtraction

vynasob = multiplication

vydel = division

modulus = modulus

As I said, I represent numbers as array in base 10. eg 10587 = [7,8,5,0,1]

Thank you for your responses

1
algorithmmathoptimizationprimespascal
side note, you should increase base to maximum possible - Sopel
Why Montgomery multiplication? For such relatively small numbers (100 digits is small, in that context), a simple binary exponentiation is much easier. And indeed, base 2^32 would be a little better. - Rudy Velthuis
@Sopel i thought about that. i will try it out! - honzaik
@RudyVelthuis do you mean exponentiation? I used montgomery exponentiation because according to my testing it was faster than the right-to-left binary method, i implemented it also as function - "modular_pow" but it is slower. i will try out the bigger bases. but i still dont think it should make that much of a difference - honzaik
I actually meant mutliplication (Montgomery modular multiplication, which is only useful on huge values). I confused it with modular exponentiation, which is, IME, quite fast using plain right to left exponentiation, especially for such relatively small values. But using a base of 10 would slow things down considerably. - Rudy Velthuis

1 Answers

1
votes

The answer/advice for improvement is to use biggest base you can. i changed base 10 to base 2097151 and 300ms became 8ms. thank you everyone in comments for advices