mersenneforum.org SIQS implemantation... help needed :(
 Register FAQ Search Today's Posts Mark Forums Read

 2009-01-02, 19:41 #1 Hermes     Oct 2008 52 Posts SIQS implemantation... help needed :( Hi guys I've implemented a small version of the SIQS sieve some time ago. now, after some changes I discovered that when growing the digits size of the number to be factorized, even if I can collect enough relations (about 1.2 times the factor base size) i'm not able to factor it since that, after the linear algebra stage all the linear combination found of smooth numbers for which holds: x^2 = y^2 mod n are of the form x = +- y mod n so them can't give any factor of n. note that this behaviour is not sistematic, but it seems to happens more frequently by the growing of the number to be factorized. Since I made some check, I have a little fear that the trouble is that my sieve stage is not really good... infact if i try to factor: 25626911509016950901475527595812441191940963052854598209 my siqs implementation uses a FB_size of about 3500 primes in the sieve space [-320k; +320k] I can collect about 4.200 smooth numbers by using 3950 polynomials (with several changes of the 'a' value) so I can collect about 1.1 smooth numbers per-polynomial. and can't find any factor! Can Someone suggest me some checks that I may perform? reallly thanks. /Hermes Last fiddled with by Hermes on 2009-01-02 at 19:59
 2009-01-03, 02:56 #2 jasonp Tribal Bullet     Oct 2004 2×3×19×31 Posts My usual sequence of debugging checks: - start at the square root. Verify that all the powers of all primes are even. If yes, then probably your linear algebra is okay. If no, whatever is going on may have to do with your mapping of relations to matrix columns - if the problem does not happen all the time, look for relations that may be bad somehow, i.e. the sieve value does not equal the product of the factors
2009-01-03, 03:37   #3
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by jasonp My usual sequence of debugging checks: - start at the square root. Verify that all the powers of all primes are even. If yes, then probably your linear algebra is okay. If no, whatever is going on may have to do with your mapping of relations to matrix columns - if the problem does not happen all the time, look for relations that may be bad somehow, i.e. the sieve value does not equal the product of the factors
Check for duplicate relations. They lead to a trivial dependency.

2009-01-03, 13:30   #4
Hermes

Oct 2008

318 Posts

Quote:
 Originally Posted by R.D. Silverman Check for duplicate relations. They lead to a trivial dependency.
After some checks i found that my siqs finds a lots of duplicate values of Q(t).

all of them are of the form Q(t1) = Q(t2), where t1 != t2.

for example:

Code:
[info] Found congruence: [R1733,R4079,]
SmoothN:  t=46301 | 1 * -1^1 * 5^2 * 19^1 * 67^1 * 79^1 * 1009^1 * 1033^1 * 1039^1 * 1051^1 * 1283^1 * 1367^1 * 1871^1 * 2207^1 * 3929^1 * 3931^1 * 9613^1 * 18229^1 * 19447^1 * 21523^1 |
|-> Q(46301) = -23476796006856163782154327960562329776058468371263977025 | a = 30556163745815338145843 | b = 51546277647491137453284185

SmoothN: t=33381= | 1 * -1^1 * 5^2 * 19^1 * 67^1 * 79^1 * 1009^1 * 1033^1 * 1039^1 * 1051^1 * 1283^1 * 1367^1 * 1871^1 * 2207^1 * 3929^1 * 3931^1 * 9613^1 * 18229^1 * 19447^1 * 21523^1 |
|-> Q(33381) = -23476796006856163782154327960562329776058468371263977025 | a = 44560079788324627958591 | b = -21132808171577296941765243

[eureka] Combo Found:  | 1 * -1^2 * 5^4 * 19^2 * 67^2 * 79^2 * 1009^2 * 1033^2 * 1039^2 * 1051^2 * 1283^2 * 1367^2 * 1871^2 * 2207^2 * 3929^2 * 3931^2 * 9613^2 * 18229^2 * 19447^2 * 21523^2 |
this is correct since the 'a' and the 'b' params in:

Q(t) = ( at + b )^2 - N

are different in Q(t1) and Q(t2).

Since i use the graycode approach to generate the 'b' param, once that the 'a' param is generated, the problem seems to be on the 'a' param generation itself.

actually, since I've no found any algorithm that explains how to exactly compute 'a',
I just try to minimize the difference beetween 'a' and sqrt(2*N)/M, as explained in the Contini thesis.
Then, when all possibles 'b' values are generated with a given 'a', I update the 'a' value by change one prime factor of 'a'.

each 'a' value is generated once, but seems that my approach is too poor and causes a lots of not-uniques Q(t).

Unfortunately I've no idea how to improve my 'a' generation strategy.

can someone suggest me a better approach to generate the 'a' param? :)

