20150305, 00:03  #1 
Mar 2015
110_{2} Posts 
SIQS  problem with solving linear algebra
Hi,
I decided to implement SIQS as a practical part of my Master's thesis. Everything seems to work nice except matrix solving. For that part I implemented Fast Algorithm for Gaussian Elimination described by Koc and Arachichige: https://www.cs.umd.edu/~gasarch/TOPI.../fastgauss.pdf When I try to factor 20 or 30 digit number, it's without any problem, but when I try to factor 40 digit number I get the right result very very rarely, otherwise I get as a result 1. So I have exact the same problem as was already solved here: http://mersenneforum.org/showthread.php?t=19110 But when I finish the sieving step, I do get rid of null vectors, duplicates and singletons. Then I build matrix just by copying relations from an array of relations so that I make matrix with rows = FB length + 1. If the trivial factor is found I delete the first relation from the matrix and add new one. I'm doing this as long as I have extra relations. If I'm really lucky I find non trivial factor. I really think that this is not the right way how to do it and I bet that I'm doing something wrong when I'm building the matrix, but I just don't know, what it is. Could someone tell me, what I'm doing wrong, please? Any hint will be appreciated. PS.: I apologize, my english is quite limited. 
20150305, 02:32  #2 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
7221_{10} Posts 
I think generally what the "good" programs around here do is put most or all of the relations into a matrix (disregarding FB+1), and solve it; you should get a good 30+ dependencies, each with a good chance of producing factors.
I can't be more specific though. Try looking through the source for Msieve (which is basically the "good" program I meant above): http://sourceforge.net/p/msieve/code/HEAD/tree/trunk/ The three folders of interest are "common", "gnfs", and "mpqs". I'm not sure how much the filtering differs between the three folders, but poking around may be useful. 
20150305, 09:05  #3  
Mar 2015
2·3 Posts 
Quote:
I used msieve to check if my implementation of SIQS is generating right polynoms and if it's sieving right. Everything OK. But I'm totally lost at msieve's linear algebra step. I think the Lanczos method is too complicated to me for understanding it, but I will try to look at the building matrix there more deeply. 

20150305, 16:15  #4 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
16065_{8} Posts 
Lanczos is merely a method of finding dependencies in an ultra sparse matrix (such as those required for sieving methods). If you are confident in your Gaussian implementation, then in can indeed be simply ignored. The parts before it (filtering and merging) and the parts after (the sqrt) are more likely to be of interest.

20150305, 17:54  #5 
Mar 2003
7×11 Posts 
I'd suggest writing some code to verify the congruence for each relation before you start the linear algebra. One bad relation can cause the all of the dependencies to be invalid. If some of the relations are invalid and your code works up to 30 digits but it fails around 40 digits then it's likely that you have an integer somewhere in your sieve code that is overflowing. If all of the relations are good then I'd say it's likely you have the same problem but it's in the dependency calculation stage.

20150305, 18:10  #6  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2^{2}×2,741 Posts 
Quote:


20150305, 20:22  #7  
Mar 2015
2×3 Posts 
Quote:
I couldn't find that mistake when I was factoring 20 digit number, because I used large FB, so one sieving polynom was enough. I also couldn't find it when I was factoring 30 digit number, because more polynoms were used, but coeficient a wasn't changed. I thank everyone that post a comment here and tried to help me. I'm glad that I overcame my fear of using english, it was totally worth it!! :D 

20150305, 22:35  #8 
Mar 2003
7·11 Posts 
Glad you found the problem! SIQS is complicated enough that when something goes wrong it is sometimes difficult to know where to start. I made my own implementation about ten years ago and found that verifying data at each stage helped a lot. At its best I was able to factor a C114 in 14 days using about 20 cores.

20150306, 02:35  #9 
"Curtis"
Feb 2005
Riverside, CA
5·17·59 Posts 
Dome
Your english is better than many on this forum, even somewhat regular posters. You write quite well, and the important parts about code or math are very clear. We're glad you used the forum, and I enjoy threads like this as it keeps reminding me that learning an algorithm like SIQS is within my intellectual reach if I find a cure for (personal) laziness. 
20150306, 06:23  #10  
Romulan Interpreter
"name field"
Jun 2011
Thailand
3^{4}·11^{2} Posts 
Quote:
@dome: 

20150306, 16:54  #11  
Mar 2015
2·3 Posts 
Quote:
Well, you factored pretty big number with your SIQS. I'll take it as a challenge! I'll try to get as closer as possilble, but still a lot of work to do. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
restarting nfs linear algebra  cubaq  YAFU  2  20170402 11:35 
New Method for Solving Linear Systems  Dubslow  Miscellaneous Math  24  20120824 10:46 
Solving linear systems faster than ever...  WraithX  Math  2  20101023 21:27 
Linear algebra at 600%  CRGreathouse  Msieve  8  20090805 07:25 
Solving linear systems modulo n  drido  Math  3  20080208 15:06 