mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2004-09-15, 13:29   #1
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default Nice Result! M971

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
R.D. Silverman is offline   Reply With Quote
Old 2004-09-16, 13:50   #2
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

32×307 Posts
Default

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.
garo is offline   Reply With Quote
Old 2004-09-16, 14:13   #3
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

2×3,701 Posts
Default

You are probably better off running GMP-ECM
Prime95 is offline   Reply With Quote
Old 2004-09-16, 14:15   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

24×5×7×19 Posts
Default

Quote:
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
xilman is offline   Reply With Quote
Old 2004-09-16, 14:43   #5
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

Quote:
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.
geoff is offline   Reply With Quote
Old 2004-09-16, 14:54   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2004-09-16, 14:58   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Thumbs up

Quote:
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 is offline   Reply With Quote
Old 2004-09-16, 15:05   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Thumbs up

Quote:
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
R.D. Silverman is offline   Reply With Quote
Old 2004-09-16, 15:21   #9
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2004-09-16, 15:21   #10
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

32×307 Posts
Default

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
garo is offline   Reply With Quote
Old 2004-09-16, 15:22   #11
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

2×3,701 Posts
Default

Quote:
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.
Prime95 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Nice progress! schickel FactorDB 29 2012-07-18 17:03
Nice pic Dubslow Forum Feedback 0 2012-05-02 02:13
Let's do another nice big GNFS job! fivemack Factoring 84 2011-04-26 10:22
M971 factored philmoore Lounge 5 2004-09-14 20:18
Nice link... Xyzzy Lounge 4 2003-06-28 13:37

All times are UTC. The time now is 00:11.

Mon Apr 12 00:11:31 UTC 2021 up 3 days, 18:52, 1 user, load averages: 1.52, 1.38, 1.45

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.