HP49(119)... - Page 12

VBCurtis · 2016-10-07, 03:42

Some RSA-768 stats, for reference:

2^16 x 2^15 sieve area (identical to 16e)
4 large primes (!!!!!) on alg side, 3 on rational
mfba = 140, mfbr = 110
lpba = lpbr = 40 (they note mfba/mfbr are set optimally for lp = 37, but they accepted up to 40-bit large primes)
Factor base 1100M on one side, 200M on the other side.
64G raw relations, 27% duplicate rate. At 150 bytes per relation, that's about 10TB of data.
193M matrix of total weight 27G (144 per row, jasonp has noted this is not quite equivalent to target-density in msieve). The authors noted they expected 250M matrix of weight 37G, so they conclude they oversieved by nearly a factor of 2.
1500 core-years sieving normalized to opteron-2.2ghz core.

If we accept their conclusion of oversieving, 800 core-years might've been enough. Today's standard core is perhaps 50% faster than Athlon-2.2, so let's say 550 core-years on modern 3.4Ghz hardware.

GNFS-251 should be roughly 15 times longer to sieve than RSA-768, so 8000 modern core-years might produce a rather large matrix, with 10000 possibly a good plan to produce a more manageable matrix.

pinhodecarlos · 2016-10-07, 05:21

Few notes if we use NFS@Home:

1) Request Greg authorisation and confirm if we can use the 5f application
2) Confirm if NFS server has plenty of hard space with backup
3) Prior to the start of sieving NFS should release a statement explaining this run is for a GNFS world record factorisation so people could mobilise their computers to help
4) Give to NFS clients an estimate of the sieve time in function on the numbers of cores allocated
5) Confirm with Greg if the cluster can be used to run the post-processing stage hence I think his grant had ended but this is a medium term goal so he might have it back next year.

From my side I can push several teams to support us on sieving.

