Go Back > Factoring Projects > Factoring

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

22×1,481 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
Old 2013-08-26, 14:29   #2
bsquared's Avatar
Feb 2007

2×1,789 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.
bsquared is offline   Reply With Quote
Old 2013-08-26, 23:02   #3
Just call me Henry
henryzz's Avatar
Sep 2007
Cambridge (GMT/BST)

172416 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.
henryzz is offline   Reply With Quote

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

All times are UTC. The time now is 05:32.

Thu Oct 28 05:32:14 UTC 2021 up 97 days, 1 min, 0 users, load averages: 1.93, 1.74, 1.77

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.