Quote:
Originally Posted by bsquared
Doing the recoding first on our 1442080bit exponent reduces the number of nonzero bits from to 720737 (one bits) to 480780 (one or minusone bits).
Then doing the sliding window algorithm on the recoded exponent results in 100622 muls (plus precomputation). Those multiplications will range over elements x^b, 2^13 < b < 2^13, b odd.
So, now that I've written all this down, I see that recoding probably doesn't save much over just doing sliding window. Especially since you need x^1 mod M with recoding.

Searched today exactly that crypto paper, thanks.
I'll check it.