Why is TFing small numbers harder?

casmith789 · 2014-12-19, 19:30

If I go to mersenne.ca I can work out the CPU credit for each assignment. Why is the CPU credit approx. 10x more when doing an exponent 10 times smaller? Shouldn't it be the same or even more for the larger exponent given bigger numbers are involved?

e.g.

M100000 from 2^70 to 2^71 - 2391 GHz days
M1000000 from 2^70 to 2^71 - 239 GHz days
M10000000 from 2^70 to 2^71 - 24 GHz days

paulunderwood · 2014-12-19, 19:42

Let Mp=2^p-1. Then Mp factors into the product of numbers of the form 2*p*n+1. So you get more bits for free with larger p when doing trial division, as you can step 2*p. I will leave it up to you to find out about factors modulo 8.

ATH · 2014-12-19, 20:16

For M100000 you need to search 2*n*p + 1 where n goes from: 2^70 / (2*100000) = 5,902,958,103,587,056 to 2^71 / (2*100000) = 11,805,916,207,174,113.

For M1000000 n goes from 2^70 / (2*1000000) = 590,295,810,358,705 to 2^71 / (2*1000000) = 1,180,591,620,717,411 and for M10000000 n goes from 59,029,581,035,870 to 118,059,162,071,741.

So each time the exponent raises by factor of 10 the search space decreases by a factor of 10, because we register the factor depth of the entire factor 2*p*n + 1 instead of the size or bit depth of the constant n.

casmith789 · 2014-12-19, 22:35

Thanks guys, that makes sense

MattcAnderson · 2014-12-21, 16:23

You're welcome.

2014-12-19, 19:30	#1
casmith789 Dec 2014 10₁₆ Posts	Why is TFing small numbers harder? If I go to mersenne.ca I can work out the CPU credit for each assignment. Why is the CPU credit approx. 10x more when doing an exponent 10 times smaller? Shouldn't it be the same or even more for the larger exponent given bigger numbers are involved? e.g. M100000 from 2^70 to 2^71 - 2391 GHz days M1000000 from 2^70 to 2^71 - 239 GHz days M10000000 from 2^70 to 2^71 - 24 GHz days

2014-12-19, 19:42	#2
paulunderwood Sep 2002 Database er0rr 2×3²×11×19 Posts	Let Mp=2^p-1. Then Mp factors into the product of numbers of the form 2pn+1. So you get more bits for free with larger p when doing trial division, as you can step 2p. I will leave it up to you to find out about factors modulo 8. Last fiddled with by paulunderwood on 2014-12-19 at 19:50*

2014-12-19, 20:16	#3
ATH Einyen Dec 2003 Denmark 6126₈ Posts	For M100000 you need to search 2np + 1 where n goes from: 2^70 / (2100000) = 5,902,958,103,587,056 to 2^71 / (2100000) = 11,805,916,207,174,113. For M1000000 n goes from 2^70 / (21000000) = 590,295,810,358,705 to 2^71 / (21000000) = 1,180,591,620,717,411 and for M10000000 n goes from 59,029,581,035,870 to 118,059,162,071,741. So each time the exponent raises by factor of 10 the search space decreases by a factor of 10, because we register the factor depth of the entire factor 2pn + 1 instead of the size or bit depth of the constant n. Last fiddled with by ATH on 2014-12-19 at 20:17

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
TFing 100M numbers	aurashift	Information & Answers	46	2015-05-01 04:09
ECM on small Mersenne Numbers	Erich	PrimeNet	16	2012-09-29 23:08
P-1 on small numbers	Unregistered	Information & Answers	2	2011-08-22 22:53
Strong Law of Small Numbers?	Christenson	Information & Answers	36	2011-02-16 04:29
A new Strong Law of Small Numbers example	cheesehead	Math	7	2009-02-06 20:49

2014-12-19, 22:35	#4
casmith789 Dec 2014 2⁴ Posts	Thanks guys, that makes sense

2014-12-21, 16:23	#5
MattcAnderson "Matthew Anderson" Dec 2010 Oregon, USA 1100100001₂ Posts	You're welcome.