Cunningham Tables @mersenneforum.org v2.0

garo · 2005-08-01, 15:17

In this subforum we are attempting to summarize the amount of ECM work known to have been done on the Cunningham Table composites.

v2.0 of the tables at mersenneforum have undergone many changes. The changes are as follows:

1. I have removed the 2- and 2+ tables as they are already on George's website at http://mersenne.org/ecm.htm Hosting them here caused a lot of confusion. I am however keeping track of 2LM work and a new thread has been created for it.

2. The curves reported are now in ECM6 curves. Note that this is different from the old B2=100*B1 we were using. George's pages are still using the old definition so please take care not to get confused.

3. Along with the curve counts, I am also keeping track of the proportion of work that has been finished for each level. For example, under 12,236+ for the 43M or 50 digit level you will see 3355 (0.558516). This means that 3355 ECM6 equivalent curves have been run at this level. Normally, 7771 curves are required at this level which would give us a completion proportion of 0.4317. But we see a completion proportion of 0.55 as 400 curves have already been run at the 110M or 55 digit level and these curves also impact the completion proportion at all other levels.

For the more technically minded, if the completion proportion is "x", it means that if a factor at that bit level exists then the probability that it has been missed is e^-x.

The precise formula used for computing the completion proportionis as follows:
t45 = c45/4590 + c50/1321 +c55/617 + c60/300;
t50 = c45/34522 + c50/7771 + c55/3155 +c60/1500;
t55 = c50/51303 + c55/17899 + c60/9000;
t60 = c55/111395 + c60/43670;

where t45 gives the 45digits proportion complete figure and c45 gives the number of curves run at 45 digits. This illustrates that 617 curves at the 55 digit level are equivalent to the optimal number at the 45 digit level. Note that my denominators for c60 are not precise. If someone can give me exact numbers I will make the change ehre and remove this comment.

Finally, numbers marked as resv have been reserved for GNFS/SNFS and thus no further ECM is required on these numbers.

garo · 2005-08-01, 15:38

Hence, to find out how much work is required at a given level, check the number in brackets for that level.. If it is greater than 1, no more work is required at that level. If it is less than 1, subtract it from 1 and multiply that figure by the optimal number of ECM6 curves (or Prime95 curves if you are using Prime95 for stage 2).

The optimal number of curves required is:

Code:

digits 	optimal B1 	expected curves expected curves
	                (B2=100*B1)     (default parameters for ecm-6.0)
20 	11,000 		84		77
25 	50,000 		262		206
30 	250,000 	648		401
35 	1,000,000 	1,588		948
40 	3,000,000 	4,716		2,440
45 	11,000,000 	9,770		4,590
50 	43,000,000 	18,143		7,771
55 	110,000,000 	45,841		17,899
60 	260,000,000 	114,973		43,670
65 	850,000,000 	193,436		69,351

So continuing with the 12,236+ example, we need (1-0.55)*7771=3495 more curves at the 50 digit level with GMP-ECM6.0 (B1=43M, B2=ECM6.0 default).

Or (1-0.55)*18143 = 8164 more curves with prime95 (B1=43M, B2=4.29G).

garo · 2005-08-01, 17:29

A little more information. The following is the set of curve counts I finally used for Bruce Dodson's work on the Cunningham Tables. This follows from the discussions on this forum as well as emails exchanged between rogue and him that were forwarded to me.

Code:

                p45/11M p50/44M p55/110M p60/260M
c136-145        3755    860     0       0 (was 4500,1000 ecm5)
c146-155        0       2590    0       0 (was 3000 ecm5)
c156-175        0       2160    0       0 (was 2500 ecm5 curves)
c176-185        0       1500    590     0 
c186-195        0       40      630     0 (1000 p50 in progress)
c196-205        0       30      165     0
c206-219        0       0       165     0 
c220-289        0       0       165     0
c290-365        0       0       100     0
c366-384        0       0       530     0

Plus some extra curves on c156-161

bdodson · 2006-07-04, 08:00

Quote:

Originally Posted by garo

A little more information. The following is the set of curve counts I finally used for Bruce Dodson's work on the Cunningham Tables. This follows from the discussions on this forum as well as emails exchanged between rogue and him that were forwarded to me.

