![]() |
![]() |
#1 |
Oct 2008
52 Posts |
![]()
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 |
![]() |
![]() |
![]() |
#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 |
![]() |
![]() |
![]() |
#3 | |
Nov 2003
164448 Posts |
![]() Quote:
|
|
![]() |
![]() |
![]() |
#4 | |
Oct 2008
52 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 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. |
|
![]() |
![]() |
![]() |
#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 2009-01-03 at 16:45 |
![]() |
![]() |
![]() |
#6 |
Nov 2005
32×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...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 |
![]() |
![]() |
![]() |
#7 |
Tribal Bullet
Oct 2004
1101110011102 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.
|
![]() |
![]() |
![]() |
#8 |
Nov 2005
1438 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.
|
![]() |
![]() |
![]() |
#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.
|
![]() |
![]() |
![]() |
#10 |
Oct 2008
110012 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 |
![]() |
![]() |
![]() |
#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 | |
![]() |
||||
Thread | Thread Starter | Forum | Replies | Last Post |
SIQS on GPU | cgy606 | Factoring | 1 | 2016-10-21 13:37 |
SIQS problems | henryzz | Factoring | 2 | 2013-08-26 23:02 |
SIQS Problem | patrickkonsor | Factoring | 3 | 2008-10-20 12:03 |
partial relations in SIQS | ThiloHarich | Factoring | 6 | 2007-12-03 18:48 |
Simple Idea for SIQS | ThiloHarich | Factoring | 5 | 2006-03-16 08:22 |