Low Weight Subsequences

masser · 2007-01-28, 03:34

Currently, srsieve breaks up our sequences of interest into many subsequences. With one of the commandline options on srfile, the exponent sequence is displayed. Would it be possible to add a commandline option that would print the exponent forms for the subsequences AND counts for that sequence?

What I'm thinking is that if there are some extremely low-weight subsequences it might be possible to get rid of those subsequences (by testing or P-1 factoring) and thus speed up the overall project sieve.

geoff · 2007-01-31, 05:08

Quote:

Originally Posted by masser

Currently, srsieve breaks up our sequences of interest into many subsequences. With one of the commandline options on srfile, the exponent sequence is displayed. Would it be possible to add a commandline option that would print the exponent forms for the subsequences AND counts for that sequence?

In srfile version 0.6.5 you can use this command:

srfile -c X input.txt

to get the length of each modulo X subsequence in input.txt. X should be the value that the sieve reports in `split S base B sequences into T base B^X subsequences'.

michaf · 2007-01-31, 09:35

If I understand it correctly, you will try to eliminate the 243 values of n in

204394*5^n-1: n = 16*m+11, 7509 terms
with n = 51 (mod 60): 243 terms

to eliminate the n=51 case of 204394, which is about 1/1800th of the total of cases?

If I understand this correctly, it will only very marginally speed things up

However, I might be terribly wrong

masser · 2007-01-31, 14:54

I was expecting the minimum sequence to be a little smaller. I thought that if there were several subsequences with less than about 50 n remaining, we could test out those subsequences and see a boost.

Actually it might be fun anyway to test out some of the lowest weighted subsequences... get some timing results for PRP tests at n = 2 million, speed up the overall sieve marginally...

michaf · 2007-01-31, 15:04

I'm in for a little challenge... is there a way to create a list of those numbers?
(204394*5^n-1: n = 16*m+11 with n = 51 (mod 60): 243 terms)?

masser · 2007-01-31, 15:07

You could do it with Excel or Gnumeric (on linux)... it's a little bit of work that way. Maybe Geoff has a trick he knows of...

tnerual · 2007-01-31, 16:59

don't forget that PRP don't remove k/n pair from the sieve file ... the sieve file contain a lot of allready prp'ed value.

so if you want to remove a subsequence, you have to find factors.

but factors are comming very slow:

for exemple i sieved my k (285728) up to 15000 *10^9 (15T i think) and now i find 2 factors every day (amd x2-4200, one core sieving) and there is only 5 subsequences. PRP give exactly the same rate (2 test a day per core, at n= 740000)

one possible attack is p-1 factoring of the lowest weighted sequence. i know that some people love p-1 factoring.

but first we need to know the top 10 of the "lowest weighted subsequence"

michaf · 2007-01-31, 18:17

I think we would remove them if they are double-checked prp.
And 2 tests per day isn't too bad, since we 'only' need to do some 250 of them
(if no factors are found).
(say that around 2M it will take 2 days per test, still doable)

tnerual · 2007-01-31, 20:18

Quote:

Originally Posted by michaf

I think we would remove them if they are double-checked prp.
And 2 tests per day isn't too bad, since we 'only' need to do some 250 of them
(if no factors are found).
(say that around 2M it will take 2 days per test, still doable)

riesel is allready "doubleprped" up to 60000 but k/n pair are still in the dat files. removing those pair will give a smaller dat file but will not improve speed (or very marginally).

and yes 250 test is doable

michaf · 2007-02-01, 10:55

Those number which were prp'd once were left in only to accomodate the double-checking effort. (otherwise we would need to do the sieving once again).
Also, when sieving now eliminates a prp'd value, it will thereby eliminate the need for a double-check.

All of these that have been double-checked can be removed, but this has not been done, since it only marginally speeds up the sieving process.

Hmm... upto 60k double-checked... that is now 3%... More then marginally now, maybe we should delete them now.

michaf · 2007-02-01, 22:32

First result:
204394*5^202251-1 has a factor: 159148635697417

(I am running ECM with B1=1000 and B2=100000 10 curves and P-1 with B1=10000 and B2=100000 on every number (which have not been prp'd yet))
If those parameters are way off, let me know please :>

2007-01-28, 03:34	#1
masser Jul 2003 wear a mask 2×7×109 Posts	feature request Currently, srsieve breaks up our sequences of interest into many subsequences. With one of the commandline options on srfile, the exponent sequence is displayed. Would it be possible to add a commandline option that would print the exponent forms for the subsequences AND counts for that sequence? What I'm thinking is that if there are some extremely low-weight subsequences it might be possible to get rid of those subsequences (by testing or P-1 factoring) and thus speed up the overall project sieve.

2007-02-01, 22:32	#11
michaf Jan 2005 479 Posts	First result: 2043945^202251-1 has a factor: 159148635697417 (I am running ECM with B1=1000 and B2=100000 10 curves and P-1 with B1=10000 and B2=100000 on every number (which have not been prp'd yet)) If those parameters are way off, let me know please :> Last fiddled with by michaf on 2007-02-01 at 22:34*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
New low weight project	Citrix	Riesel Prime Search	54	2014-01-08 23:55
High weight k's	kar_bon	Riesel Prime Data Collecting (k*2^n-1)	26	2013-09-11 23:12
Generating Low-Weight Ks	henryzz	Riesel Prime Search	9	2012-04-09 21:36
Low weight k's	kar_bon	Riesel Prime Data Collecting (k*2^n-1)	18	2010-05-14 08:49
Low Weight 15k	Citrix	15k Search	20	2004-06-20 21:00

2007-01-31, 09:35	#3
michaf Jan 2005 479 Posts	If I understand it correctly, you will try to eliminate the 243 values of n in 2043945^n-1: n = 16m+11, 7509 terms with n = 51 (mod 60): 243 terms to eliminate the n=51 case of 204394, which is about 1/1800th of the total of cases? If I understand this correctly, it will only very marginally speed things up However, I might be terribly wrong

2007-01-31, 14:54	#4
masser Jul 2003 wear a mask 2×7×109 Posts	I was expecting the minimum sequence to be a little smaller. I thought that if there were several subsequences with less than about 50 n remaining, we could test out those subsequences and see a boost. Actually it might be fun anyway to test out some of the lowest weighted subsequences... get some timing results for PRP tests at n = 2 million, speed up the overall sieve marginally...

2007-01-31, 15:04	#5
michaf Jan 2005 479₁₀ Posts	I'm in for a little challenge... is there a way to create a list of those numbers? (2043945^n-1: n = 16m+11 with n = 51 (mod 60): 243 terms)?

2007-01-31, 15:07	#6
masser Jul 2003 wear a mask 2·7·109 Posts	You could do it with Excel or Gnumeric (on linux)... it's a little bit of work that way. Maybe Geoff has a trick he knows of...

2007-01-31, 16:59	#7
tnerual Oct 2006 7×37 Posts	don't forget that PRP don't remove k/n pair from the sieve file ... the sieve file contain a lot of allready prp'ed value. so if you want to remove a subsequence, you have to find factors. but factors are comming very slow: for exemple i sieved my k (285728) up to 15000 *10^9 (15T i think) and now i find 2 factors every day (amd x2-4200, one core sieving) and there is only 5 subsequences. PRP give exactly the same rate (2 test a day per core, at n= 740000) one possible attack is p-1 factoring of the lowest weighted sequence. i know that some people love p-1 factoring. but first we need to know the top 10 of the "lowest weighted subsequence"

2007-01-31, 18:17	#8
michaf Jan 2005 479₁₀ Posts	I think we would remove them if they are double-checked prp. And 2 tests per day isn't too bad, since we 'only' need to do some 250 of them (if no factors are found). (say that around 2M it will take 2 days per test, still doable)

2007-02-01, 10:55	#10
michaf Jan 2005 479 Posts	Those number which were prp'd once were left in only to accomodate the double-checking effort. (otherwise we would need to do the sieving once again). Also, when sieving now eliminates a prp'd value, it will thereby eliminate the need for a double-check. All of these that have been double-checked can be removed, but this has not been done, since it only marginally speeds up the sieving process. Hmm... upto 60k double-checked... that is now 3%... More then marginally now, maybe we should delete them now.