PS( forgot about the polynomial search...who's gonna do it?!)

VBCurtis · 2016-10-07, 06:04

Carlos-
Is the 96-bit mfbr/mfba limit lifted on the 5f siever? It didn't occur to me that anything other than CADO would work for this job.

Edit: and, ohyea, how are you going to get 17e or 18e from lasieve?

pinhodecarlos · 2016-10-07, 06:17

Quote:

Originally Posted by VBCurtis

Carlos-
Is the 96-bit mfbr/mfba limit lifted on the 5f siever? It didn't occur to me that anything other than CADO would work for this job.

Edit: and, ohyea, how are you going to get 17e or 18e from lasieve?

Curtis,

First question I don't know, second not a clue...lol
Can CADO be integrated onto NFS@Home platform?!

xilman · 2016-10-07, 10:08

Quote:

Originally Posted by VBCurtis

Carlos-
Is the 96-bit mfbr/mfba limit lifted on the 5f siever? It didn't occur to me that anything other than CADO would work for this job.

Edit: and, ohyea, how are you going to get 17e or 18e from lasieve?

I used ggnfs for rsa768 sieving.

pinhodecarlos · 2016-10-07, 11:06

Quote:

Originally Posted by xilman

I used ggnfs for rsa768 sieving.

That's good.

In the meantime, this is a little off topic, but if my calculations are correct taken for BOINC NFS@Home page, in the last 24 hours almost 3200 cores were connected to NFS@Home grid running the 5f siever. Each core being an equivalent to an i7-3630QM CPU @ 3.20GHz core.
Calculations were based on my laptop estimating time of one hour to process one 5f siever task. Faster computers can run the task in 2500 seconds or less. 80k 5f tasks done in the last 24 hours. Let's see next couple of days during the challenge because the core numbers might be over estimated do to clients bunkering.

VBCurtis · 2016-10-12, 16:41

Quote:

Originally Posted by VBCurtis

I'll donate a few hundred ECM curves, as I have grown tired of M1277 ECM work.

A bit of testing with ECM-7.0.1 on a 16GB machine with -maxmem 13000:
Comparing 4.2e9, 6e9, and 7e9, B1=6e9 minimizes expected time to complete a t70. With B1 = 6e9, increasing B2 by 30% further reduced t70 time, with higher B2 bounds still to be tested.

I am now working to find what bounds minimize expected t75 time on this 16GB machine. I also have two 32GB machines to use to see what effect doubling maxmem (and thus quartering k) has on the minimum. At under one curve per day, this testing may take a while!

Nooks · 2018-07-11, 03:40

Quote:

Originally Posted by WraithX

I was recently asked about the status of HP49 119 c251, and wanted to update everyone. I'd also like to ask if anyone here on the forum would help me tackle this number with GNFS?

I may be two years late, but I'm very pleased to learn that others think c251 is within reach of dedicated volunteers. Seeing this number factored would be amazing.

I've been working on steadily larger factorizations of less than 200 digits using CADO-NFS with a fair bit of success and am trying to improve my understanding of GNFS parameters and sizing.

VBCurtis · 2018-07-11, 14:39

Quote:

Originally Posted by Nooks

I may be two years late, but I'm very pleased to learn that others think c251 is within reach of dedicated volunteers. Seeing this number factored would be amazing.
I've been working on steadily larger factorizations of less than 200 digits using CADO-NFS with a fair bit of success and am trying to improve my understanding of GNFS parameters and sizing.

GNFS on this c251 is surely not within the reach of regular folks. Even our resident superpower Ryan Propper would not be able to factor this, and he at one point had 500-1000 cores available. The matrix is the main hurdle; if our band of dedicated volunteers included time on a sizable cluster, then we'd have a chance. CADO with I=17 should be sufficient for sieving, but that requires something like 30GB memory per process!

You should have a look at the CADO-NFS thread in this subforum, where we discuss improvements on the default CADO-NFS params files. If you're doing jobs of 160+ digits, I'd really like to see timing data and parameter choice from your runs.

Nooks · 2018-07-11, 15:28

Quote:

Originally Posted by VBCurtis

GNFS on this c251 is surely not within the reach of regular folks. Even our resident superpower Ryan Propper would not be able to factor this, and he at one point had 500-1000 cores available. The matrix is the main hurdle; if our band of dedicated volunteers included time on a sizable cluster, then we'd have a chance. CADO with I=17 should be sufficient for sieving, but that requires something like 30GB memory per process!

I guess I got a little excited by earlier estimates of c251 needing only (!) 10,000 core-years. I've been fascinated by HP49 for a long time.

30GB per process would limit one's ability to find machines to run on and use all the cores, certainly.

Quote:

Originally Posted by VBCurtis

You should have a look at the CADO-NFS thread in this subforum, where we discuss improvements on the default CADO-NFS params files. If you're doing jobs of 160+ digits, I'd really like to see timing data and parameter choice from your runs.

I've been trying to understand where time went in the RSA-768 and RSA-220 factorizations, so of course I'm happy to share what timing data I have, such as it is, given that only one or two numbers were factored in a single, uninterrupted run that did not require some intervention or restarting.

My latest factorization on a 179-digit N is running mksol now and should finish in about a week, I'll update the CADO-NFS thread then.

Perhaps another route to take here is to have a conversation about how to write a c250 parameter file for CADO-NFS; I've previously played around with using the c270 params file that's included, and am learning how the parameters relate to one another but I still don't understand it fully.

VBCurtis · 2018-07-11, 20:19

Have a look at this thread about M1277 http://mersenneforum.org/showthread....523#post487523 for some discussion of parameter selection of a sort-of-similar-sized SNFS job. Test-sieving in CADO is a pain, as one must invoke LAS with the entire parameter list as arguments; I plan to figure out how to do it with a GNFS-180 I'm about to factor with CADO. Specifically, I want to see if CADO likes 3 large primes better at this size, and if so what MFBR is most efficient.

2016-10-07, 05:21	#123
pinhodecarlos "Carlos Pinho" Oct 2011 Milton Keynes, UK 3×17×97 Posts	Few notes if we use NFS@Home: 1) Request Greg authorisation and confirm if we can use the 5f application 2) Confirm if NFS server has plenty of hard space with backup 3) Prior to the start of sieving NFS should release a statement explaining this run is for a GNFS world record factorisation so people could mobilise their computers to help 4) Give to NFS clients an estimate of the sieve time in function on the numbers of cores allocated 5) Confirm with Greg if the cluster can be used to run the post-processing stage hence I think his grant had ended but this is a medium term goal so he might have it back next year. From my side I can push several teams to support us on sieving. PS( forgot about the polynomial search...who's gonna do it?!) Last fiddled with by pinhodecarlos on 2016-10-07 at 05:30

2016-10-07, 06:04	#124
VBCurtis "Curtis" Feb 2005 Riverside, CA 4,861 Posts	Carlos- Is the 96-bit mfbr/mfba limit lifted on the 5f siever? It didn't occur to me that anything other than CADO would work for this job. Edit: and, ohyea, how are you going to get 17e or 18e from lasieve? Last fiddled with by VBCurtis on 2016-10-07 at 06:09

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
P-1 on M1061 and HP49.99	ATH	Factoring	21	2009-10-13 13:16

2016-10-07, 03:42	#122
VBCurtis "Curtis" Feb 2005 Riverside, CA 4,861 Posts	Some RSA-768 stats, for reference: 2^16 x 2^15 sieve area (identical to 16e) 4 large primes (!!!!!) on alg side, 3 on rational mfba = 140, mfbr = 110 lpba = lpbr = 40 (they note mfba/mfbr are set optimally for lp = 37, but they accepted up to 40-bit large primes) Factor base 1100M on one side, 200M on the other side. 64G raw relations, 27% duplicate rate. At 150 bytes per relation, that's about 10TB of data. 193M matrix of total weight 27G (144 per row, jasonp has noted this is not quite equivalent to target-density in msieve). The authors noted they expected 250M matrix of weight 37G, so they conclude they oversieved by nearly a factor of 2. 1500 core-years sieving normalized to opteron-2.2ghz core. If we accept their conclusion of oversieving, 800 core-years might've been enough. Today's standard core is perhaps 50% faster than Athlon-2.2, so let's say 550 core-years on modern 3.4Ghz hardware. GNFS-251 should be roughly 15 times longer to sieve than RSA-768, so 8000 modern core-years might produce a rather large matrix, with 10000 possibly a good plan to produce a more manageable matrix.

2018-07-11, 20:19	#132
VBCurtis "Curtis" Feb 2005 Riverside, CA 4,861 Posts	Have a look at this thread about M1277 http://mersenneforum.org/showthread....523#post487523 for some discussion of parameter selection of a sort-of-similar-sized SNFS job. Test-sieving in CADO is a pain, as one must invoke LAS with the entire parameter list as arguments; I plan to figure out how to do it with a GNFS-180 I'm about to factor with CADO. Specifically, I want to see if CADO likes 3 large primes better at this size, and if so what MFBR is most efficient.