Thanks to Mark and Garo for their efforts at sorting through my
versions of curve counts. Seems to be time for an update. The
curves from the Opteron cluster are in two parts. The rest of 2005
has been summarized by Paul Zimmermann on the ECMNET page
c120-355; a 1-liner:

Note (Dec 05): Bruce Dodson did 620 curves on c196-c384 with B1=110e6.

I will break that up as an update on the curves already reported
below. These curves were complete tests to p45 on all of the Cunninghams
in this range [tests at or above p45 having been completed earlier on
all smaller ranges]. The Most Wanted Mersenne number M1061 got
considerable additional attention, another 7875 curves with B1=110M,
for a total of 620+7875 = 8495 curves. Garo's post above (not to
mention Alex's -v report) lists 17899 curves as a complete p55-test,
so I had 8495/17899 = 47.46%. We could translate that into the
B2 = 100*B1 curves on George's page as .4746* 46000 = 21830 curves;
a bit more than the "few" curently listed. If this sounds like a correct
accounting, someone could send the current count on to George?

At the risk of complicating matters, this brings us to 2006, during most
of which I've been using B1=260M. The short version here is that most
of c146 - c210 is (or soon will be) tested up to p50, which includes c. 300
numbers, the smallest one-third of the Cunningham list (all bases, including
base-2, for which counts seem to be elsewhere). I'll indicate counts of
curves completed (and [queued, soon to be completed]) below.

Bruce Dodson

Quote:

Originally Posted by garo

Code:

                p45/11M p50/44M p55/110M p60/260M
c136-145        3755    860     0       0 (was 4500,1000 ecm5)

add 5500/44M.

Quote:

Originally Posted by garo

Code:

c146-155        0       2590    0       0 (was 3000 ecm5)

add 5500/44M.

Quote:

Originally Posted by garo

Code:

c156-175        0       2160    0       0 (was 2500 ecm5 curves)

This range got split. For c156-165,
add 2000/44M and 600/260M, with a last [1000/44M] running.

For c166 - c174, add 1150/260M. With B1=260M, 1538 curves
is a complete test to p50.

Quote:

Originally Posted by garo

Code:

c176-185        0       1500    590     0

For c175 - c185, add 300/260M and 340/850M,
where 850M is p65-optimal, but still requires 660 curves for
a complete test to p50. To answer a question raised by Bob,
the 850M curves were actually run before the 260M curves,
all applied to completing a test to p50. [At the time, the 850M
limits served to test -save/-resume, making use of large memory
- 128Gb - available on our Itanium2 sgi smp.] So in this range,
I have
1000/9000 + 590/3155 + 300/1538 + 340/660 (= 1.008% t50).
Looks like I lost some ecm5 curves somewhere.

Quote:

Originally Posted by garo

Code:

c186-195        0       40      630     0 (1000 p50 in progress)

The summary is
2000/9000 + 1000/7771 + 630/3155 + 710/1538 (1.012% t50),
where 9000 is a test to p50 in ecm5, 7771 to p50 in ecm6 both
with b1=44M. With the above ecm5 translation, I've added
2726 /44M (including the old "in progress") and 710/260M.

Quote:

Originally Posted by garo

Code:

c196-205        0       30      165     0
c206-219        0       0       165     0 
c220-289        0       0       165     0

First, 455 should be added to the 165, for 110M. Next,
the range c196 - c210 was split, and 735/260M added.
I have the last [600/260M] needed for t50 "queued".
Finally, in the range c211 - c250, 285/260M was added.

Current possible continuation might be to further split
c211-c231 (for 768-bits) and possibly c231-c241 (for
800-bits), in which case finishing t50 would take 1050/260M
for each number. There are 865-or-so numbers on the
ecmnet cunningham.in file; 433 would be half, for another
133 numbers of the c. 271 in c211-c250, say somewhere
between 768- and 800-, depending upon how well the available
Opteron cycles hold up.

Quote:

Originally Posted by garo

Code:

c290-365        0       0       100     0
c366-384        0       0       530     0

