20140201, 21:16  #1 
Dec 2013
2^{2} Posts 
QS question regarding finding just trivial solution
Maybe this question of mine is trivial too.. my apologies if so. I just ended up in writing a linux C QS factoring program by my own and tried it against many semiprimes 64, 96, 128 bits long (20, 30, 39 digits).
Everything works fine against 20 digits: 100% factors finding in few seconds with FB 50100 primes, the trials against 30 digits are FB sensitive: 50% success or less if FB is 700 pimes, 100% success using 450600 primes. Unfortunately I could not get any success on semiprimes 128 bits long even having tested different FB spanning from 1300 up to 2000 primes: all the trials come up with matix solved but just trivial factor = 1 found for each of the many solutions found in each attempt made. The matrix in all the trials described above had a number of rows = FB lenght + 1. Is this beaviour coherent with the quadratic sieve model or have I to suppose there is a flaw in my implemantation? Any hint or suggestion is welcome. 
20140201, 22:20  #2 
Aug 2002
Buenos Aires, Argentina
56F_{16} Posts 
Have you eliminated singletons before perfoming the linear algebra? This is an important step.
Last fiddled with by alpertron on 20140201 at 22:20 
20140202, 00:46  #3 
Dec 2013
2^{2} Posts 
QS question regarding finding just trivial solutions

20140202, 01:54  #4 
Nov 2003
2^{2}·5·373 Posts 

20140202, 02:13  #5 
Aug 2002
Buenos Aires, Argentina
10101101111_{2} Posts 
Well, when I implemented SIQS in my applet, it did not accumulate repeated congruences as you said above. In this case I had a problem that for large factorizations, the linear algebra did not find a proper factor, as happened to the OP.
I solved the problem by discarding singletons. 
20140202, 07:06  #6  
Dec 2013
4_{8} Posts 
Quote:


20140202, 13:57  #7 
Tribal Bullet
Oct 2004
DD7_{16} Posts 
Unfortunately the linear algebra failing usually doesn't give a clue as to why the failure happens. If you are only looking for one vector in the nullspace and mess up the handling of even one factor base entry, you will have no nullspace 50% of the time. If there is even one duplicate you will have no nullspace. If two relations are different but lead to identical matrix entries, this is the same as if you had a duplicate (of course you can proceed directly to the square root if that happened). If you are combining relations with large primes in common, and that empties out one row or one column of the matrix at random, you often will have no nullspace. Even if you are not combining relations, having a factor base entry that does not appear in the matrix will cause problems.
Last fiddled with by jasonp on 20140202 at 14:01 
20140202, 19:52  #8  
Sep 2008
Kansas
2^{2}×5×173 Posts 
Quote:


20140202, 21:04  #9  
Dec 2013
2^{2} Posts 
QS question regarding finding just trivial solutions / solved
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Suddenly I'm getting only trivial TF tests  fivemack  Software  34  20151025 16:54 
Trivial question  davieddy  Information & Answers  6  20111208 08:07 
Trivial bug: repeated PM notifications  Christenson  Forum Feedback  0  20110321 03:49 
newbie question  finding small factors of very large numbers  NeoGen  Math  7  20070313 00:04 
SNFS trivial factorization  fetofs  Factoring  39  20060726 12:32 