mersenneforum.org QS question regarding finding just trivial solution
 Register FAQ Search Today's Posts Mark Forums Read

 2014-02-01, 21:16 #1 vinloren   Dec 2013 22 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 semi-primes 64, 96, 128 bits long (20, 30, 39 digits). Everything works fine against 20 digits: 100% factors finding in few seconds with FB 50-100 primes, the trials against 30 digits are FB sensitive: 50% success or less if FB is 700 pimes, 100% success using 450-600 primes. Unfortunately I could not get any success on semi-primes 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.
 2014-02-01, 22:20 #2 alpertron     Aug 2002 Buenos Aires, Argentina 56F16 Posts Have you eliminated singletons before perfoming the linear algebra? This is an important step. Last fiddled with by alpertron on 2014-02-01 at 22:20
2014-02-02, 00:46   #3
vinloren

Dec 2013

22 Posts
QS question regarding finding just trivial solutions

Quote:
 Originally Posted by alpertron Have you eliminated singletons before perfoming the linear algebra? This is an important step.
Not really, I did'nt even check whether singletons are there or not, anyway I check that each supposed solution be a perfect square and this check is actually ok.

2014-02-02, 01:54   #4
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by alpertron Have you eliminated singletons before perfoming the linear algebra? This is an important step.
But irrelevant to the current question.

More relevant would be the presence of duplicates.

 2014-02-02, 02:13 #5 alpertron     Aug 2002 Buenos Aires, Argentina 101011011112 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.
2014-02-02, 07:06   #6
vinloren

Dec 2013

48 Posts

Quote:
 Originally Posted by alpertron 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.
Well, I think I have something to work on trying to solve my problem, I'll follow both paths (singletons and duplicates). Thanks for the suggestions got from who considered my post.

 2014-02-02, 13:57 #7 jasonp Tribal Bullet     Oct 2004 DD716 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 2014-02-02 at 14:01
2014-02-02, 19:52   #8
RichD

Sep 2008
Kansas

22×5×173 Posts

Quote:
 Originally Posted by vinloren I just ended up in writing a linux C QS factoring program by my own ...
Someone else had a similar idea a while back. Perhaps you can get some ideas from this thread.

2014-02-02, 21:04   #9
vinloren

Dec 2013

22 Posts
QS question regarding finding just trivial solutions / solved

Quote:
 Originally Posted by jasonp 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.
I checked what was going on regarding the building of the matrix and found no duplicate at all but a lot of singletons. I just got rid of the singletons and eventually the correct factorization come up "magically". Thanks to all those who had given hints to me.

 Similar Threads Thread Thread Starter Forum Replies Last Post fivemack Software 34 2015-10-25 16:54 davieddy Information & Answers 6 2011-12-08 08:07 Christenson Forum Feedback 0 2011-03-21 03:49 NeoGen Math 7 2007-03-13 00:04 fetofs Factoring 39 2006-07-26 12:32

All times are UTC. The time now is 03:06.

Wed Dec 8 03:06:33 UTC 2021 up 137 days, 21:35, 1 user, load averages: 1.47, 1.73, 1.81