6^383+1 by GNFS is complete. Thanks!

fivemack · 2007-12-21, 00:05

I think the present sieving is sufficient, and we're getting to Q values large enough to get diminishing returns; so please don't reserve any more ranges unless you have access to gnfs-lasieve4I15e, and in that case try things in the 20M-25M range.

I think we need 200 million relations; we get slightly under two relations per Q on average, so reservations should be within the range 25M - 140M (initially I estimated slightly over two relations per Q, so an upper limit of 125M, but the drop-off of relations with Q is a bit faster than I expected).

Reservations

Code:

[-5e8,5e8] x [1,2500] linesieve fivemack [completed, 1969966 relations, see discussion below]
 24M - 25M  fivemack @15e [completed, 4130624 relations]
 25M - 30M  fivemack  [completed, 15e sieve, 21039132 relations]
 30M - 55M  smh       [completed, 49516175 relations]
 55M - 60M  fivemack @14e [completed, 9739894 relations]
 60M - 67M  fivemack @14e [completed, 13204459 relations]
 67M - 70M  bsquared  [completed, 5513489 relations]
 70M - 72M  andi47  [completed, 3628344 relations]
 72M - 75M  jhansen   [completed, 5386758 relations]
 75M - 80M  jbristow   [completed, 8814348  relations]
 80M - 86M  andi47     [completed, 10285122 relations]
 86M -100M  akruppa   [completed, 23176554 relations]
100M -120M  akruppa   [completed, 31232260 relations]
120M -122M  fivemack [completed, 3034380 relations]
122M -130M  smh     [completed, 11836672 relations]
130M -132M  bsquared [completed, 2961713 relations]
132M -135M  fivemack @15e [completed, 11921570 relations]
135M -137M  andi47 [completed, 2917655 relations]
137M -138M  fivemack @14e [completed, 1450811 relations]
138M -140M  fivemack @15e [completed, 6274349 relations]

Instructions

To sieve, use

Code:

gnfs-lasieve4I14e -o 55.56 -a 6+383.job -f 55000000 -c 1000000

with '55.56' changed appropriately, -f <start of range> -c <size of range>, and 6+383.job being the file enclosed in the bottom section of this post.

If your computer crashes mid-job, look at the last hex number on the last full line of the output file '55.56', convert it to decimal, and use that as the '-f' when you start again; subtract from '-c' appropriately so that your range ends in the right place.

