SIQS - problem with solving linear algebra

[Dome]

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.

[Dubslow]

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.

[Dome]

Originally Posted by Dubslow

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.

Thank you for the hint. I tried to build matrix with all relations I gathered (duplicants, singletons already deleted), I got like 90 dependencies but all of them leads to result = 1.

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.

[Dubslow]

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.

[dleclair]

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.

[xilman]

Originally Posted by Dome

Thank you for the hint. I tried to build matrix with all relations I gathered (duplicants, singletons already deleted), I got like 90 dependencies but all of them leads to result = 1.

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.

20-odd years ago we used sztructured Gaussian elimination. I could try and dig up some code from that era if you think it might help.

[Dome]

Originally Posted by dleclair

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.

Thanks to you I found the problem. I was sieving only through a * x^2 + 2 * b + c, because if this is smooth then a * (a * x^2 + 2 * b + c) = (a * x + b)^2 - N is automatically smooth too. BUT I forgot to add the divisors of coeficient a to the relations. What a stupid mistake...

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

[dleclair]

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.

[VBCurtis]

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.

[LaurV]

Originally Posted by VBCurtis

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.

+1

@dome:

[Dome]

Originally Posted by dleclair

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.

So true, sometimes it's making me crazy or totally hopeless, strong will is really required. :-D

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.