Register FAQ Search Today's Posts Mark Forums Read

 2022-01-04, 04:54 #1 carpetpool     "Sam" Nov 2016 22·83 Posts Msieve Quadratic Sieve error I am (somewhat) new to using Msieve (and factoring projects too), I am trying to factor this random semiprime as a performance test, and I get the following error: Code: Mon Jan 03 20:08:41 2022 Msieve v. 1.53 (SVN 1005) Mon Jan 03 20:08:41 2022 random seeds: f6785680 8e1867c8 Mon Jan 03 20:08:41 2022 factoring 2694676428019683370848062134396528778302568276990914268387963332068274744924319183673678607 (91 digits) Mon Jan 03 20:08:41 2022 searching for 15-digit factors Mon Jan 03 20:08:41 2022 commencing quadratic sieve (91-digit input) Mon Jan 03 20:08:41 2022 using multiplier of 43 Mon Jan 03 20:08:41 2022 using generic 64kb sieve core Mon Jan 03 20:08:41 2022 sieve interval: 18 blocks of size 65536 Mon Jan 03 20:08:41 2022 processing polynomials in batches of 6 Mon Jan 03 20:08:41 2022 using a sieve bound of 1685933 (63379 primes) Mon Jan 03 20:08:41 2022 using large prime bound of 155105836 (27 bits) Mon Jan 03 20:08:41 2022 using double large prime bound of 553516580371368 (42-49 bits) Mon Jan 03 20:08:41 2022 using trial factoring cutoff of 49 bits Mon Jan 03 20:08:41 2022 polynomial 'A' values have 12 factors Mon Jan 03 20:30:34 2022 63916 relations (17218 full + 46698 combined from 717970 partial), need 63475 Mon Jan 03 20:30:35 2022 begin with 96928 relations Mon Jan 03 20:30:35 2022 reduce to 26830 relations in 4 passes Mon Jan 03 20:30:35 2022 attempting to read 26830 relations Mon Jan 03 20:30:35 2022 failed to read relation 0 Mon Jan 03 20:30:35 2022 failed to read relation 1 Mon Jan 03 20:30:35 2022 failed to read relation 2 Mon Jan 03 20:30:35 2022 failed to read relation 3 Mon Jan 03 20:30:35 2022 failed to read relation 4 Mon Jan 03 20:30:35 2022 failed to read relation 5 ... Mon Jan 03 20:30:35 2022 failed to read relation 1166 Mon Jan 03 20:30:35 2022 failed to read relation 1167 Mon Jan 03 20:30:35 2022 failed to read relation 1168 Mon Jan 03 20:30:35 2022 failed to read relation 1169 Mon Jan 03 20:30:35 2022 failed to read relation 1170 Mon Jan 03 20:30:35 2022 recovered 25659 relations Mon Jan 03 20:30:35 2022 recovered 20198 polynomials Mon Jan 03 20:30:35 2022 attempting to build 1815 cycles Mon Jan 03 20:30:35 2022 found 1815 cycles in 1 passes Mon Jan 03 20:30:35 2022 distribution of cycle lengths: Mon Jan 03 20:30:35 2022 length 1 : 1663 Mon Jan 03 20:30:35 2022 length 2 : 136 Mon Jan 03 20:30:35 2022 length 3 : 14 Mon Jan 03 20:30:35 2022 length 4 : 2 Mon Jan 03 20:30:35 2022 largest cycle: 4 relations Mon Jan 03 20:30:35 2022 matrix is 63379 x 1815 (0.2 MB) with weight 49959 (27.53/col) Mon Jan 03 20:30:35 2022 sparse part has weight 49959 (27.53/col) Mon Jan 03 20:30:35 2022 matrix is corrupt; skipping linear algebra Mon Jan 03 20:30:35 2022 elapsed time 00:21:54 Everything up to the 63k relations worked seemingly fine, although it appears it failed somewhere in the data collection phase. I didn't even get the factors. No files except the log file are in the directory, so there is no save or error file or anything like that I could read off of. When I re-ran the factoring process again, it started from scratch. Any suggestions on how to handle this or what software I should use more generally? I am willing to spend about a day on work (at least for now), so I figured 120-130 digits is reasonable. Thanks for any help, appreciated a lot !
 2022-01-04, 06:26 #2 VBCurtis     "Curtis" Feb 2005 Riverside, CA 10100100111102 Posts YAFU's quadratic sieve is quite a bit faster than msieve's. Edit: if you're in linux, and going to be doing mostly GNFS jobs, CADO is far superior to msieve/ggnfs. But if your jobs will be under ~94 digits, then YAFU-quadratic sieve is still the winner. Did you do a previous job in this same folder? Both the error and the mismatch between the relations counts on these two lines: 63916 relations (17218 full + 46698 combined from 717970 partial), need 63475 Mon Jan 03 20:30:35 2022 begin with 96928 relations suggest that some old data was in msieve.dat when you started this job, and that old data corrupted the new job. If you erase all the temporary files after each job, I think you'll find this current composite will factor just fine. Last fiddled with by VBCurtis on 2022-01-04 at 06:28
2022-01-04, 08:58   #3
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

598410 Posts

Quote:
 Originally Posted by VBCurtis If you erase all the temporary files after each job, I think you'll find this current composite will factor just fine.

Msieve should do that itself pretty reliably.

2022-01-05, 06:45   #4
carpetpool

"Sam"
Nov 2016

22·83 Posts

Quote:
 Originally Posted by VBCurtis YAFU's quadratic sieve is quite a bit faster than msieve's. Edit: if you're in linux, and going to be doing mostly GNFS jobs, CADO is far superior to msieve/ggnfs. But if your jobs will be under ~94 digits, then YAFU-quadratic sieve is still the winner. Did you do a previous job in this same folder? Both the error and the mismatch between the relations counts on these two lines: 63916 relations (17218 full + 46698 combined from 717970 partial), need 63475 Mon Jan 03 20:30:35 2022 begin with 96928 relations suggest that some old data was in msieve.dat when you started this job, and that old data corrupted the new job. If you erase all the temporary files after each job, I think you'll find this current composite will factor just fine.
Thanks, your suggestion seemed to work. Also, is the same true for NFS (YAFU better than Msieve), presumably for 130+ digits?

2022-01-05, 14:29   #5
bsquared

"Ben"
Feb 2007

3,617 Posts

Quote:
 Originally Posted by carpetpool Thanks, your suggestion seemed to work. Also, is the same true for NFS (YAFU better than Msieve), presumably for 130+ digits?
If you use *only* msieve, then by far yes, because msieve does not have a lattice siever. Which is why everyone uses either CADO, or some combination of msieve and ggnfs. msieve does the polynomial generation and post processing (filtering, linear algebra) and ggnfs does the sieving. YAFU is a C program that automates this process, or there are some script options for the same (e.g., factmsieve.py).

 Similar Threads Thread Thread Starter Forum Replies Last Post Ilya Gazman Factoring 3 2020-08-22 17:14 Ilya Gazman Factoring 3 2016-02-22 11:32 Sam Kennedy Factoring 20 2013-01-09 16:50 paul0 Factoring 3 2011-09-22 17:12 ThiloHarich Factoring 5 2006-07-14 09:51

All times are UTC. The time now is 08:44.

Thu May 19 08:44:49 UTC 2022 up 35 days, 6:46, 0 users, load averages: 1.69, 1.53, 1.52