mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-11-20, 10:55   #1
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

6316 Posts
Default partial relations in SIQS

When (at which bit length) does the usage of 1-partial Primes decreases the running time?
ThiloHarich is offline   Reply With Quote
Old 2007-11-20, 13:51   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

348910 Posts
Default

Quote:
Originally Posted by ThiloHarich View Post
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)
jasonp is offline   Reply With Quote
Old 2007-11-21, 16:46   #3
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

6316 Posts
Default

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 is offline   Reply With Quote
Old 2007-11-21, 16:52   #4
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

32·11 Posts
Default

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.
ThiloHarich is offline   Reply With Quote
Old 2007-11-21, 17:25   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13×257 Posts
Default

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
bsquared is offline   Reply With Quote
Old 2007-11-22, 17:17   #6
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

1438 Posts
Default

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 2007-11-22 at 17:46
ThiloHarich is offline   Reply With Quote
Old 2007-12-03, 18:48   #7
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

32×11 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
SIQS on GPU cgy606 Factoring 1 2016-10-21 13:37
Distribution of relations over the sieving interval in SIQS mickfrancis Factoring 3 2014-05-20 15:45
Reporting partial ECM results? apsen PrimeNet 3 2011-07-03 14:54
More relations mean many more relations wanted fivemack Factoring 7 2007-08-04 17:32
Partial fraction of this expression?please!! tinhnho Miscellaneous Math 4 2005-01-17 19:45

All times are UTC. The time now is 09:20.

Wed Nov 25 09:20:40 UTC 2020 up 76 days, 6:31, 4 users, load averages: 1.61, 1.64, 1.49

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.