bbb120

[R. Gerbicz]

Originally Posted by paulunderwood

I recall this method... for example: N=(1001111011)_2 can be written as (10[10000-1][100-1])_2. The former takes 9S + 6M and the latter takes 9S + 2M +2D (where S=squaring, M=mult by base and D=div by base). I don't think I have it quite right

No.

Say you are using k=3 in the method (k depends on length of the exponent),
then precompute x^3,x^5,x^7 mod n

See your N=(1001111011)_2 exponent

with 5 squaring get x^32, at this point you have processed the 100000_2 part in the exponent.
Now multiple this by x^(111_2)=x^7 to get x^39.
With 3 more squaring you get x^312.
Multiple this by x^(101_2)=x^5 to get x^317
With one more squaring you get x^634,
multiple this by x^(1_2)=x^1 to get x^635=x^N mod n. (all above computations are done in mod n).

If the length of the exponent is L, then with random exponent you need L squaring and only approx L/4 multiplication,
what is a good gain over the extra cost's standard L/2 multiplication (because half of the digits is 1).

Ofcourse there is an optimal k value for L, but the size of memory could also limit this k value (you need to store x^3 mod n,.. in the array). Also notice that you need 2^(k-1) multiplications to build up the precomputed array.