modular exponentiation?

[cyrille de brébisson]

Hello,

>I've never even heard of binary multiplication chains.
>I've certainly heard of powers-of-two multiplication by bit-shifting though.
>I don't know if this is the same thing

Yes, they are. When you do "powers-of-two multiplication by bit-shifting", you do things like:
res= 0
while a!=0
if a is odd then res= res+b
a= a shift right (divide by 2)
b= b+b (or b shift left: multiply by 2)
end

power of 2 power by bit shifting is
res= 0
while a!=0
if a is odd then res= res*b // Note the + changed into a *
a= a shift right (divide by 2) // no changes there
b= b*b // Multiply by 2 changed into a square (the power equivalent of +)
end

So, same algo, different functions...

Where this is interesting and applies to the original "question" is that breaking the power loops allows you to add the modulo function in the innerloop and never end up with large numbers.

The net result is that you will have to perform
sum(ln(n)*1.5) multiplications and modulo calculations (=~8800) assuming that bits are odd with 50% probability...

With some luck your CPU does have a build in / or % function...
The main issue is that you need to do calculations with numbers that can be as big as 10^20 (2 10 digits number being multiplied) which takes 67 bits... and this overflows a 64 bit register :-(
So you will have to create a longer precision arithmetics for the multiplication and modulo...

Cyrille
Cyrille