mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2020-08-06, 18:59   #23
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

63358 Posts
Default

Maybe also relevant to mention that the problem of finding the shortest addition chain for a given binary string is known to be NP-hard (section 14.102 in HOAC). But you'd only have to do it once for a fixed B1.

Last fiddled with by bsquared on 2020-08-06 at 19:00
bsquared is online now   Reply With Quote
Old 2020-08-06, 19:42   #24
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

25708 Posts
Default

Quote:
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
Old 2020-08-06, 20:18   #25
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

57816 Posts
Default

Quote:
Originally Posted by bsquared View Post
we can just use left-to-right sliding windows to get the number of multiplications down to 102989 plus precomputing 2^12 odd multipliers x^b, 1 <= b < 2^k (b odd), using the (optimal) max window size k=13.
Yes, I've used the popular sliding window name, but here there is no such precomputation here. Yeah it is hard to believe there is such an algorithm, because in that sliding window you are actually doing many squaring, so you could not reach less than log2(N)=b multiplications, that is a complexity barrier here. But as I've written with the given x^(2^e) you can reach ~b/2 multiplications if you are using only the bits=1, what is now lower than the barrier. But there is another type of "precomputation" when in y[k] you're accumulating the products you needed to raise to the k-th power.

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 counter-example.
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.
R. Gerbicz is offline   Reply With Quote
Old 2020-08-06, 20:42   #26
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

37·89 Posts
Default

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).
bsquared is online now   Reply With Quote
Old 2020-08-06, 20:58   #27
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

23×52×7 Posts
Default

Quote:
Originally Posted by bsquared View Post
That's a very nice approach. As mentioned, the short addition chain problem is hard.
What addition chains here is now obsolete in the method. See one of my post, the required final task for E=2 to get:
R=y[1]*y[3]^3*y[5]^5*y[7]^7 mod M.
R. Gerbicz is offline   Reply With Quote
Old 2020-08-06, 23:05   #28
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

140010 Posts
Default

Quote:
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.
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 non-zero term the sharper inequality holds:
abs(exponent)<=2^E*4/3 (just sum 2^E,2^(E-2),2^(E-4) etc.)
even with these tiny improvements you lost (at least for this given fixed N), but likely in the general case also.
R. Gerbicz is offline   Reply With Quote
Old 2020-08-19, 01:44   #29
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

23·52·7 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
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Some puzzle Harrywill Puzzles 4 2017-05-03 05:10
Four 1's puzzle Uncwilly Puzzles 75 2012-06-12 13:42
a puzzle bcp19 Puzzles 18 2012-03-02 04:11
Dot puzzle nibble4bits Puzzles 37 2006-02-27 09:35
now HERE'S a puzzle. Orgasmic Troll Puzzles 6 2005-12-08 07:19

All times are UTC. The time now is 16:56.

Wed Sep 30 16:56:03 UTC 2020 up 20 days, 14:07, 0 users, load averages: 2.31, 1.79, 1.75

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.