20090102, 19:41  #1 
Oct 2008
5^{2} 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 perpolynomial. 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 20090102 at 19:59 
20090103, 02:56  #2 
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 
20090103, 03:37  #3  
Nov 2003
16444_{8} Posts 
Quote:


20090103, 13:30  #4  
Oct 2008
5^{2} Posts 
Quote:
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  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 notuniques 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. 

20090103, 16:40  #5 
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 20090103 at 16:45 
20090104, 17:57  #6 
Nov 2005
3^{2}×11 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...q5fH4EirKy1Yg
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 20090104 at 17:59 
20090104, 19:12  #7 
Tribal Bullet
Oct 2004
110111001110_{2} 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 40100 factor base primes is enough to generate all the 'a' values required.

20090105, 08:08  #8 
Nov 2005
143_{8} 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.

20090105, 14:01  #9 
"Ben"
Feb 2007
3,371 Posts 
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.

20090105, 15:56  #10 
Oct 2008
11001_{2} 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 
20090105, 16:08  #11 
"Ben"
Feb 2007
3,371 Posts 
Yes, just be sure to choose the multiplier before you compute your factor base. It will most likely be noticably faster.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
SIQS on GPU  cgy606  Factoring  1  20161021 13:37 
SIQS problems  henryzz  Factoring  2  20130826 23:02 
SIQS Problem  patrickkonsor  Factoring  3  20081020 12:03 
partial relations in SIQS  ThiloHarich  Factoring  6  20071203 18:48 
Simple Idea for SIQS  ThiloHarich  Factoring  5  20060316 08:22 