partial relations in SIQS

[ThiloHarich]

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

[jasonp]

Originally Posted by ThiloHarich

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

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)

[ThiloHarich]

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.

[ThiloHarich]

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.

[bsquared]

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

[ThiloHarich]

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.

[ThiloHarich]

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.