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:

[URL]https://www.cs.umd.edu/~gasarch/TOPICS/factoring/fastgauss.pdf[/URL]

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:

[URL]http://mersenneforum.org/showthread.php?t=19110[/URL]

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.

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): [url]http://sourceforge.net/p/msieve/code/HEAD/tree/trunk/[/url]
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.

[QUOTE=Dubslow;397041]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): [URL]http://sourceforge.net/p/msieve/code/HEAD/tree/trunk/[/URL]
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.[/QUOTE]

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.

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.

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.

[QUOTE=Dome;397056]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.[/QUOTE]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.

[QUOTE=dleclair;397088]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.[/QUOTE]

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.

[FONT=Consolas][SIZE=2][COLOR=#57a64a][FONT=Consolas][SIZE=2][COLOR=#57a64a][FONT=Consolas][SIZE=2][COLOR=#57a64a][FONT=Arial][COLOR=#000000]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[/COLOR][/FONT]
[/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT][/COLOR][/SIZE][/FONT]

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.

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.

[QUOTE=VBCurtis;397135]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.[/QUOTE]
+1

@dome: :tu:

[QUOTE=dleclair;397121]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.[/QUOTE]

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.

[QUOTE=VBCurtis;397135]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.[/QUOTE]

Thank you, your compliment means a lot to me! Yeah, laziness is my big enemy too. I'm glad that there is community that is interested in factorization, because sometimes it's really hard to find the correct answers at the articles or books.

[QUOTE=Dome;397167]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.[/QUOTE]

Sincere good luck to you on that challenge! You will need to move past Gaussian solvers and understand block Lanczos or Wiedemann if you're going to shoot for C100+. Or at least understand it enough to adopt Jason's awesome implementation in msieve, like I and others have done :smile:.

[QUOTE=bsquared;397173]Sincere good luck to you on that challenge! You will need to move past Gaussian solvers and understand block Lanczos or Wiedemann if you're going to shoot for C100+. Or at least understand it enough to adopt Jason's awesome implementation in msieve, like I and others have done :smile:.[/QUOTE]RSA-129 was done with MPQS and structured Gauss back in 1994 because the other algorithms weren't available then.

That said, BL or BW is indeed the way to go these days for C100+ numbers.

[QUOTE=bsquared;397173]Sincere good luck to you on that challenge! You will need to move past Gaussian solvers and understand block Lanczos or Wiedemann if you're going to shoot for C100+. Or at least understand it enough to adopt Jason's awesome implementation in msieve, like I and others have done :smile:.[/QUOTE]

That's true, if I want to factorize numbers like 100+ digits big, Gaussian elimination has to be changed. I implemented Guassian only because it's easy to implement and it's easy to understand it. SIQS is my project for the master's thesis and I need to implement it quickly, because I have only one semester to make it working, do measurements and describe my implementation, so I'm in rush (At my university we work on our thesis only two semesters, first semester we are learning the theory, and in the second one we are implementing the practical part). But after school I would like to make my SIQS better.