mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-12-21, 00:05   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

18D116 Posts
Default 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
fivemack is offline   Reply With Quote
Old 2007-12-24, 15:45   #2
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,353 Posts
Default

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.
fivemack is offline   Reply With Quote
Old 2007-12-24, 18:03   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2007-12-24, 21:28   #4
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,353 Posts
Default

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 ...)
fivemack is offline   Reply With Quote
Old 2007-12-24, 22:04   #5
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2007-12-24, 22:51   #6
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,353 Posts
Default

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 is offline   Reply With Quote
Old 2007-12-28, 21:05   #7
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,353 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
fivemack is offline   Reply With Quote
Old 2007-12-30, 12:20   #8
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

2·17·73 Posts
Default

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
Andi47 is offline   Reply With Quote
Old 2008-01-01, 20:50   #9
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

100101001012 Posts
Default

Should we do any line sieving using msieve?
smh is offline   Reply With Quote
Old 2008-01-01, 23:25   #10
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,353 Posts
Default

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.
fivemack is offline   Reply With Quote
Old 2008-01-02, 00:01   #11
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

DC716 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.

Last fiddled with by jasonp on 2008-01-02 at 00:08
jasonp is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 03:33.

Sun Aug 9 03:33:55 UTC 2020 up 22 days, 23:20, 1 user, load averages: 2.00, 2.00, 1.88

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.