mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > CADO-NFS

Reply
 
Thread Tools
Old 2019-12-03, 09:00   #12
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

572210 Posts
Default

When calling the siever directly 2^A is the sieve region. A=31 defaults to I=16 A=29 to I=15 etc. A=2*I-1
I think that A=32 will be 2^16 by 2^16. It is twice the region of A=31 in any case.
A=32 is more manageable than I=17 memory wise so it is an option for low q sieving to get more yield.

sieve.adjust_strategy is different strategies for selection of I and J in 2^I by 2^J given A=I+J. It is described in las -h
Quote:
-adjust-strategy strategy used to adapt the sieving range to the q-lattice basis (0 = logI constant, J so that boundary is capped; 1 = logI constant, (a,b) plane norm capped; 2 = logI dynamic, skewed basis; 3 = combine 2 and then 0) ; default=0
3 can be better sometimes but can use more memory. It is a potentially useful option for someone with a low yield or if you want to focus sieving on less qs.
I would suggest some experimentation with this may be worthwhile. It may speed up some sizes for some q(which q might be an unanswered research question)

Is it getting to the point where NFS@Home should be looking at switching to the CADO siever?

Last fiddled with by henryzz on 2019-12-03 at 09:01
henryzz is offline   Reply With Quote
Old 2019-12-03, 11:26   #13
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

1024410 Posts
Default

This post to the CADO-NFS list seems very slightly relevant.

Quote:
It is persisting.

./cado-nfs.py <309 digit RSA number> -t 60

I cannot provide the exact number per my work agreement.

Best Regards,
--
Justin Granger
Someone trying polynomial searching on a kilobit composite.
xilman is online now   Reply With Quote
Old 2019-12-03, 17:56   #14
Robert_JD
 
Robert_JD's Avatar
 
Sep 2010
So Cal

2·52 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Nice. But reading the file requires knowledge of some app specific syntax.

Knowledge not required, just a dose of enough common sense logic that others in this thread would inevitably grasp
Robert_JD is offline   Reply With Quote
Old 2019-12-03, 18:10   #15
Robert_JD
 
Robert_JD's Avatar
 
Sep 2010
So Cal

3216 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
900 core-years computation time (800 sieve, 100 matrix) on 2.1ghz Xeons gold. They observe this job ran 3x faster than would be expected from an extrapolation from RSA-768, and in fact would have been 25% faster on identical hardware than RSA-768 was.

I'd love a more detailed list of parameters! Perhaps a future CADO release will include them in the c240.params default file. :)

For comparison, we ran a C207 Cunningham number 2,2330L in about 60 core-years sieve, which scales really roughly to an estimate of 3840 core-years sieve (6 doublings at 5.5 digits per doubling). The CADO group found a *massive* improvement in sieve speed for large problems! 4 times faster, wowee.

Edit: Their job is so fast that RSA-250 is easily within their reach. Which means that C251 from Euclid-Mullen is within reach, theoretically. I mean, imagine if all NFS work over 200 digits is suddenly twice as fast.....

Quote:
...imagine if all NFS work over 200 digits is suddenly twice as fast.....
I certainly wouldn't mind re-factoring RSA-200 again, which took a little less than 7 months - IF utilizing similar parameter upgrades would possibly double the speed.
Robert_JD is offline   Reply With Quote
Old 2019-12-03, 18:49   #16
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

72·47 Posts
Default

The link just went down. I'm guessing it's due to high traffic.
ixfd64 is offline   Reply With Quote
Old 2019-12-03, 19:46   #17
Nooks
 
Jul 2018

1316 Posts
Default

A copy of the announcement has been saved in the Internet Archive: http://web.archive.org/web/201912031...er/001139.html
Nooks is offline   Reply With Quote
Old 2020-08-10, 12:51   #18
Branger
 
Oct 2018

3×5 Posts
Default

Some additional details about the RSA-240 factorization, as well as the discrete log done at the same time can be found at:

https://eprint.iacr.org/2020/697
Branger is offline   Reply With Quote
Old 2020-08-10, 16:35   #19
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

10DF16 Posts
Default

Quote:
Originally Posted by Branger View Post
Some additional details about the RSA-240 factorization, as well as the discrete log done at the same time can be found at:

https://eprint.iacr.org/2020/697
This paper also exhibits the factors of RSA-250!!
Parameters were nearly the same as for RSA-240, except for increasing sieve region from A=32 to A=33 (a doubling of sieve area, equivalent to using a mythical 17e on GGNFS).
Still 2LP on one side, 3 on the other.
Lim's were 2^31. Only 8.7G raw relations were needed, 6.1G unique!!

They cite 2450 Xeon-Gold-2.1Ghz core-years sieving, 250 core-years matrix for 405M matrix size.

Last fiddled with by VBCurtis on 2020-08-10 at 16:36
VBCurtis is offline   Reply With Quote
Old 2020-08-10, 18:39   #20
charybdis
 
Apr 2020

10111012 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
Parameters were nearly the same as for RSA-240, except for increasing sieve region from A=32 to A=33 (a doubling of sieve area, equivalent to using a mythical 17e on GGNFS).
Tried this out - a single instance of las with their parameters uses 38GB of memory
charybdis is offline   Reply With Quote
Old 2020-08-10, 22:09   #21
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

3×1,031 Posts
Default

That makes you think how big is the LA machine. Only a few people around here can accommodate a 40M matrix let alone a 405M matrix!!
RichD is offline   Reply With Quote
Old 2020-08-11, 00:19   #22
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

7×617 Posts
Default

Same way Greg does- the supercomputing grids used by the CADO team for these factorizations can handle jobs such as a matrix distributed over many nodes. The paper includes a summary of the number of nodes used for each step of the RSA-240 matrix.

I'm not aware of filtering being split over multiple nodes, so that is the part that needs the largest-memory machine, and that likely fit in 256GB (perhaps 384).
VBCurtis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
factored mp / (mp < 100.000.000 ) bhelmes Data 3 2018-09-28 18:31
10^224 + 3 factored 2147483647 Factoring 0 2016-12-31 16:22
Factored vs. Completely factored aketilander Factoring 4 2012-08-08 18:09
F33 is factored !! Raman Factoring 4 2010-04-01 13:57
RSA-100 factored! ewmayer Math 5 2003-05-14 15:08

All times are UTC. The time now is 12:59.

Thu Sep 24 12:59:27 UTC 2020 up 14 days, 10:10, 2 users, load averages: 2.10, 1.83, 1.72

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.