SIQS problems

henryzz · 2013-08-26, 11:11

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.

bsquared · 2013-08-26, 14:29

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.

henryzz · 2013-08-26, 23:02

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.

2013-08-26, 11:11	#1
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 1011010111010₂ 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 (Ax+B)^2-N and for here (Ax+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.

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

2013-08-26, 14:29	#2
bsquared "Ben" Feb 2007 110100101011₂ 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
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 1011010111010₂ 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.