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.

Checked those 480780, 100622 numbers. Turned out that it is using more multiplications, I counted every mults, and to get the final product from the y[] array you also need mults. I mean this is not that a big surprise, for the old/known powmod problem your signed representation could be a winner, but this is a slightly different problem.
Counted 104979 mults for your method but using E=13, and 106085 for E=12.
[I have 104341 for my method with E=13].
Actually when you first hit a given entry in the y[] array then you can do only a (fast) set and not a mult, so that is smaller than 100622 mults (in my method you can also do this trick). And for the exponents (for E=12) yes it is true that  2^(E+1)< exponent <2^(E+1) but since in the signed representation you don't see two consectuive nonzero term the sharper inequality holds:
abs(exponent)<=2^E*4/3 (just sum 2^E,2^(E2),2^(E4) etc.)
even with these tiny improvements you lost (at least for this given fixed N), but likely in the general case also.