mersenneforum.org Where in the RSA 180 woods am I?
 Register FAQ Search Today's Posts Mark Forums Read

 2019-05-04, 14:55 #1 AlienDjinn   Apr 2019 Bay Area, CA 11 Posts Where in the RSA 180 woods am I? I'm new to factoring but enjoying this forum a lot. I bought a new RYZEN 2700x 16 core system and have been attacking the RSA 180 for a couple of days now. As a benchmark my system demolished the RSA 100 in 9 minutes. Below is my factor log. Is there any way to tell how far in the process I might be? At one point I hit a max threshold and it switched strategies. "error generating or reading NFS polynomials elapsed time of 186454.8044 seconds exceeds 67500 second deadline; poly select done nfs: commencing algebraic side lattice sieving over range: 41300000 - 41320000 nfs: commencing algebraic side lattice sieving over range: 41260000 - 41280000" Code: ********************************** Factor.log ******************************* 04/30/19 08:35:38 v1.34.5 @ ROCINANTE, **************************** 04/30/19 08:35:38 v1.34.5 @ ROCINANTE, Starting factorization of 191147927718986609689229466631454649812986246276667354864188503638807260703436799058776201365135161278134258296128109200046702912984568752800330221777752773957404540495707851421041 04/30/19 08:35:38 v1.34.5 @ ROCINANTE, using pretesting plan: normal 04/30/19 08:35:38 v1.34.5 @ ROCINANTE, no tune info: using qs/gnfs crossover of 95 digits 04/30/19 08:35:38 v1.34.5 @ ROCINANTE, **************************** 04/30/19 08:35:38 v1.34.5 @ ROCINANTE, rho: x^2 + 3, starting 1000 iterations on C180 04/30/19 08:35:38 v1.34.5 @ ROCINANTE, rho: x^2 + 2, starting 1000 iterations on C180 04/30/19 08:35:38 v1.34.5 @ ROCINANTE, rho: x^2 + 1, starting 1000 iterations on C180 04/30/19 08:35:38 v1.34.5 @ ROCINANTE, pm1: starting B1 = 150K, B2 = gmp-ecm default on C180 04/30/19 08:35:38 v1.34.5 @ ROCINANTE, current ECM pretesting depth: 0.00 04/30/19 08:35:38 v1.34.5 @ ROCINANTE, scheduled 30 curves at B1=2000 toward target pretesting depth of 55.38 04/30/19 08:35:38 v1.34.5 @ ROCINANTE, Finished 30 curves using Lenstra ECM method on C180 input, B1=2K, B2=gmp-ecm default 04/30/19 08:35:38 v1.34.5 @ ROCINANTE, current ECM pretesting depth: 15.18 04/30/19 08:35:38 v1.34.5 @ ROCINANTE, scheduled 74 curves at B1=11000 toward target pretesting depth of 55.38 04/30/19 08:35:41 v1.34.5 @ ROCINANTE, Finished 74 curves using Lenstra ECM method on C180 input, B1=11K, B2=gmp-ecm default 04/30/19 08:35:42 v1.34.5 @ ROCINANTE, current ECM pretesting depth: 20.24 04/30/19 08:35:42 v1.34.5 @ ROCINANTE, scheduled 214 curves at B1=50000 toward target pretesting depth of 55.38 04/30/19 08:35:48 v1.34.5 @ ROCINANTE, Finished 224 curves using Lenstra ECM method on C180 input, B1=50K, B2=gmp-ecm default 04/30/19 08:35:48 v1.34.5 @ ROCINANTE, pm1: starting B1 = 3750K, B2 = gmp-ecm default on C180 04/30/19 08:35:49 v1.34.5 @ ROCINANTE, current ECM pretesting depth: 25.35 04/30/19 08:35:49 v1.34.5 @ ROCINANTE, scheduled 430 curves at B1=250000 toward target pretesting depth of 55.38 04/30/19 08:36:38 v1.34.5 @ ROCINANTE, Finished 432 curves using Lenstra ECM method on C180 input, B1=250K, B2=gmp-ecm default 04/30/19 08:36:38 v1.34.5 @ ROCINANTE, pm1: starting B1 = 15M, B2 = gmp-ecm default on C180 04/30/19 08:36:44 v1.34.5 @ ROCINANTE, current ECM pretesting depth: 30.46 04/30/19 08:36:44 v1.34.5 @ ROCINANTE, scheduled 904 curves at B1=1000000 toward target pretesting depth of 55.38 04/30/19 08:43:16 v1.34.5 @ ROCINANTE, Finished 912 curves using Lenstra ECM method on C180 input, B1=1M, B2=gmp-ecm default 04/30/19 08:43:16 v1.34.5 @ ROCINANTE, current ECM pretesting depth: 35.56 04/30/19 08:43:16 v1.34.5 @ ROCINANTE, scheduled 2350 curves at B1=3000000 toward target pretesting depth of 55.38 04/30/19 09:29:45 v1.34.5 @ ROCINANTE, Finished 2352 curves using Lenstra ECM method on C180 input, B1=3M, B2=gmp-ecm default 04/30/19 09:29:45 v1.34.5 @ ROCINANTE, current ECM pretesting depth: 40.63 04/30/19 09:29:45 v1.34.5 @ ROCINANTE, scheduled 4480 curves at B1=11000000 toward target pretesting depth of 55.38 04/30/19 14:41:53 v1.34.5 @ ROCINANTE, Finished 4480 curves using Lenstra ECM method on C180 input, B1=11M, B2=gmp-ecm default 04/30/19 14:41:53 v1.34.5 @ ROCINANTE, current ECM pretesting depth: 45.73 04/30/19 14:41:53 v1.34.5 @ ROCINANTE, scheduled 7553 curves at B1=43000000 toward target pretesting depth of 55.38 05/01/19 22:53:28 v1.34.5 @ ROCINANTE, Finished 7568 curves using Lenstra ECM method on C180 input, B1=43M, B2=gmp-ecm default 05/01/19 22:53:28 v1.34.5 @ ROCINANTE, final ECM pretested depth: 50.86 05/01/19 22:53:28 v1.34.5 @ ROCINANTE, scheduler: switching to sieve method 05/01/19 22:53:28 v1.34.5 @ ROCINANTE, nfs: commencing nfs on c180: 191147927718986609689229466631454649812986246276667354864188503638807260703436799058776201365135161278134258296128109200046702912984568752800330221777752773957404540495707851421041 05/01/19 22:53:28 v1.34.5 @ ROCINANTE, nfs: commencing poly selection with 16 threads 05/01/19 22:53:28 v1.34.5 @ ROCINANTE, nfs: setting deadline of 67500 seconds 05/04/19 02:41:03 v1.34.5 @ ROCINANTE, nfs: completed 16 ranges of size 250 in 186454.8044 seconds 05/04/19 02:41:03 v1.34.5 @ ROCINANTE, nfs: best poly = # norm 1.442139e-017 alpha -7.879891 e 7.667e-014 rroots 5 05/04/19 02:41:03 v1.34.5 @ ROCINANTE, nfs: commencing lattice sieving with 16 threads 05/04/19 05:19:54 v1.34.5 @ ROCINANTE, nfs: commencing lattice sieving with 16 threads thanks! --Alien
