mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-07-19, 13:31   #1
SilverMan
 
Jul 2007

2×32 Posts
Question 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
SilverMan is offline   Reply With Quote
Old 2007-07-19, 14:09   #2
Chris Card
 
Chris Card's Avatar
 
Aug 2004

100000102 Posts
Default

Quote:
Originally Posted by SilverMan View Post
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.
If a row is all zeros it means that the corresponding primes are already found at even powers in your relations, so yes, you can ignore them for the linear algebra.
Quote:
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?
I think this is where you've got confused (and it can be confusing, so you have my sympathy). You are trying to find linear combinations of the columns that are zero (mod 2), so the zero rows are irrelevant. As long as you have more columns than rows there will be solutions, and to find them use Gaussian elimination (for example). Look up algorithms for finding the kernel of a matrix over a field, e.g. in Knuth or Cohen.

Hope that helps

Chris
Chris Card is offline   Reply With Quote
Old 2007-07-19, 14:11   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,163 Posts
Default

Quote:
Originally Posted by SilverMan View Post
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.
This is where you have trouble. Having the last two rows all zero does not mean you can ignore them, it means that it doesn't matter whether the last two variables are 0 or 1. Choose 0 or 1 randomly as the last two bits in the solution, then perform back substitution like normal. Looking for nullspace vectors means you want a nonzero vector such that multiplying by the above gives the zero vector, and rows full of zeros in the reduced matrix give you the flexibility to find a nonzero solution. If you ignore the last two rows, then you're picking zero for the last two variables, and with that choice the only nullspace vector is all-zeros, like you've found.

Hope this helps.
jasonp is offline   Reply With Quote
Old 2007-07-19, 14:19   #4
Chris Card
 
Chris Card's Avatar
 
Aug 2004

13010 Posts
Default

Quote:
Originally Posted by jasonp View Post
This is where you have trouble. Having the last two rows all zero does not mean you can ignore them, it means that it doesn't matter whether the last two variables are 0 or 1. Choose 0 or 1 randomly as the last two bits in the solution, then perform back substitution like normal. Looking for nullspace vectors means you want a nonzero vector such that multiplying by the above gives the zero vector, and rows full of zeros in the reduced matrix give you the flexibility to find a nonzero solution. If you ignore the last two rows, then you're picking zero for the last two variables, and with that choice the only nullspace vector is all-zeros, like you've found.

Hope this helps.
Did I get my rows and columns mixed up? Oops! Or maybe not. Reading again, the rows are primes, and so we combine columns.
(I told you it was confusing..)

Chris

Last fiddled with by Chris Card on 2007-07-19 at 14:21
Chris Card is offline   Reply With Quote
Old 2007-07-19, 14:32   #5
SilverMan
 
Jul 2007

228 Posts
Default

Quote:
Originally Posted by jasonp View Post
This is where you have trouble. Having the last two rows all zero does not mean you can ignore them, it means that it doesn't matter whether the last two variables are 0 or 1. Choose 0 or 1 randomly as the last two bits in the solution, then perform back substitution like normal. Looking for nullspace vectors means you want a nonzero vector such that multiplying by the above gives the zero vector, and rows full of zeros in the reduced matrix give you the flexibility to find a nonzero solution. If you ignore the last two rows, then you're picking zero for the last two variables, and with that choice the only nullspace vector is all-zeros, like you've found.

Hope this helps.
Yes, this is what i do - having two zero rows i choose the last two variables for example 1 and 0. By "discarding" i mean "freely choosing its value" - sorry for the confusion. Then i compute the rest and get the complete "solution vector" as i call it. But often it gives me only trivial factors. Sometimes i go through hundreds or thousands of solutions in this phase because i have like 20 zero rows, which takes a lot of time. I wonder how other programs do this, because always the lin. algebra phase is a matter of miliseconds - for me it takes sometimes very long (even tens of seconds) for small numbers and matrices.

Last fiddled with by SilverMan on 2007-07-19 at 14:33
SilverMan is offline   Reply With Quote
Old 2007-07-19, 14:58   #6
Chris Card
 
Chris Card's Avatar
 
