mersenneforum.org RSA-240 and RSA-250 Factored!!
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2019-12-03, 09:00   #12
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

22×1,433 Posts

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

2019-12-03, 11:26   #13
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

22×32×281 Posts

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.

2019-12-03, 17:56   #14
Robert_JD

Sep 2010
So Cal

2·52 Posts

Quote:
 Originally Posted by R.D. Silverman 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

2019-12-03, 18:10   #15
Robert_JD

Sep 2010
So Cal

1100102 Posts

Quote:
 Originally Posted by VBCurtis 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.

 2019-12-03, 18:49 #16 ixfd64 Bemusing Prompter     "Danny" Dec 2002 California 3×769 Posts The link just went down. I'm guessing it's due to high traffic.
 2019-12-03, 19:46 #17 Nooks   Jul 2018 19 Posts A copy of the announcement has been saved in the Internet Archive: http://web.archive.org/web/201912031...er/001139.html
 2020-08-10, 12:51 #18 Branger   Oct 2018 F16 Posts 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
2020-08-10, 16:35   #19
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

4,391 Posts

Quote:
 Originally Posted by Branger 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

2020-08-10, 18:39   #20
charybdis

Apr 2020

107 Posts

Quote:
 Originally Posted by VBCurtis 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

 2020-08-10, 22:09 #21 RichD     Sep 2008 Kansas 3×7×149 Posts 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!!
 2020-08-11, 00:19 #22 VBCurtis     "Curtis" Feb 2005 Riverside, CA 4,391 Posts 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).

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post bhelmes Data 3 2018-09-28 18:31 2147483647 Factoring 0 2016-12-31 16:22 aketilander Factoring 4 2012-08-08 18:09 Raman Factoring 4 2010-04-01 13:57 ewmayer Math 5 2003-05-14 15:08

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

Fri Oct 23 11:03:48 UTC 2020 up 43 days, 8:14, 0 users, load averages: 1.06, 1.06, 1.14

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.