2019-05-04, 15:15   #2
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100111000001112 Posts

Quote:
 Originally Posted by AlienDjinn As a benchmark my system demolished the RSA 100 in 9 minutes.
For every 5 digits, the runtime of this workflow roughly doubles.
So a very rough estimate of your remaining time is

t = 9 * 2^(80/5) = 589824 minutes ~= 9800 hours ~= 410 days

Scaling from 9 minutes to 410 days is arguably imperfect. You may want to run a 140 digit challenge to get a better time estimate. Then a 150 digit. Both of these will be a tiny fraction of the time for the GNFS-180.

The analogy will also be imperfect in terms of memory needed to solve the resulting linear algebra. Search the forum for a past result in GNFS-180. Something like 32Gb of memory may be needed; maybe more.

In short, where in the woods are you? You are in the edge tree line; you haven't even fully entered the forest.

2019-05-04, 17:04   #3
AlienDjinn

Apr 2019
Bay Area, CA

11 Posts

Quote:
 Originally Posted by Batalov For every 5 digits, the runtime of this workflow roughly doubles. So a very rough estimate of your remaining time is t = 9 * 2^(80/5) = 589824 minutes ~= 9800 hours ~= 410 days Scaling from 9 minutes to 410 days is arguably imperfect. You may want to run a 140 digit challenge to get a better time estimate. Then a 150 digit. Both of these will be a tiny fraction of the time for the GNFS-180. The analogy will also be imperfect in terms of memory needed to solve the resulting linear algebra. Search the forum for a past result in GNFS-180. Something like 32Gb of memory may be needed; maybe more. In short, where in the woods are you? You are in the edge tree line; you haven't even fully entered the forest.