(ie, if the output file ends

Code:

12571943595,90442:da66c29,648802f,17455,55543,7,2B,47,3,3,B,B:11c54b27,84f9ac1,2A2D7,34565,67553,12B7B9,19CF,148D,5,5,1F,1F3,2,2,34DFF65
-11386617209,23426:72c380b,4371

then you convert 34DFF65 to decimal, getting 55443301, and continue with

Code:

gnfs-lasieve4I14e -o 55a.56 -a 6+383.job -f 55443301 -c 556699

There is a limitation in gnfs-lasieve4 meaning that, if you are sieving a range starting below 50000000, you need to change the 'alim' line in the job file to be the start of your range.

I reckon 1000 Q takes about eight CPU-minutes on a 2.4GHz Core2, so a million takes a bit under a week on one such core.

Uploading
Connect by anonymous FTP to ftp.chiark.greenend.org.uk, then do

Code:

cd special/twomack-relations/esbjerg
binary
put relation.file

The 'esbjerg' directory has special magic properties meaning that it doesn't show up in 'ls', which may confuse some ftp clients, but is apparently necessary to avoid people finding it by looking at random anon-ftp sites then using it as a pirate haven.

As of 00:01 on 02 January 2008, I have in esbjerg completed relation files for 30.0-42.5, 67-70, 72-75 and additionally on my workstation 25-28, 42.5-60.0, 65-67 and 86-120. I need to wait for some new hard drives to arrive before I can decompress and merge everything and get a really good idea of percentage completion, and my supplier's been a bit incompetent: maybe by the 9th?

Collaborators, start your sieves!

6+383 file

Code:

n: 230380135646168002240144238096238189782429580465812519176892278271650463794969643225877877269156894108094881082195219664775471894182470295616143804362949333632033489
skew: 210886.76
c5 11472718320
c4 -3795305047120954
c3 -2612363701552248486716
c2 107677876784557388243547221
c1 33277562211750204806364306268284
c0 547440910672314203689898814059115360
Y1 2391424041494417171
Y0 -7253635851193924156735160443739
rlim: 50000000
alim: 50000000
lpbr: 31
lpba: 31
rlambda: 2.6
alambda: 2.6
mfbr: 62
mfba: 62

If you have any questions, pm me or post on this thread

fivemack · 2007-12-24, 15:45

I should have an upload mechanism in place by New Year - it requires a friend of mine to fiddle about with the filesystem configuration on his colocated machine, which will have to wait until after Christmas, and then you can upload the files by FTP. Until then, if you have web space that you can put files on, I can pull them down without trouble.

akruppa · 2007-12-24, 18:03

The 86M-100M range is finished (looks like no one else is using the Grid5000 clusters over Christmas!), may I take 100M-120M as well? If that's ok, I won't take more than this range as not to jeopardize the collaborative character of this effort.

Alex

fivemack · 2007-12-24, 21:28

That's quite spectacular performance. If I'd known there were resources on that scale available ...

[I'd have done exactly what I'm doing now - what I don't have is the parallel software for a truly-large matrix]

There's no virtue in not applying available resources; go ahead with 100M - 120M.

If you have resources of this scale, I presume 7-269 has already succumbed ... do you feel like sieving 2^841-1

?

(2x^6+1;x-2^140, sp=50M lp=31, q_alg=25M-175M ought to suffice ...)

akruppa · 2007-12-24, 22:04

The problem is predicting availability. Yesterday and today there was almost no one else using the cluster in Bordeaux. That's about 400 Opteron cores I can use. If I use nodes at other locations as well it might be 1000 or more, enough to sieve a decent size project in a day. However, if other users start running their own jobs again I might not get an awful lot of cpu time for weeks. It's a gamble.

I'm not using those machines for NFS very much yet, mostly because I couldn't do all the post-processing work. But if someone else is willing to handle the messy part...

7,269- is sieved and the matrix is running. I'm preparing 3,533- for sieving at the moment. Both are easy enough that I can do the post-processing with the CWI tools I'm familiar with. The sq < 120M for 6^383+1 are finished as well, I'm trying to think of somewhere to put them for download.

If you'll do the filtering and matrix and only need the relations for a bigger project, I'd gladly join and see how much cpu time I can grab. 2,841- is fine with me. Does it need more ECM first?

Alex

fivemack · 2007-12-24, 22:51

Well, I've got a quad-core on order, and might as well go for 8GB memory for it - there are two 2G sticks sitting on my desk at work - at which point 2,841- shouldn't be an impossible filtering and matrix job, though the relations will be a cumbersome amount of data to move around. I don't know how much it's been ECMed, if you're in a position to start ECM tonight and switch to sieving in the morning, that might be the right combination.

Go for it; at worst I'll have to organise another phalanx of mersenneforum people in 2008 to mop up such relations as couldn't be done over xmas on the Grid.

fivemack · 2007-12-28, 21:05

Quote:

Originally Posted by fivemack

I should have an upload mechanism in place by New Year - it requires a friend of mine to fiddle about with the filesystem configuration on his colocated machine, which will have to wait until after Christmas, and then you can upload the files by FTP.

This is now set up; instructions in the head post. Remember to set 'binary' when uploading compressed files. If you have any problems PM me. I have already got 86-120 and 42.5-55, as well (obviously) as the regions I've sieved.

Andi47 · 2007-12-30, 12:20

Just a little statistics:

Code:

relations found so far:          90,508,868
completed size of search range:  52.5 million Q
Relations per Q (average):       1.724

Range          Size        Relations     Relations/Q
 41M5 - 55M    13M5        26360160      1.953
 55M - 60M      5M          9739894      1.948
 86M - 100M    14M         23176554      1.655
100M - 120M    20M         31232260      1.562

smh · 2008-01-01, 20:50

Should we do any line sieving using msieve?

fivemack · 2008-01-01, 23:25

Line sieving might not be a bad idea. I'm not at all sure about parameter choice; (10..90)th-percentile range of A and 5th-percentile range of B is a=-10^10 .. 10^10, b=0..3000, but I've not done line sieving at all so I don't know how long that would take.

jasonp · 2008-01-02, 00:01

Quote:

Originally Posted by fivemack

Line sieving might not be a bad idea. I'm not at all sure about parameter choice; (10..90)th-percentile range of A and 5th-percentile range of B is a=-10^10 .. 10^10, b=0..3000, but I've not done line sieving at all so I don't know how long that would take.

Anyone planning to run line sieving should create an msieve factor base file like normal, then add 'SLINE 1e10' to the list of parameters.

A single line should take maybe a half hour, though very small b (< 100) could take a really long time. The siever will switch dynamically between two and three large primes, and to save time will perform a lot of precomputation up front. I've tested the code with 28-bit large primes but using 31-bit large primes could chew up a lot of memory. Note also that when the polynomial skew is very large then a huge portion of the relations found will be duplicated by the lattice siever, if b is chosen too large

Feel free to PM me any generated logfiles if you'd like me to verify that things are behaving as expected.

2007-12-21, 00:05	#1
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 1936₁₆ Posts	6^383+1 by GNFS is complete. Thanks! I think the present sieving is sufficient, and we're getting to Q values large enough to get diminishing returns; so please don't reserve any more ranges unless you have access to gnfs-lasieve4I15e, and in that case try things in the 20M-25M range. I think we need 200 million relations; we get slightly under two relations per Q on average, so reservations should be within the range 25M - 140M (initially I estimated slightly over two relations per Q, so an upper limit of 125M, but the drop-off of relations with Q is a bit faster than I expected). Reservations Code: [-5e8,5e8] x [1,2500] linesieve fivemack [completed, 1969966 relations, see discussion below] 24M - 25M fivemack @15e [completed, 4130624 relations] 25M - 30M fivemack [completed, 15e sieve, 21039132 relations] 30M - 55M smh [completed, 49516175 relations] 55M - 60M fivemack @14e [completed, 9739894 relations] 60M - 67M fivemack @14e [completed, 13204459 relations] 67M - 70M bsquared [completed, 5513489 relations] 70M - 72M andi47 [completed, 3628344 relations] 72M - 75M jhansen [completed, 5386758 relations] 75M - 80M jbristow [completed, 8814348 relations] 80M - 86M andi47 [completed, 10285122 relations] 86M -100M akruppa [completed, 23176554 relations] 100M -120M akruppa [completed, 31232260 relations] 120M -122M fivemack [completed, 3034380 relations] 122M -130M smh [completed, 11836672 relations] 130M -132M bsquared [completed, 2961713 relations] 132M -135M fivemack @15e [completed, 11921570 relations] 135M -137M andi47 [completed, 2917655 relations] 137M -138M fivemack @14e [completed, 1450811 relations] 138M -140M fivemack @15e [completed, 6274349 relations] Instructions To sieve, use Code: gnfs-lasieve4I14e -o 55.56 -a 6+383.job -f 55000000 -c 1000000 with '55.56' changed appropriately, -f <start of range> -c <size of range>, and 6+383.job being the file enclosed in the bottom section of this post. If your computer crashes mid-job, look at the last hex number on the last full line of the output file '55.56', convert it to decimal, and use that as the '-f' when you start again; subtract from '-c' appropriately so that your range ends in the right place. (ie, if the output file ends Code: 12571943595,90442:da66c29,648802f,17455,55543,7,2B,47,3,3,B,B:11c54b27,84f9ac1,2A2D7,34565,67553,12B7B9,19CF,148D,5,5,1F,1F3,2,2,34DFF65 -11386617209,23426:72c380b,4371 then you convert 34DFF65 to decimal, getting 55443301, and continue with Code: gnfs-lasieve4I14e -o 55a.56 -a 6+383.job -f 55443301 -c 556699 There is a limitation in gnfs-lasieve4 meaning that, if you are sieving a range starting below 50000000, you need to change the 'alim' line in the job file to be the start of your range. I reckon 1000 Q takes about eight CPU-minutes on a 2.4GHz Core2, so a million takes a bit under a week on one such core. Uploading Connect by anonymous FTP to ftp.chiark.greenend.org.uk, then do Code: cd special/twomack-relations/esbjerg binary put relation.file The 'esbjerg' directory has special magic properties meaning that it doesn't show up in 'ls', which may confuse some ftp clients, but is apparently necessary to avoid people finding it by looking at random anon-ftp sites then using it as a pirate haven. As of 00:01 on 02 January 2008, I have in esbjerg completed relation files for 30.0-42.5, 67-70, 72-75 and additionally on my workstation 25-28, 42.5-60.0, 65-67 and 86-120. I need to wait for some new hard drives to arrive before I can decompress and merge everything and get a really good idea of percentage completion, and my supplier's been a bit incompetent: maybe by the 9th? Collaborators, start your sieves! 6+383 file Code: n: 230380135646168002240144238096238189782429580465812519176892278271650463794969643225877877269156894108094881082195219664775471894182470295616143804362949333632033489 skew: 210886.76 c5 11472718320 c4 -3795305047120954 c3 -2612363701552248486716 c2 107677876784557388243547221 c1 33277562211750204806364306268284 c0 547440910672314203689898814059115360 Y1 2391424041494417171 Y0 -7253635851193924156735160443739 rlim: 50000000 alim: 50000000 lpbr: 31 lpba: 31 rlambda: 2.6 alambda: 2.6 mfbr: 62 mfba: 62 If you have any questions, pm me or post on this thread Last fiddled with by fivemack on 2008-01-19 at 19:29 Reason: finish stats

2007-12-24, 18:03	#3
akruppa "Nancy" Aug 2002 Alexandria 100110100011₂ Posts	The 86M-100M range is finished (looks like no one else is using the Grid5000 clusters over Christmas!), may I take 100M-120M as well? If that's ok, I won't take more than this range as not to jeopardize the collaborative character of this effort. Alex Last fiddled with by akruppa on 2007-12-24 at 18:05 Reason: spelling

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
6^383+1 by GNFS (polynomial search; now complete)	fivemack	Factoring	20	2007-12-26 10:36
f14 complete	masser	Sierpinski/Riesel Base 5	2	2006-04-23 16:05
Complete Factorization???	Khemikal796	Factoring	13	2005-04-15 15:21
Factoring -1.#J% complete	Peter Nelson	Software	4	2005-04-06 00:17
61.5 thru 62m complete to 2^60	nitro	Lone Mersenne Hunters	0	2003-12-07 13:50

2007-12-24, 15:45	#2
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 1100100110110₂ Posts	I should have an upload mechanism in place by New Year - it requires a friend of mine to fiddle about with the filesystem configuration on his colocated machine, which will have to wait until after Christmas, and then you can upload the files by FTP. Until then, if you have web space that you can put files on, I can pull them down without trouble.

2007-12-24, 21:28	#4
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2·7·461 Posts	That's quite spectacular performance. If I'd known there were resources on that scale available ... [I'd have done exactly what I'm doing now - what I don't have is the parallel software for a truly-large matrix] There's no virtue in not applying available resources; go ahead with 100M - 120M. If you have resources of this scale, I presume 7-269 has already succumbed ... do you feel like sieving 2^841-1 ? (2x^6+1;x-2^140, sp=50M lp=31, q_alg=25M-175M ought to suffice ...)

2007-12-24, 22:04	#5
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	The problem is predicting availability. Yesterday and today there was almost no one else using the cluster in Bordeaux. That's about 400 Opteron cores I can use. If I use nodes at other locations as well it might be 1000 or more, enough to sieve a decent size project in a day. However, if other users start running their own jobs again I might not get an awful lot of cpu time for weeks. It's a gamble. I'm not using those machines for NFS very much yet, mostly because I couldn't do all the post-processing work. But if someone else is willing to handle the messy part... 7,269- is sieved and the matrix is running. I'm preparing 3,533- for sieving at the moment. Both are easy enough that I can do the post-processing with the CWI tools I'm familiar with. The sq < 120M for 6^383+1 are finished as well, I'm trying to think of somewhere to put them for download. If you'll do the filtering and matrix and only need the relations for a bigger project, I'd gladly join and see how much cpu time I can grab. 2,841- is fine with me. Does it need more ECM first? Alex

2007-12-24, 22:51	#6
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2·7·461 Posts	Well, I've got a quad-core on order, and might as well go for 8GB memory for it - there are two 2G sticks sitting on my desk at work - at which point 2,841- shouldn't be an impossible filtering and matrix job, though the relations will be a cumbersome amount of data to move around. I don't know how much it's been ECMed, if you're in a position to start ECM tonight and switch to sieving in the morning, that might be the right combination. Go for it; at worst I'll have to organise another phalanx of mersenneforum people in 2008 to mop up such relations as couldn't be done over xmas on the Grid.

2008-01-01, 20:50	#9
smh "Sander" Oct 2002 52.345322,5.52471 29×41 Posts	Should we do any line sieving using msieve?

2008-01-01, 23:25	#10
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 1936₁₆ Posts	Line sieving might not be a bad idea. I'm not at all sure about parameter choice; (10..90)th-percentile range of A and 5th-percentile range of B is a=-10^10 .. 10^10, b=0..3000, but I've not done line sieving at all so I don't know how long that would take.