partial relations in SIQS
When (at which bit length) does the usage of 1partial Primes decreases the running time?

[QUOTE=ThiloHarich;118860]When (at which bit length) does the usage of 1partial Primes decreases the running time?[/QUOTE]
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) 
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 [url]http://www.mersenneforum.org/showthread.php?t=7212[/url]. I need 1.6 sec with my java application to find the factor. 
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. 
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 
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. 
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. 
All times are UTC. The time now is 14:33. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.