OH WOW! Appreciate the response Batalov. I've got long journey ahead...

2019-05-05, 06:04   #5
AlienDjinn

Apr 2019
Bay Area, CA

11 Posts

Quote:
 Originally Posted by VBCurtis The journey of learning to factor is not best taken by jumping in to a 1-year job (which has already been done, besides). 1. Does each phase scale by 15x? Which scale worse, or better? 2. Should they all scale similarly, or is this a setting you can adjust for yourself? 3. Do more cores affect each phase similarly? Which parts scale perfectly by number of cores, and which are limited to a small number of threads? 4. Do you have an Nvidia GPU, and is it set up to use CUDA software for the first phase?
Hi VB Curtis,

Thanks for the feedback and course correction. Do you have any recommended tuning links or can I more information in this forum?

Thanks again,

--Alien

 2019-05-05, 13:35 #6 VBCurtis     "Curtis" Feb 2005 Riverside, CA 23·5·139 Posts Do you run linux or windows? Do you have a CUDA-supported GPU? On Linux, CADO-NFS has easier to control settings, and a (lengthy) dedicated thread within this subforum for our collective discoveries about tuning the package. It's not available (well, not "easily" compiled) for Windows, alas. Are you presently using YAFU, or factmsieve.py? If you have the .poly and .fb files, you could compare the settings your software chose with the settings for inputs near C180 on the subforum "NFS@home" thread "queue management"; say, C177 to c183 should be relevant. But, to do that, you'd need to know what the abbreviations mean. I lack time this morning to explain that, but I'd start with the wiki entries on Integer Factorization and the General Number Field Sieve. The latter has some useful links. Someone in the forum has likely posted a guide at some point in the past, but I don't personally know where (in fact, maybe I'll write one!).
 2019-05-05, 13:53 #7 bsquared     "Ben" Feb 2007 1110100010112 Posts From the log in the first post it looks like YAFU is being used. Another thing to learn is that for RSA numbers, where the approximate size of the factors is known, it is pointless to run ECM curves on them. ECM's effectiveness decreases with the size of the smallest *factor* of the input. By design, RSA numbers have very large smallest factors; thus, ECM will not be effective. YAFU's factor function is intended to be used where one has no knowledge of the input and therefore rho, p-1, and ecm have a chance to pull out small factors. When you know beforehand that there are no small factors, you can skip directly to NFS (e.g., yafu "nfs(your-input)" instead of yafu "factor(your-input)"). This would have saved you 38 some hours of needless ECM in this case. As VBCurtis has mentioned, YAFU hasn't been tuned well (at all) for inputs this large. It may work, but a little manual intervention would likely save a lot of time.
2019-05-05, 21:46   #8
AlienDjinn

Apr 2019
Bay Area, CA

11 Posts

Thanks VBCurtis and bsquared for the help.

Quote:
 Originally Posted by VBCurtis Do you run linux or windows? Do you have a CUDA-supported GPU?.
VBCurtis you inspired me to get a CUDA enabled GPU. Question though, is 'GPU_NUM' refer to the number of CUDA cores? (factmsieve-086.py)

USE_CUDA = False
GPU_NUM = 0
MSIEVE_POLY_TIME_LIMIT = 0
MIN_NFS_BITS = 264

Quote:
 Originally Posted by VBCurtis Are you presently using YAFU, or factmsieve.py? If you have the .poly and .fb files, you could compare the settings your software chose with the settings for inputs near C180 on the subforum "NFS@home" thread "queue management"; say, C177 to c183 should be relevant. But, to do that, you'd need to know what the abbreviations mean. I lack time this morning to explain that, but I'd start with the wiki entries on Integer Factorization and the General Number Field Sieve. The latter has some useful links. Someone in the forum has likely posted a guide at some point in the past, but I don't personally know where (in fact, maybe I'll write one!).
