20071120, 10:55  #1 
Nov 2005
101 Posts 
partial relations in SIQS
When (at which bit length) does the usage of 1partial Primes decreases the running time?

20071120, 13:51  #2 
Tribal Bullet
Oct 2004
3537_{10} Posts 
As usual, it depends on a lot of different things: the choice of factor base size, the speed of trial factoring relative to sieving (you will be doing much more of the former because the cutoff for accepting sieve values is lower), etc. In my experience it is always beneficial to use one large prime, except maybe for the very smallest jobs (< 18 digits or so)

20071121, 16:46  #3 
Nov 2005
145_{8} Posts 
My factor base is greater then yours (around two times).
I tried various factoring algorithms  resieving  trial division  pollard rho  mixture of resieving and trial division  mixture of resieving and trial division with large primes mixture of resieving and trial division (at the 500 th prime in the factor base i switch) give best results. The factoring needs half of the complete time (the other half is due to sieving). So, not surprisingly sieving with large primes does not improve the speed. For the example '732197471686198597184965476425281169401188191' given in http://www.mersenneforum.org/showthread.php?t=7212. I need 1.6 sec with my java application to find the factor. 
20071121, 16:52  #4 
Nov 2005
101 Posts 
I do not use the (slow) java class BigInteger to do the trial factoring.
Instead i look at the modulus due to a factor p of the factor base, which is an primitive int. Only if the index x of the generating function a(x) + b mod p hits one of the two roots mod p for the factor p we do the expensive division. But the division stage is still to slow. 
20071121, 17:25  #5 
"Ben"
Feb 2007
2·3^{2}·191 Posts 
Maybe your factor base is just too big. More primes > more trial division.
My siqs implementation wants 913 relations normally. In this case, it uses 0.436 sec sieving and 0.19 sec doing trial division. If I force it to use a factor base of size 1826 (x2 bigger), this becomes 0.27 sec sieving and 0.61 sec doing trial division, for a net slowdown.  ben 
20071122, 17:17  #6 
Nov 2005
101 Posts 
If I use a Factor Base size of 1624 I have the following timings:
Time sieving 2.014 sec Time factoring .406 sec # polynoms: 792 If I use my Factor base with size 4022 Time sieving .922 sec Time factoring .535 sec # polynoms: 331 Search Interval is 157228, I use no large Primes here. I do not know how to speed up sieving, since it is just a simple loop. while (xIndex < length) { qLength [xIndex] = factorLength; xIndex += factor; } For the large Factorbase switching the polynomial needs only a small portion of the running time. Last fiddled with by ThiloHarich on 20071122 at 17:46 
20071203, 18:48  #7 
Nov 2005
101 Posts 
I had a simple bug now it works with large Primes:
Time sieving .893 sec Time factoring .467 sec 2966 decompositions over all 794 Large decompositions If I switch to smaller factor bases (1500 decompositions), the sieving time goes up to 1.500 sec. This might be due to the slow handling of array in java in the sieving phase. Even HotSpot (which compiles/optimizes often used parts) does hot help since the main loop is executed for the higher primes in the factor base only a few times ( < 10). Thanks for the input. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
SIQS on GPU  cgy606  Factoring  1  20161021 13:37 
Distribution of relations over the sieving interval in SIQS  mickfrancis  Factoring  3  20140520 15:45 
Reporting partial ECM results?  apsen  PrimeNet  3  20110703 14:54 
More relations mean many more relations wanted  fivemack  Factoring  7  20070804 17:32 
Partial fraction of this expression?please!!  tinhnho  Miscellaneous Math  4  20050117 19:45 