M1061...

[thomasn]

Time for a summary :

Name		Curves		Multiplier		B2		Message No		Line total		
Wolf		200		1		4290000000		#109		200		
Jhansen		100		2,16		184367799127		#108		216		
Frmky		100		2,16		184367799127		#105		216		
Xyzzy		275		2,12		178426462988		#104		583		
Thomasn		400		1		4290000000		#91		400		
												
Thomasn		200		1		4290000000		#106		200		
Thomasn		200		1		4290000000		#103		200		
Geoff		275		1,32		1,50E+010		#102		363		
							
												
Grand total			2378

After this update, only 2432 curves remain!

The usual drill : please have a look at the list above, and if your contribution is not correct, or left out, say so. I will mail George in a day or two.

Thomas

[thomasn]

Another matter :
Do we count curves with B1 = 11e7 towards the total for 50 digit factors?

I have previously not done so, but found that I might be mistaken.

If we do : what is the multiplier(s) ?

Thomas

[marc]

Nope. 11e7 is the next level - 55bits. After we finish this level we move on to 55 which I don't think prime95 can manage.

I haven't had my regular computer for a while so I haven't done any work but what does everyone want to do after we finish 50bits? We could either move onto the next exponent or continue on to the next level. A curve for 11e7 takes a lot longer than 44e6 and we'd need far more curves to complete that depth whereas moving on would leave M1061 unfactored, which I would find mildly irritating.

[JHansen]

Hi all!

I think you should continue. This way there is a chance of finding a record factor with the ECM method. However, when going to the 55 digit level GMP-ECM should be used.

From the README of GMP-ECM:

digits D  optimal B1      B2        expected curves N(B1,B2,D)
 55        11e7          6.8e11           22000

-----
Cheers,
Jes

[xilman]

Originally Posted by marc

Nope. 11e7 is the next level - 55bits. After we finish this level we move on to 55 which I don't think prime95 can manage.

I haven't had my regular computer for a while so I haven't done any work but what does everyone want to do after we finish 50bits? We could either move onto the next exponent or continue on to the next level. A curve for 11e7 takes a lot longer than 44e6 and we'd need far more curves to complete that depth whereas moving on would leave M1061 unfactored, which I would find mildly irritating.

First, not moving on could also leave M1061 unfactored. If the smallest factor has 90 digits, say, it is very unlikely that it will be found by ECM.

Secondly, if M1061 isn't factored by ECM, the only plausible alternative approach at the moment is to use SNFS. That would be a major undertaking with today's technology, to put it mildly. Before we'd even consider factoring it by SNFS we would want to be reasonably sure that there are no small factors. I haven't worked out the figures, but gut feeling is that we'd want it run to at least 55 digits and possibly 60 before starting.

As I'm not personally running ECM on M1061 I won't make a recommendation either way. However, the material above may help others to make their decisions.


Paul

[geoff]

I think we should continue to the 55 digit level. Finding a 55 digit factor of the smallest unfactored mersenne would be much more interesting than finding a 50 digit factor of the second smallest unfactored mersenne.

If anyone wants to do just the stage one step at this level, then I could finish the stage two step for them.

[Xyzzy]

I've switched to the 55 digit level so others can continue to use Prime95/Mprime on the 50 digit stuff...

I think we should at least finish up the 55 digit level... 22k curves sounds like a lot, but I bet a few of us can finish it up in a few months...

I haven't been keeping track of the 55 digit stuff I've posted, but hopefully thomasn will continue to keep stats for us!

[R.D. Silverman]

Originally Posted by geoff

I think we should continue to the 55 digit level. Finding a 55 digit factor of the smallest unfactored mersenne would be much more interesting than finding a 50 digit factor of the second smallest unfactored mersenne.

If anyone wants to do just the stage one step at this level, then I could finish the stage two step for them.

A "back of the envelope" conditional probability calculation [see my ECM
analysis paper] suggests that given the ECM failure at the 50 digit level,
there is only a 10 to 15% chance of succeeding at the 55 digit level.
[also taking into account the a priori distribution via Dickman's function;
This gives a prior, ECM failure gives a sample, so we can compute a
posterior via Bayes' Thm].

This matches my instinct based on my [18 years] experience with ECM.
If you fail, increasing the search bounds to 5 more digits doesn't succeed
that often.

I think it better to move on. Rather than focus on just one number, there
is a reasonable chance that if we test a bunch of numbers to the 50 digit
level, we can find a 60 digit factor somewhere along the way.

Leave M1061 until SNFS is able to handle it. My paper also shows a method
to determine how long to run ECM before switching to SNFS in order to
minimize the expected time to succeed. I no longer have software
that would let me do the calculations. I *guess* that the 50 digit level
is about where one should switch.

Besides, I think M1061 would make a good candidate for the first number
done with SNFS of over 1024 bits. R311 is a competing candidate.
I don't agree that finding a 55 digit factor of M1061 would be all that
interesting. We have found a few 55 digit factors. I would much rather hope
that M1061 has 2 factors OVER 150 digits. It would be a much "prettier"
result. I would rather find 10 factors of 2^n +/- 1 in the 45-50 digit range
than a single 55 to 60 digit factor of M1061. But that is just my preference.

Many of the 2+ numbers have not even been tested at all (or very little)
at the 45 digit level.

[geoff]

These are the times for 55 digit curves at various B2 bounds on my 2.9GHz P4 (mprime 23.9, gmp-ecm 5.0.3):

Stage one with B1=110e6: mprime 1368 sec. (gmp-ecm 4010 sec.)

 B2/Poly   Step 2   memory    total    eqv. std  time per
            time     used     time     curves    std curve

 11e9/12:   212s      66M     1580s     0.443     3567s
 22e9/12:   338s      95M     1706s     0.511     3339s
 30e9/12:   440s     112M     1808s     0.550     3287s*
 43e9/30:   661s     128M     2029s     0.610     3326s
 62e9/30:   816s     159M     2184s     0.654     3339s
 86e9/30:  1063s     191M     2431s     0.700     3472s
170e9/30:  1614s     264M     2982s     0.792     3765s
340e9/30:  2550s     381M     3918s     0.889     4407s
680e9/30:  3978s     538M     5346s     1.000     5346s

Using B2=30e9 would need 6.65 P4 GHz years of effort to complete the 55 digit level.

I still think it is worthwhile putting some effort into this, but perhaps we should work out the effort needed to complete some other projects for a comparison.

This is about the same effort needed to complete 27 GIMPS 10 million digit LL tests.

[biwema]

I think the limits are not so clear.
It is also possible to find big factors with smaller bounds. Many of the largest ecm factors were found with b1=3M or B1=11M.

I it is also possible to continue with prime95 for 55 digit factors. If the weight is correct, we can count some (say about 3) 44M/4.29G curves as one 110M/11G curve or similar.

another possibility is to distribute the intermediate results. One person starts a bunch p95 curves and someone else finishes the intermediate file with GMP.

[geoff]

I worked out the times and weights for 55 digit curves done with mprime only:

 B1      B2     weight   S1    S2   Total  Time/std
                                    time    curve

44e6   4.29e9   0.166    544   247   791    4765
11e7   4.29e9   0.352   1368   247  1615    4588

On a P4 at least it is better to do the full stage 1 step to B1=11e7 even when stage 2 is restricted to 4.29e9. Using gmp-ecm for stage two is even better of course.