2009-02-28, 23:38 | #1 |
10011100000110_{2} Posts |
Trial factoring speed
Hello,
I am using Windows XP (32-bit) with 32-bit Prime95 (25.9 build 3). I have an AMD Athlon 64 3200+. For fun I started trial factoring exponents in the 99,000,000 range. I also started trial factoring exponents in the 199,000,000 range. It seems that the exponents in the 199 million range trial factor *faster* than the smaller ones in the 99 million range. Is there a mathematical reason for this? My worktodo.txt: Factor=199999673,0,63 Factor=99999073,0,63 Trial factoring to 63 bits is faster on the bigger exponent. Does anyone else see similar results? |
2009-03-01, 00:32 | #2 |
"Nancy"
Aug 2002
Alexandria
2,467 Posts |
Yes, there's a mathematical reason. A Mersenne number 2^{[I]p[/I]}-1 can only have factors of the form 2kp+1, so a larger exponent means there are fewer candidate factors to test below a given bound. There is some more info on the math behind GIMPS at http://www.mersenne.org/various/math.php
Alex |
2009-03-01, 00:57 | #3 |
13040_{8} Posts |
15 Ridgely
Ahhh, that makes sense. As p gets higher, there's less potential factors due to 2kp+1.
I had the mindset that for general numbers, the bigger the number, the longer the number of calculations and the longer the time it would take to trial factor all primes < 2^X. Thanks for your quick response. |
2009-03-01, 02:43 | #4 |
Einyen
Dec 2003
Denmark
2·17·101 Posts |
It's because the bitdepth is the "standard" choice for measuring trialfactoring, but for mersennenumbers it's not very logical, since we only test every 2*k*p from k=1,2,3.....
For your exponent 99999073 k-values up to 2^63/(2*99999073) = 46.1*10^{9} are tested, but for 199999673 only k-values up to 2^63/(2*199999673) = 23.1 * 10^{9} are tested. So if you test 199999673 to 64bit instead it will correspond to almost the same number of tests and you'll see that 199999673 will take longer. Last fiddled with by ATH on 2009-03-01 at 02:43 |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
GPU Trial Factoring FAQ | garo | GPU Computing | 100 | 2019-04-22 10:58 |
Approximating Factoring Speed | hasan4444 | Factoring | 17 | 2009-10-28 14:34 |
Clues to speed up the factoring | zarabatana | Miscellaneous Math | 21 | 2009-10-17 02:50 |
Speed of P-1 testing vs. Trial Factoring testing | eepiccolo | Math | 6 | 2006-03-28 20:53 |
How to only do Trial Factoring? | michael | Software | 23 | 2004-01-06 08:54 |