Thread: SIQS problems
View Single Post
Old 2013-08-26, 11:11   #1
Just call me Henry
henryzz's Avatar
Sep 2007
Cambridge (GMT/BST)

2·2,909 Posts
Default 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.
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.
henryzz is offline   Reply With Quote