mersenneforum.org partial relations in SIQS
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2007-11-20, 10:55 #1 ThiloHarich     Nov 2005 10110 Posts partial relations in SIQS When (at which bit length) does the usage of 1-partial Primes decreases the running time?
2007-11-20, 13:51   #2
jasonp
Tribal Bullet

Oct 2004

33×131 Posts

Quote:
 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)

 2007-11-21, 16:46 #3 ThiloHarich     Nov 2005 101 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.
 2007-11-21, 16:52 #4 ThiloHarich     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.
 2007-11-21, 17:25 #5 bsquared     "Ben" Feb 2007 65548 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
 2007-11-22, 17:17 #6 ThiloHarich     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 2007-11-22 at 17:46
 2007-12-03, 18:48 #7 ThiloHarich     Nov 2005 11001012 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 cgy606 Factoring 1 2016-10-21 13:37 mickfrancis Factoring 3 2014-05-20 15:45 apsen PrimeNet 3 2011-07-03 14:54 fivemack Factoring 7 2007-08-04 17:32 tinhnho Miscellaneous Math 4 2005-01-17 19:45

All times are UTC. The time now is 08:28.

Sat May 8 08:28:32 UTC 2021 up 30 days, 3:09, 0 users, load averages: 3.34, 3.68, 3.92

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.