 mersenneforum.org QS - lin. algebra phase
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read  2007-07-19, 13:31 #1 SilverMan   Jul 2007 2·32 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    2007-07-19, 14:09   #2
Chris Card

Aug 2004

7·19 Posts Quote:
 Originally Posted by SilverMan 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   2007-07-19, 14:11   #3
jasonp
Tribal Bullet

Oct 2004

3,547 Posts Quote:
 Originally Posted by SilverMan 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.   2007-07-19, 14:19   #4
Chris Card

Aug 2004

7×19 Posts Quote:
 Originally Posted by jasonp 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   2007-07-19, 14:32   #5
SilverMan

Jul 2007

2·32 Posts Quote:
 Originally Posted by jasonp 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   2007-07-19, 14:58 #6 Chris Card   Aug 2004 8516 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   2007-07-19, 15:06   #7
SilverMan

Jul 2007

2×32 Posts Quote:
 Originally Posted by Chris Card 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    2007-07-19, 15:57   #8
jasonp
Tribal Bullet

Oct 2004

3,547 Posts Quote:
 Originally Posted by SilverMan 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.   2007-07-19, 16:21   #9
SilverMan

Jul 2007

2·32 Posts Quote:
 Originally Posted by jasonp 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 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 ... 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   2007-07-19, 17:52   #10
jasonp
Tribal Bullet

Oct 2004

3,547 Posts Quote:
 Originally Posted by SilverMan 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.   2007-07-20, 08:14 #11 SilverMan   Jul 2007 2·32 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 Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post R.D. Silverman Other Mathematical Topics 15 2014-10-29 19:42 kracker Hardware 5 2014-01-20 02:33 em99010pepe Hardware 0 2011-11-11 15:18 Joshua2 Homework Help 11 2010-01-29 21:37 SlashDude 15k Search 1 2003-12-16 23:09

All times are UTC. The time now is 09:20.

Mon Sep 26 09:20:28 UTC 2022 up 39 days, 6:49, 0 users, load averages: 1.58, 1.49, 1.44

Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