mersenneforum.org newb needs help - factoring RSA512 error
 Register FAQ Search Today's Posts Mark Forums Read

 2014-11-03, 09:49 #1 barthmaul   Nov 2014 3 Posts newb needs help - factoring RSA512 error Hello, i'm new in this bussiness and i have a problem with factoring RSA512. Polynomial selection - 5 days on Tesla K20 , sieving 4 days on 5 servers (7 cores each), found 444870517 relations, 737.5% of the estimated minimum (60323676). And now i have someting like this : Code: Sat Nov 01 09:09:04 2014 -> Running matrix solving step ... Sat Nov 01 09:09:04 2014 Sat Nov 01 09:09:04 2014 Sat Nov 01 09:09:04 2014 Msieve v. 1.50 (SVN Official Release) Sat Nov 01 09:09:04 2014 random seeds: 041eb5f8 8f6798e7 Sat Nov 01 09:09:04 2014 factoring 10807561426505345052016343192843324674003752183584439431855278468457615148415828451132399374576833616654358191612829629246076273020826999666784140736359641 (155 digits) Sat Nov 01 09:09:05 2014 searching for 15-digit factors Sat Nov 01 09:09:06 2014 commencing number field sieve (155-digit input) Sat Nov 01 09:09:06 2014 R0: -1148862696576247991128008723087 Sat Nov 01 09:09:06 2014 R1: 132920060949705133 Sat Nov 01 09:09:06 2014 A0: -175221820052441334929633397566648043896 Sat Nov 01 09:09:06 2014 A1: 1066282257861769640439151209947372 Sat Nov 01 09:09:06 2014 A2: 371117678219451318054521018 Sat Nov 01 09:09:06 2014 A3: 11720645312502938107 Sat Nov 01 09:09:06 2014 A4: -718769358546 Sat Nov 01 09:09:06 2014 A5: 5400 Sat Nov 01 09:09:06 2014 skew 20962266.38, size 7.259e-015, alpha -8.407, combined = 3.530e-012 rroots = 5 Sat Nov 01 09:09:06 2014 Sat Nov 01 09:09:06 2014 commencing linear algebra Sat Nov 01 09:09:06 2014 read 695609 cycles Sat Nov 01 09:09:07 2014 cycles contain 1363559 unique relations Sat Nov 01 09:13:14 2014 read 1363559 relations Sat Nov 01 09:13:15 2014 using 20 quadratic characters above 536867844 Sat Nov 01 09:13:24 2014 building initial matrix Sat Nov 01 09:13:29 2014 memory use: 176.6 MB Sat Nov 01 09:13:30 2014 read 695609 cycles Sat Nov 01 09:13:30 2014 matrix is 54839 x 695609 (32.7 MB) with weight 493777 ( 0.71/col) Sat Nov 01 09:13:30 2014 sparse part has weight 218571 ( 0.31/col) Sat Nov 01 09:13:30 2014 filtering completed in 2 passes Sat Nov 01 09:13:30 2014 matrix is 34890 x 11904 (1.2 MB) with weight 380655 (31.98/col) Sat Nov 01 09:13:30 2014 sparse part has weight 169594 (14.25/col) Sat Nov 01 09:13:30 2014 matrix starts at (0, 0) Sat Nov 01 09:13:30 2014 matrix is 34890 x 11904 (1.2 MB) with weight 380655 (31.98/col) Sat Nov 01 09:13:30 2014 sparse part has weight 169594 (14.25/col) Sat Nov 01 09:13:30 2014 matrix needs more columns than rows; try adding 2-3% more relations When I try to restart the job (on one server only) i have something like this: Code: Mon Nov 03 08:21:03 2014 -> factmsieve.py (v0.76) Mon Nov 03 08:21:03 2014 -> This is client 1 of 1 Mon Nov 03 08:21:03 2014 -> Running on 7 Cores with 1 hyper-thread per Core Mon Nov 03 08:21:03 2014 -> Working with NAME = liczba512 Mon Nov 03 08:21:03 2014 -> Selected lattice siever: gnfs-lasieve4I14e Mon Nov 03 08:21:03 2014 -> Creating param file to detect parameter changes... Mon Nov 03 08:21:03 2014 -> Running setup ... Mon Nov 03 08:21:03 2014 -> Estimated minimum relations needed: 6.03237e+07 Mon Nov 03 08:21:03 2014 -> cleaning up before a restart Mon Nov 03 08:21:05 2014 -> Running lattice siever ... Mon Nov 03 08:21:05 2014 -> entering sieving loop Mon Nov 03 08:21:05 2014 -> Running matrix solving step ... Mon Nov 03 08:21:05 2014 Mon Nov 03 08:21:05 2014 Mon Nov 03 08:21:05 2014 Msieve v. 1.50 (SVN Official Release) Mon Nov 03 08:21:05 2014 random seeds: 19fe11e8 b45df540 Mon Nov 03 08:21:05 2014 factoring 10807561426505345052016343192843324674003752183584439431855278468457615148415828451132399374576833616654358191612829629246076273020826999666784140736359641 (155 digits) Mon Nov 03 08:21:06 2014 searching for 15-digit factors Mon Nov 03 08:21:07 2014 commencing number field sieve (155-digit input) Mon Nov 03 08:21:07 2014 R0: -1148862696576247991128008723087 Mon Nov 03 08:21:07 2014 R1: 132920060949705133 Mon Nov 03 08:21:07 2014 A0: -175221820052441334929633397566648043896 Mon Nov 03 08:21:07 2014 A1: 1066282257861769640439151209947372 Mon Nov 03 08:21:07 2014 A2: 371117678219451318054521018 Mon Nov 03 08:21:07 2014 A3: 11720645312502938107 Mon Nov 03 08:21:07 2014 A4: -718769358546 Mon Nov 03 08:21:07 2014 A5: 5400 Mon Nov 03 08:21:07 2014 skew 20962266.38, size 7.259e-015, alpha -8.407, combined = 3.530e-012 rroots = 5 Mon Nov 03 08:21:07 2014 Mon Nov 03 08:21:07 2014 commencing linear algebra Mon Nov 03 08:21:07 2014 read 11904 cycles Mon Nov 03 08:21:07 2014 cycles contain 11904 unique relations Mon Nov 03 08:21:07 2014 read 0 relations Mon Nov 03 08:21:07 2014 error: cannot locate relation 65531248 How to add 2-3% relations ? Please help :)
 2014-11-03, 15:59 #2 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 485610 Posts I have run into this when I have done too much over-sieving. Try to cut a 65M chunk out of the 400M+ current file.
 2014-11-03, 19:21 #3 VBCurtis     "Curtis" Feb 2005 Riverside, CA 10101010111112 Posts I'm with Ed; one day on 5 servers likely would have been sufficient. You could also try building the matrix with target-density=128 to encourage it to work harder in filtering. I would try 100M relations from your file, and target-density 128. The matrix size for GNFS-155 is usually 4M by 4M to 5M by 5M when not oversieved; yours is less than one-tenth that. Setting target-density to 128 instead of default 70 will build a smaller matrix, but I don't know how small- perhaps 3M by 3M? If you figure out the flags in msieve and try it, please let me know what comes out.
 2014-11-03, 21:34 #4 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
 2014-11-04, 06:34 #5 debrouxl     Sep 2009 17228 Posts 100M relations for a 512-bit RSA key would probably still bring filtering to its knees. RSALS, and two later solo 512-bit RSA key factorizations of mine, usually used up to 70M raw relations, which is already sizable oversieving, and reduces the matrix's size quite a bit. Indeed, the 7x oversieved dataset could be interesting for analysis purposes, though the filtering collapse already occurs with much smaller datasets
 2014-11-04, 06:57 #6 VBCurtis     "Curtis" Feb 2005 Riverside, CA 5,471 Posts His log suggests 60M minimum relations, which suggests it picked 30-bit large primes, and 75-80M relations minimum would be needed to build any matrix. But I've hacked those settings on my own script, so maybe this is a 29-bit job after all? OP- My advice assumed the *.fb file contains "SALPMAX 1073741824" and SRLPMAX the same. That number is 2^30. If that number is around 500M (2^29, specifically), then 100M relations is indeed way too many to test out matrix building and the other advice in this thread should be your plan.
 2014-11-04, 12:18 #7 debrouxl     Sep 2009 2×3×163 Posts Code: Sat Nov 01 09:13:15 2014 using 20 quadratic characters above 536867844 suggests 29-bit LPs instead I've checked my post-processing logs for 29-bit LPs tasks and 30-bit LPs tasks to confirm: the numbers on those lines are always slighly less than 2^(number of bits for single large primes). All RSALS factorizations, and my own, used 29-bit LPs, so the ~70M raw relations figure holds. A 30-bit LPs task would require ~120-130M raw relations.
 2014-11-04, 12:38 #8 barthmaul   Nov 2014 3 Posts My .fb file looks like this : Code: N 10807561426505345052016343192843324674003752183584439431855278468457615148415828451132399374576833616654358191612829629246076273020826999666784140736359641 SKEW 20962266.38 A5 5400 A4 -718769358546 A3 11720645312502938107 A2 371117678219451318054521018 A1 1066282257861769640439151209947372 A0 -175221820052441334929633397566648043896 R1 132920060949705133 R0 -1148862696576247991128008723087 FAMAX 27100000 FRMAX 27100000 SALPMAX 536870912 SRLPMAX 536870912 i know it's a lame question - where can i find a manual for msieve ? I don't know (yet) how to cut 65m relations (i believe. there's a different method than manually in notepad :) and how to change a target density.
 2014-11-04, 16:20 #9 debrouxl     Sep 2009 2·3·163 Posts In fact, msieve has built-in help, accessible through msieve --help Nowadays, in the latest msieve versions, changing the number of relations and target density is done through "filter_maxrels=X" and "target_density=X" arguments following (immediately ?) -nc or -nc1.
