Nice Result! M971

[R.D. Silverman]

In case everyone has not yet heard:

David Symcox factored M971 using Mprime.

This was the smallest Mersenne number with no known factors.
He found a 53 digit factor with ECM and the cofactor was prime.

This again shows that factors remain to be found of 2^n+1 and 2^n-1 for
n < 1200. This is a useful pursuit for those with slower machines who
do not want to wait many months for a single LL test.

See:
http://www.mersenne.org/ecm.htm

Bob

[garo]

OK! So I'm intrigued and want to run some ECM tests on the 2+ Cunningham tables. I have a P4 with wondows and another with linux - both reasonably fast machines. Should I use mprime or gmp-ecm? I am very familiar with mprime/prime95 whereas gmp-ecm would require a bit of learning. Moreover, I understand that on P4s P95/mprime is faster. But is that only that case for number of the form 2^n-1 or also for 2^n+1? The machines have about 200MB of free memory that can be devoted to GMP-ECM. The number I am looking at is 2^1033+1 which hasn't had any ECM done even for the 40 digit level.

[Prime95]

You are probably better off running GMP-ECM

[xilman]

Originally Posted by garo

OK! So I'm intrigued and want to run some ECM tests on the 2+ Cunningham tables. I have a P4 with wondows and another with linux - both reasonably fast machines. Should I use mprime or gmp-ecm? I am very familiar with mprime/prime95 whereas gmp-ecm would require a bit of learning. Moreover, I understand that on P4s P95/mprime is faster. But is that only that case for number of the form 2^n-1 or also for 2^n+1? The machines have about 200MB of free memory that can be devoted to GMP-ECM. The number I am looking at is 2^1033+1 which hasn't had any ECM done even for the 40 digit level.

Personally I'd stick with mprime/prime95 if you want to run ECM on the 2+ and 2- tables, as it tends to be rather faster where it is applicable (i.e. at small values of B2). Note that M_2n = M_n * P_n and under some circumstances George's code is faster at factoring M_2n than p_n. In your case, you would try to factor M2066. It won't take you long to see whether your machine runs faster on that one or on P1033.

Good luck!

Paul

[geoff]

Originally Posted by garo

The number I am looking at is 2^1033+1 which hasn't had any ECM done even for the 40 digit level.

2^1033+1 has been tested to the 40 digit level and has had about 2000 curves done at the 45 digit level. This is an interesting number to choose, there are many options for testing associated numbers.

2^1033-1 and 2^1033+1 can be tested simultaneously by running curves on 2^2066-1. (on a P4 with Prime95 it is much faster to test 2^2066-1 than 2^1033+1, and so you effectively get to test 2^1033-1 for free).

2^1033-1, 2^1033+1, 2,2066L and 2,2066M (these last two are factors of 2^2066+1, also in the Cunningham tables) can all be tested simultaneously by running curves on 2^4132-1.

All four numbers have reasonably large unfactored parts, all above 250 digits, so while gmp-ecm would be faster than Prime95 on the stage 2 step, it is not as big a difference as for some other numbers. If you wanted to keep things simple and just use Prime95, 2^2066-1 or 2^4132-1 would be good choices I think. All four numbers have had a similar level of ECM effort reported too, i.e. tested to 40 digits.

[akruppa]

Here are other exponents where both 2^n+1 and 2^n-1 are not completely factored:

787, 799, 823, 853, 859, 887, 893, 905, 913, 923, 947, 949, 961, 991, 1001, 1009, 1019, 1021, 1025, 1027, 1033, 1037, 1043, 1051, 1055, 1067, 1079, 1087, 1091, 1105, 1109, 1115, 1123, 1127, 1129, 1133, 1135, 1139, 1147, 1151, 1153, 1157, 1159, 1161, 1163, 1165, 1167, 1175, 1177, 1183, 1187, 1191, 1193

As for using gmp-ecm, the best you can do is try out and take timings. If you have an Athlon sitting somewhere, doing stage 1 with Prime95 on P4 and stage 2 with gmp-ecm on Athlon would be ideal. If you do stage 1 on two (or more) numbers simultaneously, you should split the residue modulo the individual numbers before feeing it to gmp-ecm. It saves both time and memory. The thread http://www.mersenneforum.org/showthread.php?t=2326 has more info.

Alex

[R.D. Silverman]

Originally Posted by geoff

2^1033+1 has been tested to the 40 digit level and has had about 2000 curves done at the 45 digit level. This is an interesting number to choose, there are many options for testing associated numbers.

<snip>

.

Another option, although it would require some learning is to run Mprime
on step 1 and GMP-ECM on step 2. Mprime can output the result of
Step 1. GMP-ECM can accept it for step 2.

[R.D. Silverman]

Originally Posted by akruppa

Here are other exponents where both 2^n+1 and 2^n-1 are not completely factored:

787, 799, 823, 853, 859, 887, 893, 905, 913, 923, 947, 949, 961, 991, 1001, 1009, 1019, 1021, 1025, 1027, 1033, 1037, 1043, 1051, 1055, 1067, 1079, 1087, 1091, 1105, 1109, 1115, 1123, 1127, 1129, 1133, 1135, 1139, 1147, 1151, 1153, 1157, 1159, 1161, 1163, 1165, 1167, 1175, 1177, 1183, 1187, 1191, 1193


<snip>

Alex

Please note that for all these exponents 2^n-1 has been completely
tested through 40 digits, while for the corresponding 2^n+1, many have
not been fully tested at this level.. It would be somewhat wastefull to test both at the 40 digit level.

OTOH, very FEW of these have been fully tested to 45 digits.

Thanks for helping out.

Bob

[akruppa]

I think it's permissible to skip B1=3M for one of the numbers. Even if a ~p40 exists, the expected time to find it with B1=11M is not that much higher than with B1=3M, and the time saved by doing both numbers at once should more than make up for that.

Alex

[garo]

Okay! Looks like I will do stage 1 on 2^4132-1 using Prime95 on a P4 followed by splitting up the residues and feeding them to gmp-ecp on my Athlon machine for stage 2.

Now a few questions:

1) Are there Windows binaries for gmp-ecm on an Athlon?

2) Does anyone keep track of ECM done on LM numbers?

3) Now this may be a very silly question to ask but is there any sense at all in attempting P-1 on 2^4132-1?

4) Can someone give a short two line desciption of what stages 1 and 2 are in ECM. I know what they are in P-1.

Thanks

[Prime95]

Originally Posted by akruppa

As for using gmp-ecm, the best you can do is try out and take timings.

In comparing timings remember that GMP-ECM uses a superior algorithm to get much larger B2 values. This makes one GMP-ECM curve worth about 2 (can someone provide the exact conversion constant) prime95 curves.