mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2015-03-05, 00:03   #1
Dome
 
Mar 2015

2·3 Posts
Default 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.
Dome is offline   Reply With Quote
Old 2015-03-05, 02:32   #2
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

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.
Dubslow is offline   Reply With Quote
Old 2015-03-05, 09:05   #3
Dome
 
Mar 2015

2×3 Posts
Default

Quote:
Originally Posted by Dubslow View Post
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.
Dome is offline   Reply With Quote
Old 2015-03-05, 16:15   #4
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

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.
Dubslow is offline   Reply With Quote
Old 2015-03-05, 17:54   #5
dleclair
 
dleclair's Avatar
 
Mar 2003

3·52 Posts
Default

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.
dleclair is offline   Reply With Quote
Old 2015-03-05, 18:10   #6
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

23·13·97 Posts
Default

Quote:
Originally Posted by Dome View Post
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.
xilman is offline   Reply With Quote
Old 2015-03-05, 20:22   #7
Dome
 
Mar 2015

68 Posts
Default

Quote:
Originally Posted by dleclair View Post
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
Dome is offline   Reply With Quote
Old 2015-03-05, 22:35   #8
dleclair
 
dleclair's Avatar
 
Mar 2003

3×52 Posts
Default

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.
dleclair is offline   Reply With Quote
Old 2015-03-06, 02:35   #9
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

421910 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2015-03-06, 06:23   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2×5×859 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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:
LaurV is offline   Reply With Quote
Old 2015-03-06, 16:54   #11
Dome
 
Mar 2015

2×3 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
restarting nfs linear algebra cubaq YAFU 2 2017-04-02 11:35
New Method for Solving Linear Systems Dubslow Miscellaneous Math 24 2012-08-24 10:46
Solving linear systems faster than ever... WraithX Math 2 2010-10-23 21:27
Linear algebra at 600% CRGreathouse Msieve 8 2009-08-05 07:25
Solving linear systems modulo n drido Math 3 2008-02-08 15:06

All times are UTC. The time now is 05:32.

Wed Jul 15 05:32:05 UTC 2020 up 112 days, 3:05, 0 users, load averages: 1.36, 1.45, 1.45

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