2013-08-26, 11:11 | #1 |
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
3·5·383 Posts |
SIQS problems
I recently extended my quadratic sieve to SIQS. It worked quite well until I changed my method of generating A to make it closer to targetA=sqrt(2N)/M.
After that change it originally seemed to work fine but while tuning parameters it started crashing. It turns out that I found a duplicate relation. I didn't have a check for these as none should be found(unless there is a bug). The same relation is somehow found with two different polynomials. N=200000000000000000000000000028400000000000000000000000000969 A=966466736918196863836633 B=214349049608676801882804 x=466249 A=965342290912881030458861 B=305310616416273815538509 x=466792 I am sieving the poly (A*x+B)^2-N and for here (A*x+B)^2-N=450614363970421978243768182421 for both polys. Originally I though the problem must be because A shared all but 1 factor but no. They share all but 3 factors(according to mersennewiki this is fine). 966466736918196863836633=2339 · 2351 · 2357 · 2423 · 2473 · 2663 · 4673 965342290912881030458861=2339 · 2351 · 2399 · 2423 · 2467 · 2663 · 4597 I have done things like check B^2-N = 0 mod A and jacobi(A,N)=1 What is wrong with my poly generation? My sources for implementing this have been a combination on contini, mersennewiki, C&P and whatever I have found on mersenneforum. I would greatly love to fix this very occasional bug. Once this is sorted I have a question or 2 to ask as well. |
2013-08-26, 14:29 | #2 |
"Ben"
Feb 2007
110100001101_{2} Posts |
Contini notes that if the composition of the 'A' coefficient differs by 2 or more primes then the redundancy is greatly reduced, not eliminated. Duplicate relations are still possible. yafu turns them up regularly.
It's not clear to me how the duplicates are causing your program to crash, but if you detect and remove them it might help. |
2013-08-26, 23:02 | #3 |
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
3·5·383 Posts |
Looks like I have just been unlucky in finding this example then.
Something about how I implemented the gaussian elimination causes it to crash when i have a duplicate. It is probably something to do with say I have a relation set of {1,2} and {2,3} multiplying them together I get {1,3}. In this case I multiple {1} and {1} and get {} The empty relation fails when my code tries to do the sqrt on it. An oddity I have noticed is that I can't sieve the full way in the negative direction before (a*x+b) becomes negative. I can only sieve a range of M/sqrt(2) on the negative side rather than the full interval of M in both directions. Considering I used the fact that I plan to sieve M in both directions in calculating the optimum value of A=sqrt(2N)/M should I change my reasoning for the size of A? Is there something I am missing? This has been an interesting exercise. It can now factor 75 digit numbers in ~40 minutes. 80 digits crashed in the sqrt stage(after 2.5 hours of running). I suspect it is quite possibly something to do with the homegrown multiprecision library I am using not being planned for so large numbers. |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
SIQS on GPU | cgy606 | Factoring | 1 | 2016-10-21 13:37 |
SIQS implemantation... help needed :( | Hermes | Factoring | 24 | 2009-01-16 12:21 |
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 |