20070719, 13:31  #1 
Jul 2007
2×3^{2} Posts 
QS  lin. algebra phase
Hello all,
a few weeks ago i started working on my implementation of the Quadratic Sieve algorithm. After numerous hours of studying (god bless wikipedia ) i finaly understand the basics of how this works. But of course as always, theory is fine but practical implementation is much harder. I solved some obstacles myself and now the sieving part works quite good. The problem comes when it gets to solving that damn matrix. Everywhere i looked no one seemed to be much concerned about this, because "it takes a small amount of time compared to the sieving part". Now here comes my problem  for me, its too long! When trying bigger numbers (okay, they are small (30 digits), but for me they are big  just starting with all this), of course i use Gaussian elimination, but this is not the problem. Eliminating the matrix takes only miliseconds  the problem is that i get thousands of solutions and most of them give me only trivial factors. I realized that i must do something wrong  i think the error i do is in the way i get the solutions from the matrix. Because there is no one around me who could help, i decided to find a forum and hopefully here i will get the answer. So here is what i do (an example in a tiny matrix) 1 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 The matrix above is a result of my elimination (correct result, verified). Here i have 5 vectors found with sieving (columns) using 4 primes (rows). Its clear that combining the first, second and fourth column gives me the zero vector. The thing is, that there are two zero rows. According to my (poor) knowledge of linear algebra, this means i can discard them. So i have two rows and 5 columns > that should mean i can choose whathever values for 3 uknown variables. We work mod 2, so that is 2^3 possible solutions, right? That is 8 solutions to try  not a big problem. But when is comes to larger matrices, having like 20 or more zero rows gives me 2^20 solutions... and a hell long time to try all of them. I really feel that there is something terribly wrong. But what? I do not know. Could someone tell me how to do the linear algebra part and what can i do to make it faster? I know  use another algorithm to eliminate it, gauss is slow for big matrices. But as i said, eliminating is fast for me (small numbers and small matrix now). The problem is elsewhere... Thanks in advance for any advice, eh, and be warned, i'm new to this and i learned everything myself  so a detailed description of how to solve my problem might be needed 
20070719, 14:09  #2  
Aug 2004
10000010_{2} Posts 
Quote:
Quote:
Hope that helps Chris 

20070719, 14:11  #3  
Tribal Bullet
Oct 2004
3·1,163 Posts 
Quote:
Hope this helps. 

20070719, 14:19  #4  
Aug 2004
130_{10} Posts 
Quote:
(I told you it was confusing..) Chris Last fiddled with by Chris Card on 20070719 at 14:21 

20070719, 14:32  #5  
Jul 2007
22_{8} Posts 
Quote:
Last fiddled with by SilverMan on 20070719 at 14:33 

20070719, 14:58  #6 
Aug 2004
2×5×13 Posts 
I make the kernel of your matrix to be
(0 1 1 0 1 0 1 0 0 0 1 0 0 0 1) i.e. 3 solutions. This is assuming that each row represents a prime Chris 
20070719, 15:06  #7 
Jul 2007
12_{16} Posts 
Will look at that kernel thing  for this small matrix we have same results (2 zero rows, 2 ^ 2 solutions, ignoring the zero solution  3 solutions). Perhaps it will help with bigger matrices. Thanks

20070719, 15:57  #8  
Tribal Bullet
Oct 2004
110110100001_{2} Posts 
Quote:
If you mean that you still get the zero vector out of the matrix even though you assign random values to the solution elements corresponding to the allzero matrix rows, then it could mean that you have duplicate matrix rows, or matrix rows that start off allzero, or matrix rows that only have one entry. Rows that look like any of these cannot contribute to the solution, but do not properly belong in the nullspace. If the number of such bad rows is larger than the number of excess columns in your matrix, then the nullspace would contain only the zero vector. The bottom line is that a small amount of preprocessing for the matrix is always necessary. 

20070719, 16:21  #9  
Jul 2007
2×3^{2} Posts 
Quote:
Quote:
Quote:
Many thanks for your help guys, it seems we are getting somewhere and hopefully i will learn something and make my code better and correct Last fiddled with by SilverMan on 20070719 at 16:23 

20070719, 17:52  #10  
Tribal Bullet
Oct 2004
3·1,163 Posts 
Quote:
At a minimum, before solving the matrix you should delete all rows that are empty and all rows that have a single 1 in them. This changes the aspect ratio of the matrix, so you can also delete columns too, and may as well delete the ones with the most nonzero entries. That in turn can create more empty and singleton rows, so the process should be iterated. You want a matrix where every row contributes a little to the solution. Compressing the matrix in this way is especially important for bigger problems when Gauss elimination is replaced by block Lanczos. 

20070720, 08:14  #11 
Jul 2007
2×3^{2} Posts 
So i will be able to reduce the size of the matrix, that is great.
Im only a little bit confused with the "removing of columns". In my example i had two zero lines, so you mean i should also remove these and also two columns? And which ones? As you suggested i will check the exponents of my solutions if they are all even. Im quite sure they are, but perhaps im mistaken. The idea of removing lines with only one zero surprised me at first, but then i realized its absolutely logical 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Polynomial Algebra  R.D. Silverman  Other Mathematical Topics  15  20141029 19:42 
8 phase 12 phase, blah blah  kracker  Hardware  5  20140120 02:33 
Core i5 2500K vs Core i7 2600K (Linear algebra phase)  em99010pepe  Hardware  0  20111111 15:18 
can anyone here do algebra :)  Joshua2  Homework Help  11  20100129 21:37 
Beta user stats for Phase 2  Test of 210885  SlashDude  15k Search  1  20031216 23:09 