mersenneforum.org SIQS - problem with solving linear algebra
 Register FAQ Search Today's Posts Mark Forums Read

 2015-03-05, 00:03 #1 Dome   Mar 2015 1102 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.
 2015-03-05, 02:32 #2 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
2015-03-05, 09:05   #3
Dome

Mar 2015

1102 Posts

Quote:
 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.

 2015-03-05, 16:15 #4 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
 2015-03-05, 17:54 #5 dleclair     Mar 2003 22×19 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.
2015-03-05, 18:10   #6
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

101001000001112 Posts

Quote:
 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.

2015-03-05, 20:22   #7
Dome

Mar 2015

2·3 Posts

Quote:
 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

 2015-03-05, 22:35 #8 dleclair     Mar 2003 22×19 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.
 2015-03-06, 02:35 #9 VBCurtis     "Curtis" Feb 2005 Riverside, CA 110038 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.
2015-03-06, 06:23   #10
LaurV
Romulan Interpreter

Jun 2011
Thailand

23BC16 Posts

Quote:
 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:

2015-03-06, 16:54   #11
Dome

Mar 2015

616 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post cubaq YAFU 2 2017-04-02 11:35 Dubslow Miscellaneous Math 24 2012-08-24 10:46 WraithX Math 2 2010-10-23 21:27 CRGreathouse Msieve 8 2009-08-05 07:25 drido Math 3 2008-02-08 15:06

All times are UTC. The time now is 14:35.

Wed Jan 20 14:35:12 UTC 2021 up 48 days, 10:46, 1 user, load averages: 3.28, 3.85, 4.02