mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2022-01-04, 04:54   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

5·67 Posts
Post 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 !
carpetpool is offline   Reply With Quote
Old 2022-01-04, 06:26   #2
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

22×17×79 Posts
Default

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
VBCurtis is offline   Reply With Quote
Old 2022-01-04, 08:58   #3
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

10111011010002 Posts
Default

Quote:
Originally Posted by VBCurtis View Post

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.
henryzz is offline   Reply With Quote
Old 2022-01-05, 06:45   #4
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

5×67 Posts
Post

Quote:
Originally Posted by VBCurtis View Post
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?
carpetpool is offline   Reply With Quote
Old 2022-01-05, 14:29   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

5·727 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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).
bsquared is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Quadratic Sieve optimizations Ilya Gazman Factoring 3 2020-08-22 17:14
Java Quadratic Sieve Ilya Gazman Factoring 3 2016-02-22 11:32
Quadratic Sieve by Hand Sam Kennedy Factoring 20 2013-01-09 16:50
Finding B in Quadratic Sieve paul0 Factoring 3 2011-09-22 17:12
Quadratic Sieve in wikipedia.de ThiloHarich Factoring 5 2006-07-14 09:51

All times are UTC. The time now is 17:34.


Thu Aug 11 17:34:32 UTC 2022 up 35 days, 12:21, 3 users, load averages: 0.95, 1.13, 1.20

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