520/110M and 90/110M should be added. When completing
t50's on the smallest/mid-sized Cunninghams starts looking too
slow/hard, a 2nd pass through c251-c366 with c. 300/260M
would likely clear a few more p44..p46, though not necessarily
being easy to find among many hard numbers.

A short version of recommended limits would be p55-limits,
110M on c166 - c210 (c142 - c165 seem mostly ready to
sieve for the snfs candidates, tracking down the gnfs candidates
probably requires careful case-by-case attention). And
p50-limits, 44M on c251 - c366.

2005-08-01, 15:17	#1
garo Aug 2002 Termonfeckin, IE 2²×691 Posts	Cunningham Tables @mersenneforum.org v2.0 In this subforum we are attempting to summarize the amount of ECM work known to have been done on the Cunningham Table composites. v2.0 of the tables at mersenneforum have undergone many changes. The changes are as follows: 1. I have removed the 2- and 2+ tables as they are already on George's website at http://mersenne.org/ecm.htm Hosting them here caused a lot of confusion. I am however keeping track of 2LM work and a new thread has been created for it. 2. The curves reported are now in ECM6 curves. Note that this is different from the old B2=100B1 we were using. George's pages are still using the old definition so please take care not to get confused. 3. Along with the curve counts, I am also keeping track of the proportion of work that has been finished for each level. For example, under 12,236+ for the 43M or 50 digit level you will see 3355 (0.558516). This means that 3355 ECM6 equivalent curves have been run at this level. Normally, 7771 curves are required at this level which would give us a completion proportion of 0.4317. But we see a completion proportion of 0.55 as 400 curves have already been run at the 110M or 55 digit level and these curves also impact the completion proportion at all other levels. For the more technically minded, if the completion proportion is "x", it means that if a factor at that bit level exists then the probability that it has been missed is e^-x. The precise formula used for computing the completion proportionis as follows: t45 = c45/4590 + c50/1321 +c55/617 + c60/300; t50 = c45/34522 + c50/7771 + c55/3155 +c60/1500; t55 = c50/51303 + c55/17899 + c60/9000; t60 = c55/111395 + c60/43670; where t45 gives the 45digits proportion complete figure and c45 gives the number of curves run at 45 digits. This illustrates that 617 curves at the 55 digit level are equivalent to the optimal number at the 45 digit level. Note that my denominators for c60 are not precise. If someone can give me exact numbers I will make the change ehre and remove this comment. Finally, numbers marked as resv* have been reserved for GNFS/SNFS and thus no further ECM is required on these numbers. Last fiddled with by garo on 2005-08-01 at 16:56

2005-08-01, 15:38	#2
garo Aug 2002 Termonfeckin, IE 2²×691 Posts	Hence, to find out how much work is required at a given level, check the number in brackets for that level.. If it is greater than 1, no more work is required at that level. If it is less than 1, subtract it from 1 and multiply that figure by the optimal number of ECM6 curves (or Prime95 curves if you are using Prime95 for stage 2). The optimal number of curves required is: Code: digits optimal B1 expected curves expected curves (B2=100B1) (default parameters for ecm-6.0) 20 11,000 84 77 25 50,000 262 206 30 250,000 648 401 35 1,000,000 1,588 948 40 3,000,000 4,716 2,440 45 11,000,000 9,770 4,590 50 43,000,000 18,143 7,771 55 110,000,000 45,841 17,899 60 260,000,000 114,973 43,670 65 850,000,000 193,436 69,351 So continuing with the 12,236+ example, we need (1-0.55)7771=3495 more curves at the 50 digit level with GMP-ECM6.0 (B1=43M, B2=ECM6.0 default). Or (1-0.55)18143 = 8164 more curves with prime95 (B1=43M, B2=4.29G). Last fiddled with by garo on 2005-08-01 at 16:55*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Extensions to Cunningham tables	Raman	Cunningham Tables	87	2012-11-14 11:24
Cunningham Tables at Mersenne Wiki	Raman	Cunningham Tables	32	2012-07-10 22:27
Extended Cunningham tables	Zeta-Flux	Factoring	2	2008-03-03 18:34
New Cunningham Tables forum.	garo	Factoring	1	2006-03-23 22:17
A question about Cunningham tables	T.Rex	Factoring	14	2005-05-27 00:27