Aug 2004

2×5×13 Posts
Default

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
Chris Card is offline   Reply With Quote
Old 2007-07-19, 15:06   #7
SilverMan
 
Jul 2007

1216 Posts
Default

Quote:
Originally Posted by Chris Card View Post
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
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
SilverMan is offline   Reply With Quote
Old 2007-07-19, 15:57   #8
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101101000012 Posts
Default

Quote:
Originally Posted by SilverMan View Post
Yes, this is what i do - having two zero rows i choose the last two variables for example 1 and 0. By "discarding" i mean "freely choosing its value" - sorry for the confusion. Then i compute the rest and get the complete "solution vector" as i call it. But often it gives me only trivial factors. Sometimes i go through hundreds or thousands of solutions in this phase because i have like 20 zero rows, which takes a lot of time. I wonder how other programs do this, because always the lin. algebra phase is a matter of miliseconds - for me it takes sometimes very long (even tens of seconds) for small numbers and matrices.
Do you mean you get nonzero dependencies out of the matrix but the QS square root does not find factors most of the time? That makes me suspicious of the square root and not the linear algebra, or at least of the method you use for constructing the matrix columns.

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 all-zero matrix rows, then it could mean that you have duplicate matrix rows, or matrix rows that start off all-zero, 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.
jasonp is offline   Reply With Quote
Old 2007-07-19, 16:21   #9
SilverMan
 
Jul 2007

2×32 Posts
Default

Quote:
Originally Posted by jasonp View Post
Do you mean you get nonzero dependencies out of the matrix but the QS square root does not find factors most of the time?
Example: i get 15 non-zero solutions, i check 10 and get only trivial factors. The eleventh gets me a nontrivial one - seems okay. But what if i get say 30 zero lines, so there are 2^30 - 1 combinations of zeros and ones which i can choose for my variables (and compute the rest of them)? Often i check a huge amount of solutions only to get trivial factors...

Quote:
Originally Posted by jasonp View Post
That makes me suspicious of the square root and not the linear algebra, or at least of the method you use for constructing the matrix columns.
I dont understand this what about the square root and columns? The columns are the exponent vectors of found smooth numbers mod 2.

Quote:
Originally Posted by jasonp View Post
... The bottom line is that a small amount of preprocessing for the matrix is always necessary.
As you said, a preprocessing is perhaps necessary - i havent thought about this. So my question now is - what preprocessing should i do to minimize the number of solutions which i will have to check to obtain a nontrivial factor?

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 2007-07-19 at 16:23
SilverMan is offline   Reply With Quote
Old 2007-07-19, 17:52   #10
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,163 Posts
Default

Quote:
Originally Posted by SilverMan View Post

I dont understand this what about the square root and columns? The columns are the exponent vectors of found smooth numbers mod 2.

[...]

As you said, a preprocessing is perhaps necessary - i havent thought about this. So my question now is - what preprocessing should i do to minimize the number of solutions which i will have to check to obtain a nontrivial factor?
The point of solving the matrix is to get the powers of primes appearing in a dependency to all be even, and actually checking that they are all even is a good test that everything is working properly. If the powers of primes are all even but the square root isn't working, then you have a square root problem. If they're not all even, either the linear algebra or the matrix construction has a bug.

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.
jasonp is offline   Reply With Quote
Old 2007-07-20, 08:14   #11
SilverMan
 
Jul 2007

2×32 Posts
Default

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
SilverMan is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Polynomial Algebra R.D. Silverman Other Mathematical Topics 15 2014-10-29 19:42
8 phase 12 phase, blah blah kracker Hardware 5 2014-01-20 02:33
Core i5 2500K vs Core i7 2600K (Linear algebra phase) em99010pepe Hardware 0 2011-11-11 15:18
can anyone here do algebra :) Joshua2 Homework Help 11 2010-01-29 21:37
Beta user stats for Phase 2 - Test of 210885 SlashDude 15k Search 1 2003-12-16 23:09

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

Mon Oct 26 11:05:46 UTC 2020 up 46 days, 8:16, 0 users, load averages: 1.85, 2.06, 1.99

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.