View Single Post
Old 2020-08-19, 01:44   #29
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

13·109 Posts
Default

I've found another algorithm to compute g^exponent once you are given all g^(2^k) [mod N]. Turned out it is using more mulmods, but this still depends how efficiently you partition the bits=1 in the exponent.
The problem with the fixed window size is that you are killing those ones not that efficiently (because only half of the bits is one), what about using not fixed size windows? Fix an offset vector: offset=[0,...,], and we're searching shifts t, for that for all i index at offset[i]+t there is a one in exponent, and to get many hits say size(offset)<=14 for our N. We can use an abnormally large window, say offset[i]<2000. Accumulate the product of these x(k)=prod(g^(2^t)), at the end you need to calculate prod(x(k)^e(k)), do now the standard way, collect the product for each 2^h in the exponent e(k), note that e(k)=prod(2^offset[]), so e(k) contains very few bits=1.The complexity of each offset is:
count-1+size(offset) mulmods, where you have count different t shits for the offset, hence its rate:
rate=(count-1+size(offset))/(size(offset)*count)
[you need to lower the rate].

Last fiddled with by R. Gerbicz on 2020-08-19 at 01:55
R. Gerbicz is offline   Reply With Quote