2014-11-04, 17:02   #10
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

10101010111112 Posts

Quote:
 Originally Posted by debrouxl Code: Sat Nov 01 09:13:15 2014 using 20 quadratic characters above 536867844 suggests 29-bit LPs instead I've checked my post-processing logs for 29-bit LPs tasks and 30-bit LPs tasks to confirm: the numbers on those lines are always slighly less than 2^(number of bits for single large primes). All RSALS factorizations, and my own, used 29-bit LPs, so the ~70M raw relations figure holds. A 30-bit LPs task would require ~120-130M raw relations.
Thanks for this explanation!

2014-11-05, 12:14   #11
barthmaul

Nov 2014

310 Posts

Quote:
 Originally Posted by debrouxl In fact, msieve has built-in help, accessible through msieve --help Nowadays, in the latest msieve versions, changing the number of relations and target density is done through "filter_maxrels=X" and "target_density=X" arguments following (immediately ?) -nc or -nc1.
Thank You very much.
Is there a way to use the relations in spairs.save.gz file for msieve ? I don't have a .dat file (GGNFS deleted it after restart) but I have a 30 gb spairs file. I tried gunzip -c spairs.save.gz >> msieve.dat but now i have "error -1 reading relation 0" (and so on) in my msieve.log file.

 Similar Threads Thread Thread Starter Forum Replies Last Post EddieTheBear Hardware 19 2015-10-23 13:22 PicGrabber Msieve 20 2014-10-31 20:06 jackchina Factoring 7 2012-04-13 17:57 wsgtrsys Factoring 21 2010-07-15 08:16 Proggie Software 4 2005-01-05 07:35

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

Sun Sep 25 12:02:21 UTC 2022 up 38 days, 9:30, 0 users, load averages: 0.87, 1.02, 1.05