20061013, 23:27  #1  
Sep 2006
Odenton, MD, USA
244_{8} Posts 
P95 Trial Factor speeds 40M vs 100M
I'm running Prime95 V24.14 on a XP SP2 P4 2.6GHz . I've noticed that it takes longer to trial factor a 40.5M exponent from 2^60 to 2^62 bits then doing a 100M exponent (approx 16mins vs approx 7mins). Just wondering why?
worktodo.ini Quote:
Quote:
Quote:


20061014, 03:49  #2 
"Mark"
Feb 2003
Sydney
3·191 Posts 
Trialfactoring smaller exponents takes longer because there are more potential factors in a given size range eg 2^60 to 2^62. This is because any factor has to have the form q=2*k*P+1, where P is the prime exponent itself and k is an integer >=1. So for smaller exponents, potential factors are closer together.

20061014, 11:15  #3 
"Oliver"
Mar 2005
Germany
2×3×5×37 Posts 
Take a look here: http://mersenne.org/math.htm
as markr allready said: there are less candidates for factors in 100M mersennes from 60 to 62 bits (factor size) as in 40M mersennes. As a rule of thumb there are ~2.5 times more factor candidates for a 40M than for a 100M mersenne number in a specific range (factor size). On the other hand testing a single candidate for a 100M mersenne takes only one step longer than testing a single candidate for a 40M mersenne number. 26 steps for ~33M to ~67M 27 steps for ~67M to ~134M The number of steps for a single candidate is ceil(log2(exponent)). The duration of on step itself depends only on the size of the candidate. Since they are same size for your example each step takes the same ammount of time. 
20061015, 04:38  #4 
Sep 2006
Odenton, MD, USA
2^{2}·41 Posts 
Thanks for the information. I've been reading the references and at first they didn't make a lot of sense to me. But, the more I look at the form q=2*k*P+1 and think about it, the more it is beginning to make sense.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How many bits does/did the server trial factor to?  Jayder  Information & Answers  6  20150125 03:29 
100M digits, how much trial factoring will it do?  xorbe  LMH > 100M  189  20101209 08:30 
Trial Factor Bit Depth  lavalamp  Operation Billion Digits  8  20100802 18:49 
trial division over a factor base  Peter Hackman  Factoring  7  20091026 18:27 
Shortest time to complete a 2^67 trial factor (no factor)  dsouza123  Software  12  20030821 18:38 