20200806, 18:59  #23 
"Ben"
Feb 2007
3,361 Posts 
Maybe also relevant to mention that the problem of finding the shortest addition chain for a given binary string is known to be NPhard (section 14.102 in HOAC). But you'd only have to do it once for a fixed B1.
Last fiddled with by bsquared on 20200806 at 19:00 
20200806, 19:42  #24  
"Robert Gerbicz"
Oct 2005
Hungary
1429_{10} Posts 
Quote:
I'll check it. 

20200806, 20:18  #25  
"Robert Gerbicz"
Oct 2005
Hungary
1,429 Posts 
Quote:
To get an inside where I've gotten the idea, when you want to multiple by x^63 with the traditional method you need 6 multiplications but with: 1. multiple x and x^4 to get x^5 2. multiple x^5 and x^16 to get x^21 3. square x^21 to get x^42 4. multiple x^21 and x^42 to get x^63 You need only 5, because you need to multiple the partial product by x^63. But now it is already a gain over the classical method. Found this in my head, without computer, and actually this is the smallest counterexample. You can do even better multiple by x^64 and divide by x. Using only 3 mults total. Similar to your method. And here x is NOT fixed, but if you extract those x bases using the given N exponent/residues and see what you need to raise to the k=63 or any power in the window you can save lots of work, what we reached with the optimal E=13. 

20200806, 20:42  #26 
"Ben"
Feb 2007
3,361 Posts 
I see that you are finding a short addition chain using the x^(2^k) elements that will be computed anyway during the test. That's a very nice approach. As mentioned, the short addition chain problem is hard, so I was looking at how other known methods compared. I had thought that exponent recoding gave a larger benefit but after looking closer it is not much better than a standard sliding window. Both of those known methods are not any better than what you have found (but close).

20200806, 20:58  #27 
"Robert Gerbicz"
Oct 2005
Hungary
1,429 Posts 

20200806, 23:05  #28  
"Robert Gerbicz"
Oct 2005
Hungary
1,429 Posts 
Quote:
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. 

20200819, 01:44  #29 
"Robert Gerbicz"
Oct 2005
Hungary
1,429 Posts 
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: count1+size(offset) mulmods, where you have count different t shits for the offset, hence its rate: rate=(count1+size(offset))/(size(offset)*count) [you need to lower the rate]. Last fiddled with by R. Gerbicz on 20200819 at 01:55 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Some puzzle  Harrywill  Puzzles  4  20170503 05:10 
Four 1's puzzle  Uncwilly  Puzzles  75  20120612 13:42 
a puzzle  bcp19  Puzzles  18  20120302 04:11 
Dot puzzle  nibble4bits  Puzzles  37  20060227 09:35 
now HERE'S a puzzle.  Orgasmic Troll  Puzzles  6  20051208 07:19 