View Single Post
Old 2020-08-06, 19:42   #24
R. Gerbicz
R. Gerbicz's Avatar
"Robert Gerbicz"
Oct 2005

1,429 Posts

Originally Posted by bsquared View Post
Doing the recoding first on our 1442080-bit exponent reduces the number of non-zero bits from to 720737 (one bits) to 480780 (one or minus-one 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.
R. Gerbicz is offline   Reply With Quote