|
2018-02-21, 22:57
|
#1 |
"Victor de Hollander"
Aug 2011
the Netherlands
32·131 Posts |
How to get started with Factoring
How to get started with Factoring
Since we regularly get questions on the forum like: How do I factor <insert number>? How can I factor RSA<big>? I want to use multiple PCs to factor <digits> number? etc. I decided to write a "How to get started" post with some basic information and links to beginners guides and tools. First you need to make some basic decisions: Do you want to spend the time and effort to setup various programs and learn how to use them, maybe even compile them yourself? Do you want to factor a specific composite number? If you answered "NO" to one of the questions above I advice you to try the BOINC or Prime95 client approach below. If you answer "YES" to both, skip to factoring a specific composite. Factoring for the general public (easy setup and little maintenance) There is nothing wrong with helping factoring without going into the details on how it's done! Factoring requires a lot of resources and many desktop PCs are sitting idle most of the time while people are writing a document or are browsing the web. You can donate your compute resources to various projects that make good use of them to factor composites. Option 1: the BOINC client Download and install the BOINC client for your operating system from: https://boinc.berkeley.edu/download_all.php Add one (or multiple) of these projects: NFS@home https://escatter11.fullerton.edu/nfs/ Yoyo@home (subproject ECM) https://www.rechenkraft.net/yoyo/ YAFU@home http://yafu.myfirewall.org/yafu/ In the BOINC manager go to <Tools> --> <Computing preferences> to set your preferences on when and how much computing your computer is allowed to contribute. Option 2: Using Prime95 and PrimeNet Download and install Prime95/Mprime for your operating system from: https://www.mersenne.org/download/ (optional) Create a user ID at https://www.mersenne.org/update/ and login with that ID in the client In the Prime95/Mprime client change the <Type of Work to get> to "P-1 factoring" or "ECM factoring" in the <Worker Windows> settings menu. Factoring a specific composite Step 1: Do you have the resources? If you decide you want to factor a specific composite number, or you want to learn how to do it,you need to assess if it can be done with the compute resources you have access to. Also it should be able to complete in a reasonable amount of time. Composite: <100 digits --> can be factored by a desktop computer in a hour or less (as long as you use the right tools) 100-110 digits --> a couple of hours using a desktop with quad-core processor or greater 110-120 digits --> less than a day using a desktop with quad-core processor or greater 130 digits --> several days 140 digits --> 10+ days 150 digits --> month+ 160 digits --> half a year >170 digits --> You're mad, or you're working for the NSA! Individual Records: 210 digits (RSA-210) by Ryan Propper using institutional resources. 210 digits (HP49 term 117) by WraithX using $7600 worth of processing time on Amazon EC2 cloud machines for the sieving, and four months on a dual Xeon E5-2687W v1 for the linear algebra step. (World) Record: 232 digits (RSA-768) in 2009 a team of researchers from the CWI, the EPFL, INRIA and NTT. Effort required was the equivalent of 2000 YEARS of computing on a single core 2.2 GHz AMD Opteron. If you've been paying attention, you'll have noticed the effort required to factor a composite increases exponentially. A rule of thumb: every 5 digits requires a doubling of effort/resources Note: There exist numbers with special forms that are much easier to factor with SNFS, but we won't go into that now. I STRONGLY advice people without experience to first try factoring RSA-100 and/or RSA110! You need to learn how to setup the tools and gain experience with using them. If you neglect to do this, you risk wasting a lot of compute resources by selecting sub-optimal settings or typing the wrong commands. RSA-100 and RSA-110 were part of the RSA Factoring Challenge (https://en.wikipedia.org/wiki/RSA_numbers) RSA-100 (100 digits): Code:
1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 Code:
35794234179725868774991807832568455403003778024228226193532908190484670252364677411513516111204504060317568667 Normally you'll want to check if your number hasn't been previously factored by somebody else. This prevents you from wasting a lot of effort. You can check this in the http://www.factordb.com/ NOTE: For the exercise with RSA-100 you can skip this step. The end result is not important, you want to learn how to setup and use the tools. Step 3 Small factors Next you'll want to search for small factors first. YAFU There are multiple tools for this, but a program called YAFU (Yet Another Factoring Utility) has most of this automated It can be downloaded from: http://sourceforge.net/projects/yafu/ or precompiled windows executables from: http://gilchrist.ca/jeff/factoring/index.html There is also a subforum for YAFU: http://www.mersenneforum.org/forumdisplay.php?f=96 NOTE: In the exercise we try to factor RSA-100, which we know splits in two prime factors of about equal size (else it would be a weak key), so we can skip this step for now. GMP-ECM One of the tools YAFU uses is GMP-ECM. (http://www.mersenneforum.org/forumdisplay.php?f=55) It gets its name from using the GNU Multiple Precision arithmetic library (GMP) and using the Elliptic Curve Method (ECM) for factoring. Various precompiled binaries for Windows can be downloaded from: http://gilchrist.ca/jeff/factoring/index.html (make sure to select the correct one for the processor in your computer) more information about EMC can be found: https://en.wikipedia.org/wiki/Lenstr..._factorization I'm going to make a very bad analogy (that some people will undoubtedly hate) to very basicly explain how ECM works: We're blindfolded and going to shoot arrows with a bow at several distances (don't try this at home ;) , but we're not sure if there is going to be a target at those distances. If we hit the target we'll hear a loud siren and can take off the blindfold. There are two variables: the distance of the target and our 'luck' to hit it (remember we're blindfolded) First we're going to pull our bowstring only slightly so the arrows hit at around 25 meters (sorry 'mericans, I'm going with the metric system here) We shoot a lot of arrows in random directions in the hope that we'll hit something. After shooting 261 arrows we THINK we should have hit the target by now if there was one around 25 meters to begin with. But we can't say it 100% certain, we might just have missed it. Next we pull the string harder so the arrows hit arround 30 meters. Since we now have to cover a bigger area, we have to shoot more arrows before we can be reasonably sure that the area is covered with arrows and that there is no target there. So we now shoot 513 arrows @30 meters. Still no luck? Shoot 1071 arrows and pull the string even harder so the arrows come down at arround 35 meters. etc. Now for ECM replace 'how hard you have to pull the bow' with B1 meters with digits arrows with curves. Code:
digits optimal B1 expected curves (default parameters for GMP-ECM 7) 20 11,000 107 25 50,000 261 30 250,000 513 35 1,000,000 1,071 40 3,000,000 2,753 45 11,000,000 5,208 50 43,000,000 8,704 55 110,000,000 20,479 60 260,000,000 47,888 65 850,000,000 78,923 70 2,900,000,000 115,153 75 7,600,000,000 211,681 80 25,000,000,000 296,479 So when trying to factor a 150 digit number, we try ECM to 50 digits. If we haven't found a factor by then, we'll switch to the Number Field Sieve (NFS) or SIQS (if the composite is small enough) Step 4 General Number Field Sieve (GNFS) You can now start with Jeffs excellent beginners guide at: http://gilchrist.ca/jeff/factoring/n...ers_guide.html What you need to get started: - Python v2.6 or later from https://www.python.org/downloads/ - A copy of the factmsieve.py script from http://brg.a2hosted.com/oldsite/computing/factmsieve.py - Msieve and GGNFS from http://gilchrist.ca/jeff/factoring/index.html - Notepad++ or some other kind of texteditor https://notepad-plus-plus.org/ - Some basic skills like opening a Command Prompt/Shell/XTerminal Copy factmsieve.py, your Msieve and GGNFS folders to "C:\ggnfs" for easier referencing and navigating. NOTE: If you can't complete these steps like opening a Command Prompt and changing directory in it or editing the .py file in a text editor, you probably do not have the required computer skill to complete the exercise. Feel free to download the more graphic user interface friendly BOINC client or Prime95. After you've completed your first factorization with NFS, you might have noticed NFS is split in a few steps: - Polynomial selection/search - Sieving - Post-processing (consist of 3 steps, relations Filtering, Linear Algebra and Square Root) Read more about it in the readme.nfs file included with msieve or a copy of the text at: https://escatter11.fullerton.edu/nfs...hp?id=549#1373 Example of what factoring RSA-100 with the factmsieve.py might look like: Code:
Tue Feb 06 01:12:16 2018 -> factmsieve.py (v0.76) Tue Feb 06 01:12:16 2018 -> This is client 1 of 1 Tue Feb 06 01:12:16 2018 -> Running on 4 Cores with 1 hyper-thread per Core Tue Feb 06 01:12:16 2018 -> Working with NAME = RSA100 Tue Feb 06 01:12:16 2018 -> Running polynomial selection ... Tue Feb 06 01:12:16 2018 -> msieveSVN988-nogpu-sandybridge-win64 -v -s .\RSA100.dat -l .\RSA100.log -i .\RSA100.ini -nf .\RSA100.fb -d 3 -v -np Tue Feb 06 01:12:16 2018 Tue Feb 06 01:12:16 2018 Tue Feb 06 01:12:16 2018 Msieve v. 1.53 (SVN 988) Tue Feb 06 01:12:16 2018 random seeds: e4b6924c cd9e347d Tue Feb 06 01:12:16 2018 factoring 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 (100 digits) Tue Feb 06 01:12:17 2018 searching for 15-digit factors Tue Feb 06 01:12:17 2018 commencing number field sieve (100-digit input) Tue Feb 06 01:12:17 2018 commencing number field sieve polynomial selection Tue Feb 06 01:12:17 2018 polynomial degree: 4 Tue Feb 06 01:12:17 2018 max stage 1 norm: 1.36e+017 Tue Feb 06 01:12:17 2018 max stage 2 norm: 3.19e+015 Tue Feb 06 01:12:17 2018 min E-value: 9.14e-009 Tue Feb 06 01:12:17 2018 poly select deadline: 1286 Tue Feb 06 01:12:17 2018 time limit set to 0.36 CPU-hours Tue Feb 06 01:12:17 2018 expecting poly E from 1.29e-008 to > 1.49e-008 Tue Feb 06 01:12:17 2018 searching leading coefficients from 1 to 61389535 Tue Feb 06 01:15:16 2018 polynomial selection complete Tue Feb 06 01:15:16 2018 R0: -1500948764615509049688174 Tue Feb 06 01:15:16 2018 R1: 4412959449373 Tue Feb 06 01:15:16 2018 A0: 58495586199562777040895993643 Tue Feb 06 01:15:16 2018 A1: -5772497917414269511266 Tue Feb 06 01:15:16 2018 A2: -8833616819952621 Tue Feb 06 01:15:16 2018 A3: 595392344 Tue Feb 06 01:15:16 2018 A4: 300 Tue Feb 06 01:15:16 2018 skew 4593761.67, size 1.165e-013, alpha -4.779, combined = 1.277e-008 rroots = 2 Tue Feb 06 01:15:16 2018 elapsed time 00:03:00 Tue Feb 06 01:15:16 2018 -> Selected lattice siever: gnfs-lasieve4I12e Tue Feb 06 01:15:16 2018 -> Creating param file to detect parameter changes... Tue Feb 06 01:15:16 2018 -> Running setup ... Tue Feb 06 01:15:16 2018 -> Estimated minimum relations needed: 4.095e+06 Tue Feb 06 01:15:16 2018 -> cleaning up before a restart Tue Feb 06 01:15:16 2018 -> Running lattice siever ... Tue Feb 06 01:15:16 2018 -> entering sieving loop Tue Feb 06 01:15:16 2018 -> making sieve job for q = 900000 in 900000 .. 925000 as file RSA100.job.T0 Tue Feb 06 01:15:16 2018 -> making sieve job for q = 925000 in 925000 .. 950000 as file RSA100.job.T1 Tue Feb 06 01:15:16 2018 -> making sieve job for q = 950000 in 950000 .. 975000 as file RSA100.job.T2 Tue Feb 06 01:15:16 2018 -> making sieve job for q = 975000 in 975000 .. 1000000 as file RSA100.job.T3 Tue Feb 06 01:15:16 2018 -> Lattice sieving algebraic q from 900000 to 1000000. Tue Feb 06 01:15:16 2018 -> gnfs-lasieve4I12e -k -o spairs.out.T0 -v -n0 -a RSA100.job.T0 Tue Feb 06 01:15:16 2018 -> gnfs-lasieve4I12e -k -o spairs.out.T1 -v -n1 -a RSA100.job.T1 Tue Feb 06 01:15:16 2018 -> gnfs-lasieve4I12e -k -o spairs.out.T2 -v -n2 -a RSA100.job.T2 Tue Feb 06 01:15:16 2018 -> gnfs-lasieve4I12e -k -o spairs.out.T3 -v -n3 -a RSA100.job.T3 Tue Feb 06 01:20:20 2018 Found 1093397 relations, 26.7% of the estimated minimum (4095000). Tue Feb 06 01:20:20 2018 LatSieveTime: 303.351 Tue Feb 06 01:20:20 2018 -> making sieve job for q = 1000000 in 1000000 .. 1025000 as file RSA100.job.T0 Tue Feb 06 01:20:20 2018 -> making sieve job for q = 1025000 in 1025000 .. 1050000 as file RSA100.job.T1 Tue Feb 06 01:20:20 2018 -> making sieve job for q = 1050000 in 1050000 .. 1075000 as file RSA100.job.T2 Tue Feb 06 01:20:20 2018 -> making sieve job for q = 1075000 in 1075000 .. 1100000 as file RSA100.job.T3 Tue Feb 06 01:20:20 2018 -> Lattice sieving algebraic q from 1000000 to 1100000. Tue Feb 06 01:20:20 2018 -> gnfs-lasieve4I12e -k -o spairs.out.T0 -v -n0 -a RSA100.job.T0 Tue Feb 06 01:20:20 2018 -> gnfs-lasieve4I12e -k -o spairs.out.T1 -v -n1 -a RSA100.job.T1 Tue Feb 06 01:20:20 2018 -> gnfs-lasieve4I12e -k -o spairs.out.T2 -v -n2 -a RSA100.job.T2 Tue Feb 06 01:20:20 2018 -> gnfs-lasieve4I12e -k -o spairs.out.T3 -v -n3 -a RSA100.job.T3 Tue Feb 06 01:24:35 2018 Found 2173353 relations, 53.1% of the estimated minimum (4095000). Tue Feb 06 01:24:35 2018 LatSieveTime: 255.117 Tue Feb 06 01:24:35 2018 -> making sieve job for q = 1100000 in 1100000 .. 1125000 as file RSA100.job.T0 Tue Feb 06 01:24:35 2018 -> making sieve job for q = 1125000 in 1125000 .. 1150000 as file RSA100.job.T1 Tue Feb 06 01:24:35 2018 -> making sieve job for q = 1150000 in 1150000 .. 1175000 as file RSA100.job.T2 Tue Feb 06 01:24:35 2018 -> making sieve job for q = 1175000 in 1175000 .. 1200000 as file RSA100.job.T3 Tue Feb 06 01:24:35 2018 -> Lattice sieving algebraic q from 1100000 to 1200000. Tue Feb 06 01:24:35 2018 -> gnfs-lasieve4I12e -k -o spairs.out.T0 -v -n0 -a RSA100.job.T0 Tue Feb 06 01:24:35 2018 -> gnfs-lasieve4I12e -k -o spairs.out.T1 -v -n1 -a RSA100.job.T1 Tue Feb 06 01:24:35 2018 -> gnfs-lasieve4I12e -k -o spairs.out.T2 -v -n2 -a RSA100.job.T2 Tue Feb 06 01:24:35 2018 -> gnfs-lasieve4I12e -k -o spairs.out.T3 -v -n3 -a RSA100.job.T3 Tue Feb 06 01:28:58 2018 Found 3262317 relations, 79.7% of the estimated minimum (4095000). Tue Feb 06 01:28:58 2018 LatSieveTime: 263.394 Tue Feb 06 01:28:58 2018 -> making sieve job for q = 1200000 in 1200000 .. 1225000 as file RSA100.job.T0 Tue Feb 06 01:28:58 2018 -> making sieve job for q = 1225000 in 1225000 .. 1250000 as file RSA100.job.T1 Tue Feb 06 01:28:58 2018 -> making sieve job for q = 1250000 in 1250000 .. 1275000 as file RSA100.job.T2 Tue Feb 06 01:28:58 2018 -> making sieve job for q = 1275000 in 1275000 .. 1300000 as file RSA100.job.T3 Tue Feb 06 01:28:58 2018 -> Lattice sieving algebraic q from 1200000 to 1300000. Tue Feb 06 01:28:58 2018 -> gnfs-lasieve4I12e -k -o spairs.out.T0 -v -n0 -a RSA100.job.T0 Tue Feb 06 01:28:58 2018 -> gnfs-lasieve4I12e -k -o spairs.out.T1 -v -n1 -a RSA100.job.T1 Tue Feb 06 01:28:58 2018 -> gnfs-lasieve4I12e -k -o spairs.out.T2 -v -n2 -a RSA100.job.T2 Tue Feb 06 01:28:58 2018 -> gnfs-lasieve4I12e -k -o spairs.out.T3 -v -n3 -a RSA100.job.T3 Tue Feb 06 01:33:26 2018 Found 4361978 relations, 106.5% of the estimated minimum (4095000). Tue Feb 06 01:33:26 2018 -> msieveSVN988-nogpu-sandybridge-win64 -v -s .\RSA100.dat -l .\RSA100.log -i .\RSA100.ini -nf .\RSA100.fb -t 4 -nc1 Tue Feb 06 01:33:26 2018 Tue Feb 06 01:33:26 2018 Tue Feb 06 01:33:26 2018 Msieve v. 1.53 (SVN 988) Tue Feb 06 01:33:26 2018 random seeds: 20c66f04 aedf511c Tue Feb 06 01:33:26 2018 factoring 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 (100 digits) Tue Feb 06 01:33:27 2018 searching for 15-digit factors Tue Feb 06 01:33:27 2018 commencing number field sieve (100-digit input) Tue Feb 06 01:33:27 2018 R0: -1500948764615509049688174 Tue Feb 06 01:33:27 2018 R1: 4412959449373 Tue Feb 06 01:33:27 2018 A0: 58495586199562777040895993643 Tue Feb 06 01:33:27 2018 A1: -5772497917414269511266 Tue Feb 06 01:33:27 2018 A2: -8833616819952621 Tue Feb 06 01:33:27 2018 A3: 595392344 Tue Feb 06 01:33:27 2018 A4: 300 Tue Feb 06 01:33:27 2018 skew 4593761.67, size 1.165e-013, alpha -4.779, combined = 1.277e-008 rroots = 2 Tue Feb 06 01:33:27 2018 Tue Feb 06 01:33:27 2018 commencing relation filtering Tue Feb 06 01:33:27 2018 estimated available RAM is 16364.5 MB Tue Feb 06 01:33:27 2018 commencing duplicate removal, pass 1 Tue Feb 06 01:33:55 2018 found 357539 hash collisions in 4361977 relations Tue Feb 06 01:33:58 2018 added 146029 free relations Tue Feb 06 01:33:58 2018 commencing duplicate removal, pass 2 Tue Feb 06 01:34:00 2018 found 255002 duplicates and 4253004 unique relations Tue Feb 06 01:34:00 2018 memory use: 16.3 MB Tue Feb 06 01:34:00 2018 reading ideals above 100000 Tue Feb 06 01:34:00 2018 commencing singleton removal, initial pass Tue Feb 06 01:34:24 2018 memory use: 94.1 MB Tue Feb 06 01:34:24 2018 reading all ideals from disk Tue Feb 06 01:34:24 2018 memory use: 130.9 MB Tue Feb 06 01:34:24 2018 keeping 4582257 ideals with weight <= 200, target excess is 21260 Tue Feb 06 01:34:24 2018 commencing in-memory singleton removal Tue Feb 06 01:34:24 2018 begin with 4253004 relations and 4582257 unique ideals Tue Feb 06 01:34:25 2018 reduce to 1675133 relations and 1462605 ideals in 13 passes Tue Feb 06 01:34:25 2018 max relations containing the same ideal: 106 Tue Feb 06 01:34:26 2018 removing 422012 relations and 328079 ideals in 93933 cliques Tue Feb 06 01:34:26 2018 commencing in-memory singleton removal Tue Feb 06 01:34:26 2018 begin with 1253121 relations and 1462605 unique ideals Tue Feb 06 01:34:26 2018 reduce to 1170138 relations and 1045605 ideals in 9 passes Tue Feb 06 01:34:26 2018 max relations containing the same ideal: 83 Tue Feb 06 01:34:26 2018 removing 338513 relations and 244580 ideals in 93933 cliques Tue Feb 06 01:34:26 2018 commencing in-memory singleton removal Tue Feb 06 01:34:26 2018 begin with 831625 relations and 1045605 unique ideals Tue Feb 06 01:34:26 2018 reduce to 756896 relations and 720048 ideals in 9 passes Tue Feb 06 01:34:26 2018 max relations containing the same ideal: 61 Tue Feb 06 01:34:27 2018 removing 71565 relations and 59379 ideals in 12186 cliques Tue Feb 06 01:34:27 2018 commencing in-memory singleton removal Tue Feb 06 01:34:27 2018 begin with 685331 relations and 720048 unique ideals Tue Feb 06 01:34:27 2018 reduce to 680596 relations and 655846 ideals in 7 passes Tue Feb 06 01:34:27 2018 max relations containing the same ideal: 57 Tue Feb 06 01:34:27 2018 relations with 0 large ideals: 423 Tue Feb 06 01:34:27 2018 relations with 1 large ideals: 268 Tue Feb 06 01:34:27 2018 relations with 2 large ideals: 3711 Tue Feb 06 01:34:27 2018 relations with 3 large ideals: 25969 Tue Feb 06 01:34:27 2018 relations with 4 large ideals: 92944 Tue Feb 06 01:34:27 2018 relations with 5 large ideals: 186479 Tue Feb 06 01:34:27 2018 relations with 6 large ideals: 198757 Tue Feb 06 01:34:27 2018 relations with 7+ large ideals: 172045 Tue Feb 06 01:34:27 2018 commencing 2-way merge Tue Feb 06 01:34:27 2018 reduce to 399830 relation sets and 375080 unique ideals Tue Feb 06 01:34:27 2018 commencing full merge Tue Feb 06 01:34:30 2018 memory use: 45.0 MB Tue Feb 06 01:34:30 2018 found 194296 cycles, need 191280 Tue Feb 06 01:34:30 2018 weight of 191280 cycles is about 13655704 (71.39/cycle) Tue Feb 06 01:34:30 2018 distribution of cycle lengths: Tue Feb 06 01:34:30 2018 1 relations: 16616 Tue Feb 06 01:34:30 2018 2 relations: 17238 Tue Feb 06 01:34:30 2018 3 relations: 17900 Tue Feb 06 01:34:30 2018 4 relations: 17492 Tue Feb 06 01:34:30 2018 5 relations: 16786 Tue Feb 06 01:34:30 2018 6 relations: 15898 Tue Feb 06 01:34:30 2018 7 relations: 14833 Tue Feb 06 01:34:30 2018 8 relations: 13373 Tue Feb 06 01:34:30 2018 9 relations: 11762 Tue Feb 06 01:34:30 2018 10+ relations: 49382 Tue Feb 06 01:34:30 2018 heaviest cycle: 23 relations Tue Feb 06 01:34:30 2018 commencing cycle optimization Tue Feb 06 01:34:30 2018 start with 1310599 relations Tue Feb 06 01:34:32 2018 pruned 35991 relations Tue Feb 06 01:34:32 2018 memory use: 41.0 MB Tue Feb 06 01:34:32 2018 distribution of cycle lengths: Tue Feb 06 01:34:32 2018 1 relations: 16616 Tue Feb 06 01:34:32 2018 2 relations: 17567 Tue Feb 06 01:34:32 2018 3 relations: 18520 Tue Feb 06 01:34:32 2018 4 relations: 17917 Tue Feb 06 01:34:32 2018 5 relations: 17400 Tue Feb 06 01:34:32 2018 6 relations: 16332 Tue Feb 06 01:34:32 2018 7 relations: 15226 Tue Feb 06 01:34:32 2018 8 relations: 13614 Tue Feb 06 01:34:32 2018 9 relations: 11856 Tue Feb 06 01:34:32 2018 10+ relations: 46232 Tue Feb 06 01:34:32 2018 heaviest cycle: 23 relations Tue Feb 06 01:34:32 2018 RelProcTime: 65 Tue Feb 06 01:34:32 2018 elapsed time 00:01:06 Tue Feb 06 01:34:32 2018 LatSieveTime: 333.293 Tue Feb 06 01:34:32 2018 -> Running matrix solving step ... Tue Feb 06 01:34:32 2018 -> msieveSVN988-nogpu-sandybridge-win64 -v -s .\RSA100.dat -l .\RSA100.log -i .\RSA100.ini -nf .\RSA100.fb -t 4 -nc2 Tue Feb 06 01:34:32 2018 Tue Feb 06 01:34:32 2018 Tue Feb 06 01:34:32 2018 Msieve v. 1.53 (SVN 988) Tue Feb 06 01:34:32 2018 random seeds: 892f5894 b3427c5a Tue Feb 06 01:34:32 2018 factoring 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 (100 digits) Tue Feb 06 01:34:32 2018 searching for 15-digit factors Tue Feb 06 01:34:32 2018 commencing number field sieve (100-digit input) Tue Feb 06 01:34:32 2018 R0: -1500948764615509049688174 Tue Feb 06 01:34:32 2018 R1: 4412959449373 Tue Feb 06 01:34:32 2018 A0: 58495586199562777040895993643 Tue Feb 06 01:34:32 2018 A1: -5772497917414269511266 Tue Feb 06 01:34:32 2018 A2: -8833616819952621 Tue Feb 06 01:34:32 2018 A3: 595392344 Tue Feb 06 01:34:32 2018 A4: 300 Tue Feb 06 01:34:32 2018 skew 4593761.67, size 1.165e-013, alpha -4.779, combined = 1.277e-008 rroots = 2 Tue Feb 06 01:34:32 2018 Tue Feb 06 01:34:32 2018 commencing linear algebra Tue Feb 06 01:34:32 2018 read 191280 cycles Tue Feb 06 01:34:32 2018 cycles contain 662336 unique relations Tue Feb 06 01:34:36 2018 read 662336 relations Tue Feb 06 01:34:36 2018 using 20 quadratic characters above 4294917295 Tue Feb 06 01:34:39 2018 building initial matrix Tue Feb 06 01:34:42 2018 memory use: 82.0 MB Tue Feb 06 01:34:42 2018 read 191280 cycles Tue Feb 06 01:34:42 2018 matrix is 191099 x 191280 (57.6 MB) with weight 18410260 (96.25/col) Tue Feb 06 01:34:42 2018 sparse part has weight 12990347 (67.91/col) Tue Feb 06 01:34:43 2018 filtering completed in 2 passes Tue Feb 06 01:34:43 2018 matrix is 190998 x 191179 (57.6 MB) with weight 18405654 (96.27/col) Tue Feb 06 01:34:43 2018 sparse part has weight 12988943 (67.94/col) Tue Feb 06 01:34:43 2018 matrix starts at (0, 0) Tue Feb 06 01:34:43 2018 matrix is 190998 x 191179 (57.6 MB) with weight 18405654 (96.27/col) Tue Feb 06 01:34:43 2018 sparse part has weight 12988943 (67.94/col) Tue Feb 06 01:34:43 2018 saving the first 48 matrix rows for later Tue Feb 06 01:34:43 2018 matrix includes 64 packed rows Tue Feb 06 01:34:44 2018 matrix is 190950 x 191179 (55.3 MB) with weight 14528028 (75.99/col) Tue Feb 06 01:34:44 2018 sparse part has weight 12576419 (65.78/col) Tue Feb 06 01:34:44 2018 using block size 8192 and superblock size 589824 for processor cache size 6144 kB Tue Feb 06 01:34:44 2018 commencing Lanczos iteration Tue Feb 06 01:34:44 2018 memory use: 41.9 MB Tue Feb 06 01:34:50 2018 linear algebra at 6.3%, ETA 0h 1m Tue Feb 06 01:36:24 2018 lanczos halted after 3021 iterations (dim = 190947) Tue Feb 06 01:36:24 2018 recovered 31 nontrivial dependencies Tue Feb 06 01:36:24 2018 BLanczosTime: 112 Tue Feb 06 01:36:24 2018 elapsed time 00:01:52 Tue Feb 06 01:36:24 2018 -> Running square root step ... Tue Feb 06 01:36:24 2018 -> msieveSVN988-nogpu-sandybridge-win64 -v -s .\RSA100.dat -l .\RSA100.log -i .\RSA100.ini -nf .\RSA100.fb -t 4 -nc3 Tue Feb 06 01:36:24 2018 Tue Feb 06 01:36:24 2018 Tue Feb 06 01:36:24 2018 Msieve v. 1.53 (SVN 988) Tue Feb 06 01:36:24 2018 random seeds: 906f48bc a8e42684 Tue Feb 06 01:36:24 2018 factoring 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 (100 digits) Tue Feb 06 01:36:24 2018 searching for 15-digit factors Tue Feb 06 01:36:24 2018 commencing number field sieve (100-digit input) Tue Feb 06 01:36:24 2018 R0: -1500948764615509049688174 Tue Feb 06 01:36:24 2018 R1: 4412959449373 Tue Feb 06 01:36:24 2018 A0: 58495586199562777040895993643 Tue Feb 06 01:36:24 2018 A1: -5772497917414269511266 Tue Feb 06 01:36:24 2018 A2: -8833616819952621 Tue Feb 06 01:36:24 2018 A3: 595392344 Tue Feb 06 01:36:24 2018 A4: 300 Tue Feb 06 01:36:24 2018 skew 4593761.67, size 1.165e-013, alpha -4.779, combined = 1.277e-008 rroots = 2 Tue Feb 06 01:36:24 2018 Tue Feb 06 01:36:24 2018 commencing square root phase Tue Feb 06 01:36:24 2018 reading relations for dependency 1 Tue Feb 06 01:36:25 2018 read 95500 cycles Tue Feb 06 01:36:25 2018 cycles contain 330640 unique relations Tue Feb 06 01:36:27 2018 read 330640 relations Tue Feb 06 01:36:27 2018 multiplying 330640 relations Tue Feb 06 01:36:32 2018 multiply complete, coefficients have about 12.86 million bits Tue Feb 06 01:36:35 2018 initial square root is modulo 24486871 Tue Feb 06 01:36:41 2018 GCD is N, no factor found Tue Feb 06 01:36:41 2018 reading relations for dependency 2 Tue Feb 06 01:36:41 2018 read 95075 cycles Tue Feb 06 01:36:41 2018 cycles contain 329798 unique relations Tue Feb 06 01:36:43 2018 read 329798 relations Tue Feb 06 01:36:44 2018 multiplying 329798 relations Tue Feb 06 01:36:48 2018 multiply complete, coefficients have about 12.82 million bits Tue Feb 06 01:36:48 2018 initial square root is modulo 23389187 Tue Feb 06 01:36:54 2018 sqrtTime: 30 Tue Feb 06 01:36:54 2018 p50 factor: 37975227936943673922808872755445627854565536638199 Tue Feb 06 01:36:54 2018 p50 factor: 40094690950920881030683735292761468389214899724061 Tue Feb 06 01:36:54 2018 elapsed time 00:00:30 |
|
|
|
2018-02-22, 03:01
|
#2 |
|
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88
11100001101012 Posts |
Note: if you have yafu installed for the prefactoring, then factmsieve.py is redundant. Yafu can automate the NFS as well as it can the ECM.
|
|
|
|
|
2018-05-10, 09:56
|
#3 |
|
"Victor de Hollander"
Aug 2011
the Netherlands
32×131 Posts |
Windows install guide for GGNFS+msieve+factmsieve.py
Jeffs site is temporary down, so users can't access the beginners guide and the links to all the precompiled executables. So here a short version for Windows x64.
Step 1) Download and install Python 3.6 Here is a link to the installer (~30MB): https://www.python.org/ftp/python/3.....6.5-amd64.exe Step 2) Download GGNFS.zip (attached to this post, 2.8MB) and extract it to C:\GGNFS . Import: extract it to that exact path and don't change any filenames. If you do want to put it in a other path, you'll need to edit the python script to point to the right paths/filenames (lines 63,64,104,117,118). The zip includes the msieve exe, the python (factmsieve-0.86.py) and lasieve4 sievers, readme files for information and a couple of RSA.n files which has numbers to factor. The dir C:\GGNFS should now look like this: Code:
-a---- 10-5-2018 1:52 1793 Authors-GMPECM.txt -a---- 10-5-2018 1:52 4272 Authors-MPIR.txt -a---- 10-5-2018 1:49 101203 Changelog-msieve.txt -a---- 10-5-2018 1:52 35819 Copying-GMPECM.txt -a---- 10-5-2018 1:52 35819 Copying-MPIR.txt -a---- 10-5-2018 2:01 3700 def-nm-params.txt -a---- 10-5-2018 2:00 4968 def-par.txt -a---- 10-5-2018 3:57 77305 factmsieve-0.86.py -a---- 10-5-2018 1:55 0 gnfs-lasieve4-win64-core2-asm64.txt -a---- 19-10-2016 18:26 94208 gnfs-lasieve4I11e.exe -a---- 19-10-2016 18:26 649290 gnfs-lasieve4I11e_argfix.exe -a---- 19-10-2016 18:26 94208 gnfs-lasieve4I12e.exe -a---- 19-10-2016 18:26 618986 gnfs-lasieve4I12e_argfix.exe -a---- 19-10-2016 18:26 94208 gnfs-lasieve4I13e.exe -a---- 19-10-2016 18:26 603608 gnfs-lasieve4I13e_argfix.exe -a---- 19-10-2016 18:26 94208 gnfs-lasieve4I14e.exe -a---- 19-10-2016 18:26 596268 gnfs-lasieve4I14e_argfix.exe -a---- 19-10-2016 18:26 94208 gnfs-lasieve4I15e.exe -a---- 19-10-2016 18:26 592342 gnfs-lasieve4I15e_argfix.exe -a---- 19-10-2016 18:26 94208 gnfs-lasieve4I16e.exe -a---- 19-10-2016 18:26 589819 gnfs-lasieve4I16e_argfix.exe -a---- 10-5-2018 4:01 3789 msieve-1.53-SVN998-win64-core2-options.txt -a---- 15-10-2016 7:16 1396224 msieve-1.53-SVN998-win64-core2.exe -a---- 10-5-2018 1:53 37678 Readme-GMPECM.txt -a---- 10-5-2018 1:53 4075 Readme-MPIR.txt -a---- 10-5-2018 1:47 25825 Readme-msieve.txt -a---- 10-5-2018 1:48 59002 Readme-NFS.txt -a---- 10-5-2018 1:48 8144 Readme-QS.txt -a---- 5-2-2018 15:27 102 RSA100.n -a---- 5-2-2018 18:45 112 RSA110.n -a---- 5-2-2018 22:42 122 RSA120.n Step 4) navigate to C:\GGNFS Code:
cd C:\GGNFS Code:
python factmsieve-0.86.py RSA100.n Lines like this indicate poly search: Code:
-> msieve-1.53-SVN998-win64-core2 -s .\RSA100.dat.T0 -l .\RSA100.log.T0 -i .\RSA100.ini.T0 -nf .\RSA100.fb.T0 -np 1,100 -v > .\RSA100.msp.T0 Code:
Thu May 10 02:04:20 2018 -> entering sieving loop Thu May 10 02:04:20 2018 -> making sieve job for q = 900000 in 900000 .. 925000 as file RSA100.job.T0 Thu May 10 02:04:20 2018 -> making sieve job for q = 925000 in 925000 .. 950000 as file RSA100.job.T1 Thu May 10 02:04:20 2018 -> making sieve job for q = 950000 in 950000 .. 975000 as file RSA100.job.T2 Thu May 10 02:04:20 2018 -> making sieve job for q = 975000 in 975000 .. 1000000 as file RSA100.job.T3 Once it is done you should find the factors at the bottom of the log (RSA100.log) 7) You can delete all the RSA100.xxxx and spairs.gz temporary files if you like. Last fiddled with by VictordeHolland on 2018-05-10 at 09:59 |
|
|
|
|
2018-05-10, 10:47
|
#4 |
|
"Victor de Hollander"
Aug 2011
the Netherlands
117910 Posts |
Q) Why no separate binaries for Sandy-/Ivybridge/xxxx architecture?
A1) I wanted to provide a single package that works for (almost) everybody and the forum has a 4MB attachment limit. A2) Most of the time is spent sieving. The lasieve4 sievers use assembly (asm) code that was written in the athlon/core2 era, since the asm code isn't updated in several years, compiling them for newer achitectures provide little to no performance benefits. I ran RSA100 with 3 combinations of msieve/lasieve4: msieve-1.53-SVN998-win64-core2 + lasieve4-core2-win64-asm64 msieve-1.53-SVN998-win64-nehalem + lasieve4-westmere-win64-asm64 msieve-1.53-SVN998-win64-ivybridge + lasieve4-ivybridge-win64-asm64 and the sievers performed within ~3% of each other (4048, 3977, 3925 CPUsec). The Msieve Polysearch, Filtering and LA performed within 1 second of eachother. Q) Why no binaries for Win32? A) The 64bit sievers with assembly are twice as fast as the 32bit. If you still have a 32bit Windows installation you should consider updating to a 64bit OS. Q) I don't see 100% CPU load? A1) Your CPU probably has more than 4 cores, or has HyperThreading (HT). Consider editing lines 67 and 68 of the python script: Code:
# Set the number of CPU cores and threads NUM_CORES = 4 THREADS_PER_CORE = 1 Q) On what hardware did you test it? A) Window 7 x64, Python 3.6, Intel Core i5-2500k @4.0GHz (SandyBridge) Windows 10 x64 (1709), Python 3.6.5, Intel Core i7-3770k @3.5GHz (IvyBridge) Windows 10 x64 (1709), Python 3.6.5, Intel Core2Duo E6850 @3GHz (C2D Conroe 65nm) Q) I get an error at the end of the python script? A) The code for calculating the elapsed time and estimated processor speed is not functioning correctly. The script should still work and you'll find the factors in the log. Q) I can't launch python from the command/terminal/power shell A) If "python factmsieve-0.86.py RSA100.n" doesn't work, try "py factmsieve-0.86.py" Last fiddled with by VictordeHolland on 2018-05-10 at 10:47 |
|
|
|
|
2018-05-11, 12:21
|
#5 |
|
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
11·557 Posts |
It is worth noting that these sievers are greatly helped by hyperthreading when available. This will be related to the old asm code needing updating.
|
|
|
|
2018-05-13, 16:17
|
#6 | |
|
"Victor de Hollander"
Aug 2011
the Netherlands
32·131 Posts |
Quote:
RSA100 3770k @3.5GHz 4c 4t (1 thread/core) Code:
Thu May 10 11:40:05 2018 -> entering sieving loop ... Thu May 10 12:00:06 2018 Found 4361978 relations, 106.5% of the estimated minimum (4095000). 4c 8t (2 threads/core) Code:
Thu May 10 12:10:10 2018 -> entering sieving loop ... Thu May 10 12:25:05 2018 Found 4361980 relations, 106.5% of the estimated minimum (4095000). 895/1201 seconds = 0.745 so HT increases throughput by (1/0.745=1.342) 34%! |
|
|
|
|
|
2018-05-16, 14:37
|
#7 |
|
"Victor de Hollander"
Aug 2011
the Netherlands
49B16 Posts |
Linux (Ubuntu) guides by EdH
The user EdH made excellent guides for setting up a factoring environment on Linux (Ubuntu), his guides are in the Blogorrhea subforum. I can understand that might not be the first place beginners will look, so here are link to his guides (and the order you probably want to install them)
1) GMP (GNU Math Bignum) libraries How I Install GMP onto my Ubuntu Machines 2) GMP-ECM How I Install GMP-ECM onto my Ubuntu Machines 3) Msieve How I Install msieve onto my Ubuntu Machines 4) GGNFS How I Install ggnfs onto my Ubuntu Machines 5) YAFU How I install YAFU onto my Ubuntu Machines 6) CADO-NFS How I Install CADO-NFS onto my Ubuntu Machines 7) Optional (using multiple machines) How I Run a Larger Factorization Using Msieve, gnfs and factmsieve.py on Several Ubuntu Machines and How I Run a Larger Factorization Via CADO-NFS on Several Ubuntu Machines |
|
|
|
|
2018-05-23, 15:11
|
#8 |
|
"Victor de Hollander"
Aug 2011
the Netherlands
32×131 Posts |
How to install YAFU on Windows
Ok, you own a PC with Windows and you want to try the factoring program "YAFU" on it. But you don't want to go to the trouble of compiling the executables from source/git/SVN etc.
No problemo! 1). Download GGNFS.zip and extract to C:\GGNFS (GGNFS.zip is attached to post #3 of this thread) You actually only need the "gnfs-lasieve4IXXe.exe" executables (with XX the different sievers, 11-16) for YAFU. 2). Download GMP-ECM.zip and extract to C:\GMP-ECM (GMP-ECM.zip is attached to this post) Inside the GMP-ECM.zip you'll find the ecm.exe and some text documents with the licence, the authors, changelog, ect. GMP-ECM 7.0.4 release (SVN2991) compiled with GMP6.1.2 for Windows 64bit (Intel Core2Duo and newer) Code:
Directory: C:\GMP-ECM Mode LastWriteTime Length Name ---- ------------- ------ ---- -a--- 23-05-18 15:40 1795 Authors.txt -a--- 23-05-18 15:40 637106 ChangeLog.txt -a--- 23-05-18 15:40 7804 Copying.lib.txt -a--- 23-05-18 15:40 35821 Copying.txt -a--- 11-05-18 0:55 3846004 ecm.exe -a--- 13-05-18 14:26 2568 GMP-ECM-7.0.4-release-SVN2991-GMP6.1.2-win64-core2.txt -a--- 23-05-18 15:40 13745 News.txt -a--- 23-05-18 15:39 5914 Readme.lib.txt -a--- 23-05-18 15:40 37604 Readme.txt (YAFU.zip is also attached) YAFU.zip included the latest release version 1.34.5 (NOT the latest trunk or wip version) for Windows 64bit. Code:
Directory: C:\YAFU Mode LastWriteTime Length Name ---- ------------- ------ ---- -a--- 06-03-13 14:28 49887 Changes.txt -a--- 25-02-13 9:14 35864 docfile.txt -a--- 23-05-18 15:54 8998 Readme.txt -a--- 06-03-13 16:58 3894554 YAFU-1.34.5-win64.exe -a--- 23-05-18 15:59 132 yafu.ini C:\GGNFS\ C:\GMP-ECM\ C:\YAFU\ 5). Open yafu.ini and check if it points to the right locations of the executables Code:
ggnfs_dir=C:\GGNFS\ ecm_path=C:\GMP-ECM\ecm.exe 6). Launch and test cases Open a Commandprompt (cmd.exe) or PowerShell (Windowskey+X should give you a shortcut to PS in Windows 10) Change dir to YAFU Code:
cd C:\YAFU Code:
YAFU-1.34.5-win64.exe factor(2056802480868100646375721251575555494408897387375737955882170045672576386016591560879707933101909539325829251496440620798637813) Code:
nfs(9379745492489847473195765085744210645855556204246905462578925932774371960871599319713301154409) |
|
|
|
|
2018-07-05, 13:03
|
#9 |
|
"Victor de Hollander"
Aug 2011
the Netherlands
100100110112 Posts |
Apparently there are still people using 32bit versions of Windows.
The 7zip file attached to this post contains: Code:
Mode LastWriteTime Length Name ---- ------------- ------ ---- d---- 04-07-18 13:04 GMP-ECM7.0.4-win32 d---- 04-07-18 13:03 Lasieve4-win32-P4 d---- 02-07-18 15:59 Msieve-1.52-win32 d---- 04-07-18 13:10 YAFU-1.34.5-win32 -a--- 04-07-18 13:03 77423 factmsieve-0.86.py -a--- 05-02-18 15:27 102 RSA100.n -a--- 05-02-18 18:45 112 RSA110.n -a--- 05-02-18 22:42 122 RSA120.n |
|
|
|
|
2018-07-05, 18:32
|
#10 |
|
"Victor de Hollander"
Aug 2011
the Netherlands
32×131 Posts |
Q: How much slower is the 32-bit siever compared to the 64-bit (asm) siever?
RSA-100 on a Intel Core i5 2500k @4.0GHz (both 12e siever) 64-bit (asm) siever Code:
02:04:20 -> entering sieving loop 02:22:49 Found 4361978 relations, 106.5% of the estimated minimum (4095000). 32-bit siever Code:
15:02:35 -> entering sieving loop 15:29:53 Found 4361942 relations, 106.5% of the estimated minimum (4095000). Ok, so the 64-bit asm siever is not twice as fast as I said in a earlier post, but it is definitely faster. |
|
|
|
|
2018-11-29, 17:26
|
#11 |
"Carlos Pinho"
Oct 2011
Milton Keynes, UK
120548 Posts |
How do I tell yafu to use msieve from ggnfs folder instead of the embedded one?
Also will LA run in 8 threads with the following command line for a batch of numbers? Code:
start /min /low YAFU-1.34.5-win64.exe "nfs(@)" -batchfile in.bat -threads 8 |
|
|
|
 |
| Thread Tools | |
Similar Threads
|
||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| Getting started | 10metreh | Aliquot Sequences | 20 | 2021-07-27 12:51 |
| Getting started | XYYXF | XYYXF Project | 11 | 2020-07-14 01:48 |
| 2^772+1 has started | fivemack | NFSNET Discussion | 27 | 2007-07-07 15:53 |
| How do I get started? | KEP | Operation Billion Digits | 3 | 2005-05-09 08:02 |
| Getting Started / Welcome | Citrix | Prime Sierpinski Project | 0 | 2004-06-18 22:25 |
