View Single Post
Old 2013-08-14, 22:12   #10
Citrix
 
Citrix's Avatar
 
Jun 2003

30568 Posts
Default

Quote:
Originally Posted by Thomas11 View Post
I agree with you that while looking for small weights one should try to keep the k as small as possible to benefit from faster LLR testing.

However, I must admit that I don't understand the explanation of your approach.

You say you're taking k<2^18, which is just k<262144 - pretty small. But there are no really low weight Ks in the interval, only a few have Nash weights < 100, the lowest weight being 29 for k=138847 - about 100 times larger than the 1/4 you mentioned.

Then you write:
k1=k*2^1
k2=k*2^2
...
which leaves k essentially unchanged. It's just a cycling through the n. k1, k2, ... all have the same weight (in practise: more or less, since the n range is shifted to higher n due to the multiplier 2^i).

Then you mention the covering set for 2^5760-1.
Given the divisors of 5760 (= 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30, 32, 36, 40, 45, 48, 60, 64, 72, 80, 90, 96, 120, 128, 144, 160, 180, 192, 240, 288, 320, 360, 384, 480, 576, 640, 720, 960, 1152, 1440, 1920, 2880, 5760), this means a huge covering set, leading to k much larger than 64 bits or even 128 or 256 bits.
Or did you mean a covering set of length 5760 (=2^7 * 3^2 * 5)? This, on the other hand, would be too small.

Most likely I missed some essential part of your idea.

Perhaps, if you would post a few of the Ks generated by your procedure, I could find out what I'm missing...
1) Take k <262144 (This is the cut off LLR starts taking more time on my computer)

2) The more k's you test, the more likely you are to find a small weight k

3) using the covering set of just 3 there are 2 kinds of k--> 1/2 the candidates are divisible by 3 or no candidate is divisible by 3 (where k is a multiple of 3). If you tested up to n=10000 then you get weights of 5000, 10000

4) Now using a covering set of 3, instead of using base 2.. you go to base 4, but test only to n=5000.
you have 262144*2 k's. (as all k's less than 262144 and these k*2; ie k1=k & k2=k*2)

5) If a k is not a multiple of 3, then for k1 and k2 you will either get 0 or the weight that would be the same for base 2.
For numbers that are multiples of 3.. you generated 2 new k weights. for k1 and k2


Repeating the above process for the covering set of 2^5760-1
{3, 5, 7, 11, 13, 17, 19, 31, 37, 41, 61, 97, 163, 193, 271, 541, 641, 769}

you can generate k that have low weight but are to be tested for base=2^5760.

Then you can sieve up to 1200 to get an approximate nash weight. But given the extremely small weight of these k, you increase the n=1000000

Here are the numbers I generated with number of candidate remaining. The first 40 have been tested to 2M. The others to 250K.


I hope this makes sense.
Attached Files
File Type: txt Lowk_low weight.txt (12.4 KB, 157 views)
Citrix is offline   Reply With Quote