really thanks.

/Hermes.

 2009-01-03, 16:40 #5 jasonp Tribal Bullet     Oct 2004 2×3×19×31 Posts Coming up with a scheme to generate 'a' values, where each batch of factors is close to the optimal 'a' and doesn't repeat previous choices, was much harder than I anticipated, especially if the method is supposed to work for any size input. If you have the msieve source, you can look in mpqs/poly.c (function poly_init) to see how that code solves the problem. The postprocessing still filters out duplicates, but I've never seen the library generate duplicate QS relations. Basically the msieve source picks the anticipated size of each factor up front, then randomly chooses all factors but the last, then chooses the last to get as close as possible to the optimal 'a'. Other choices include iterating through all choices of k primes out of n possible (google 'NEXKSB' for a very elegant combinatorial algorithm that does that), and Percival's scheme of choosing most factors only rarely but making the last one an increasing sequence of primes just above the factor base limit. Last fiddled with by jasonp on 2009-01-03 at 16:45
 2009-01-04, 17:57 #6 ThiloHarich     Nov 2005 6316 Posts One strategy is to split the factors in two parts (say one with even one with odd index). I think it is called Carrier Wagstraff method. I read it in http://www.google.de/url?sa=t&source...q5f-H4EirKy1Yg or search for kechlibar quardratic sieve in google. Then some correctors are defined, which are a small product of the first group. Depending on the size you can choose 2 or 3 for it. Then choose factors from the other group, find the corrector to achieve a 'a' in the near of the desired value. delete the corrector. Choose the next set of factor from the other group without using the ones we had before. i'm not sure if we can always use new once, but you can force that they are different at many positions. The factor should not be to small, since this causes doubles. Think of a 2 in the a, which is an every second relation as well. How are your a's for duplicate rows? Last fiddled with by ThiloHarich on 2009-01-04 at 17:59
 2009-01-04, 19:12 #7 jasonp Tribal Bullet     Oct 2004 2×3×19×31 Posts I don't understand your question; while duplicates are possible the way msieve generates 'a' values, I've never seen it happen. Even a pool of 40-100 factor base primes is enough to generate all the 'a' values required.
 2009-01-05, 08:08 #8 ThiloHarich     Nov 2005 32·11 Posts I had the problem as well, but i choose the factors of the a's to be rather small, since this gives more you more b's. But then you might get the problem of duplicates.
2009-01-05, 14:01   #9
bsquared

"Ben"
Feb 2007

D2116 Posts

Quote:
 Originally Posted by ThiloHarich I had the problem as well, but i choose the factors of the a's to be rather small, since this gives more you more b's. But then you might get the problem of duplicates.
What is small? In my experience, choosing primes > 1000 works fine. Like msieve, I've never seen YAFU generate duplicates with that choice, and still get plenty of b's per a. Profiling shows that the 'a' poly initialization only takes a fraction of a percent, and any size job only typically requires a few hundred 'a' polys.

 2009-01-05, 15:56 #10 Hermes     Oct 2008 52 Posts ok... i updated my bad version of siqs now the sieve can easily be able to change the 'a' generator... to make some tests I've implemented the simpler algorithm... actually it generates a good 'a' values with a reasonable frequency ( about 80% of the generated values have a distance below the 2% from the ideal bound ). it seems to works better now... so I will made some tests... Just a question, can I use a multiplier of n, computed with the knuth schroeppel func tion, as described in the Silverman paper for the MPQS? would it be faster? :) /hermes
2009-01-05, 16:08   #11
bsquared

"Ben"
Feb 2007

3,361 Posts

Quote:
 Originally Posted by Hermes Just a question, can I use a multiplier of n, computed with the knuth schroeppel func tion, as described in the Silverman paper for the MPQS? would it be faster? :) /hermes
Yes, just be sure to choose the multiplier before you compute your factor base. It will most likely be noticably faster.

 Similar Threads Thread Thread Starter Forum Replies Last Post cgy606 Factoring 1 2016-10-21 13:37 henryzz Factoring 2 2013-08-26 23:02 patrickkonsor Factoring 3 2008-10-20 12:03 ThiloHarich Factoring 6 2007-12-03 18:48 ThiloHarich Factoring 5 2006-03-16 08:22

All times are UTC. The time now is 10:35.

Fri Jan 22 10:35:29 UTC 2021 up 50 days, 6:46, 0 users, load averages: 1.90, 2.02, 2.12