I've got both tools up and running on Windows. +1000 on the guide for us newbies!! :)

Quote:
 Originally Posted by bsquared From the log in the first post it looks like YAFU is being used. Another thing to learn is that for RSA numbers, where the approximate size of the factors is known, it is pointless to run ECM curves on them. ECM's effectiveness decreases with the size of the smallest *factor* of the input. By design, RSA numbers have very large smallest factors; thus, ECM will not be effective. YAFU's factor function is intended to be used where one has no knowledge of the input and therefore rho, p-1, and ecm have a chance to pull out small factors. When you know beforehand that there are no small factors, you can skip directly to NFS (e.g., yafu "nfs(your-input)" instead of yafu "factor(your-input)"). This would have saved you 38 some hours of needless ECM in this case. As VBCurtis has mentioned, YAFU hasn't been tuned well (at all) for inputs this large. It may work, but a little manual intervention would likely save a lot of time.

 2019-05-06, 01:26 #10 VBCurtis     "Curtis" Feb 2005 Riverside, CA 23·5·139 Posts On RSA130: msieve 1.53, GPU-enabled binary RichD sent my way: stage1_norm 3.88e+19 stage2_norm 9.34e+17 msieve SVN 1028, self-compiled with no GPU support: stage1_norm 2.05e+20 stage2_norm 6.44e+16 The latter was allowed to run on CPU for a few minutes; it seems to save 3-5 hits per minute to the .ms file. This is a bit too much output, as I'd want to give 2 CPU-hours to the search (per the 5% of guesstimated total job length rule of thumb); after 2 hours I'd have 500-800 hits. 9.34e+17 divided by 30 is 3e+16. That sounds about right for a GPU-enabled search. msieve -np1 -nps "1000,1000000 stage2_norm=3e16" -s testnumber1 if your msieve is GPU-enabled and your CUDA install works, output you will have.
2019-05-06, 01:58   #11
AlienDjinn

Apr 2019
Bay Area, CA

11 Posts

Quote:
 Originally Posted by VBCurtis On RSA130: msieve 1.53, GPU-enabled binary RichD sent my way: stage1_norm 3.88e+19 stage2_norm 9.34e+17 msieve SVN 1028, self-compiled with no GPU support: stage1_norm 2.05e+20 stage2_norm 6.44e+16 The latter was allowed to run on CPU for a few minutes; it seems to save 3-5 hits per minute to the .ms file. This is a bit too much output, as I'd want to give 2 CPU-hours to the search (per the 5% of guesstimated total job length rule of thumb); after 2 hours I'd have 500-800 hits. 9.34e+17 divided by 30 is 3e+16. That sounds about right for a GPU-enabled search. msieve -np1 -nps "1000,1000000 stage2_norm=3e16" -s testnumber1 if your msieve is GPU-enabled and your CUDA install works, output you will have.
Hi VBCurtis,

Thanks for the super detailed post! I'm trying the above but don't see much GPU usage yet.

fyi, I don't have an 'msieve.exe' I only have 'msieve-1.53-SVN998-win64-core2.exe'

1) Do I have the wrong binary? if so do you know where can I get a different one?

2) Any idea why my GPUs aren't engaged?

3) Seeing a ton of values fly by in at the command prompt but no hits yet in the .ms file.

1584 12738790608913 16272135079752196210474712
1584 34337744182451 16272135081116971690678241
1584 7678710829783 16272135080281840469834043
1584 21358728303851 16272135080775711427898844
1584 39084391013831 16272135080079524779089986
1584 1384940045431 16272135080226697437126266
1584 27803826879721 16272135080642182299793035
1584 32828762326649 16272135080641014750871832
1584 1438736427581 16272135080225917153575710
1584 13460387837819 16272135080476752277635070

thanks again,

--Alien

All times are UTC. The time now is 09:41.

Thu Dec 8 09:41:12 UTC 2022 up 112 days, 7:09, 0 users, load averages: 1.41, 1.09, 1.02