mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2014-02-01, 21:16   #1
vinloren
 
Dec 2013

22 Posts
Unhappy 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.
vinloren is offline   Reply With Quote
Old 2014-02-01, 22:20   #2
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

133310 Posts
Default

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
alpertron is offline   Reply With Quote
Old 2014-02-02, 00:46   #3
vinloren
 
Dec 2013

22 Posts
Question QS question regarding finding just trivial solutions

Quote:
Originally Posted by alpertron View Post
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.
vinloren is offline   Reply With Quote
Old 2014-02-02, 01:54   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1C4016 Posts
Default

Quote:
Originally Posted by alpertron View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2014-02-02, 02:13   #5
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

31×43 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2014-02-02, 07:06   #6
vinloren
 
Dec 2013

22 Posts
Smile

Quote:
Originally Posted by alpertron View Post
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.
vinloren is offline   Reply With Quote
Old 2014-02-02, 13:57   #7
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

348910 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2014-02-02, 19:52   #8
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

26×72 Posts
Default

Quote:
Originally Posted by vinloren View Post
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.
RichD is offline   Reply With Quote
Old 2014-02-02, 21:04   #9
vinloren
 
Dec 2013

22 Posts
Smile QS question regarding finding just trivial solutions / solved

Quote:
Originally Posted by jasonp View Post
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.
vinloren is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Suddenly I'm getting only trivial TF tests fivemack Software 34 2015-10-25 16:54
Trivial question davieddy Information & Answers 6 2011-12-08 08:07
Trivial bug: repeated PM notifications Christenson Forum Feedback 0 2011-03-21 03:49
newbie question - finding small factors of very large numbers NeoGen Math 7 2007-03-13 00:04
SNFS trivial factorization fetofs Factoring 39 2006-07-26 12:32

All times are UTC. The time now is 23:31.

Wed Oct 28 23:31:23 UTC 2020 up 48 days, 20:42, 1 user, load averages: 1.96, 2.09, 1.92

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.