P95 Trial Factor speeds 40M vs 100M

harlee · 2006-10-13, 23:27

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:

Factor=100000039,60
Factor=40509211,60
Factor=100000039,60
Factor=40509211,60
Factor=100000039,60

results.ini

Quote:

[Fri Oct 13 18:05:34 2006]
UID: harlee/sandy, M100000039 no factor to 2^62, Wc1: BFCC997C
[Fri Oct 13 18:21:49 2006]
UID: harlee/sandy, M40509211 no factor to 2^62, Wc1: 84D60D98
[Fri Oct 13 18:28:44 2006]
UID: harlee/sandy, M100000039 no factor to 2^62, Wc1: BFCC997C
[Fri Oct 13 18:44:57 2006]
UID: harlee/sandy, M40509211 no factor to 2^62, Wc1: 84D60D98
[Fri Oct 13 18:51:48 2006]
UID: harlee/sandy, M100000039 no factor to 2^62, Wc1: BFCC997C

I have found factors up in the 2^61 bit range:

Quote:

UID: harlee/sandy, M100100551 has a factor: 4426226718384761639
UID: harlee/sandy, M100117763 has a factor: 4244800983563813593
UID: harlee/penny, M100000213 has a factor: 4213987137373484209
UID: harlee/penny, M100011677 has a factor: 4014409117221605639

markr · 2006-10-14, 03:49

Trial-factoring 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.

TheJudger · 2006-10-14, 11:15

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.

harlee · 2006-10-15, 04:38

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.

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

2006-10-14, 03:49	#2
markr "Mark" Feb 2003 Sydney 3·191 Posts	Trial-factoring 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=2kP+1, where P is the prime exponent itself and k is an integer >=1. So for smaller exponents, potential factors are closer together.

2006-10-14, 11:15	#3
TheJudger "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.

2006-10-15, 04:38	#4
harlee Sep 2006 Odenton, MD, USA 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=2kP+1 and think about it, the more it is beginning to make sense.