mersenneforum.org Fourth known factor of M(M31) (preliminary announcement)
 Register FAQ Search Today's Posts Mark Forums Read

 2005-06-20, 19:51 #1 ewmayer ∂2ω=0     Sep 2002 República de California 2×13×443 Posts Fourth known factor of M(M31) (preliminary announcement) I plan on sending the following note on a new factor of M(M31) to the Number Theory mailing list shortly, but first am waiting for a few small clarifications re. the three smaller previously known factors. Will Edgington's webpage (referenced in the note) lists Roonguthai next to Haworth's name for the smallest known factor, and Forbes' next to Keller's for the next-larger factor. I seem to recall Warut (Roonguthai) and Tony (Forbes) later independently rediscovering each of these factors - Will and Tony, is this correct? Also, does anyone know whether Keiser used his or someone else's code to discover 242557615644693265201 as a factor? Thanks, -Ernst =================== The following three factors of the double-Mersenne number M(M31) (where we write factors as q = 2*k*p+1, with p = 2^31-1) were previously known: 295257526626031 # k = 68745 (Guy Haworth 1983) 87054709261955177 # k = 20269004 (Wilfrid Keller 1994) 242557615644693265201 # k = 56474845800 (Reto Keiser 1999) To the best of my knowledge, the following was not: 178021379228511215367151 # k = 41448832329225 . This was found on the afternoon of 19 June 2005 using a sieving program of my own writing. The code uses the above well-known special form of prime-exponent Mersenne factors along with the property q == +-1 (modulo 8) (which follows from 2 being a quadratic residue modulo any 2^n-1 with odd exponent n) and a small-prime sieve (using primes <= 611957) to eliminate over 90% of the resulting candidate q's. The surviving factor candidates were tested using a fast left-to-right binary powering algorithm and a 96-bit Montgomery-style modmul. ("96-bit" means that we first calculate an inverse of each q modulo 2^96, and intermediate products are as large as 192 bits. Note that in my implementation, I actually found it more convenient to calculate the inverse power 2^(-p) modulo each candidate q via the Montgomery modmul.) The sieving code used a high-level C implementation with small assembly-code macros to calculate 64x64=>128-bit unsigned integer products on processors with hardware support for same. Running in parallel on a mix of Alpha ev6 and Itanium processors, the new factor was discovered after roughly 15 GHz-days of total processing time had elapsed and 2*10^12 factor candidates tested (which works out to roughly 1000 CPU cycles to test each candidate q). By way of reference, a webpage on the current factorization status of double-Mersennes is maintained by will Edgington at http://www.garlic.com/~wedgingt/MMPstats.txt .
2005-06-20, 20:14   #2
smh

"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts

Quote:
 Also, does anyone know whether Keiser used his or someone else's code to discover 242557615644693265201 as a factor?
IIRC, Reto used Tony's program. I can't find his anouncement right now. I guess he can answer himself. He frequently hangs around here.

How does your program compare (speed) to tony's? Or is it hard to say since it doen't run on x86?

2005-06-20, 20:17   #3
akruppa

"Nancy"
Aug 2002
Alexandria

246710 Posts

I dug this out from my old Inbox files (good thing I'm such a data hog!)

Quote:
 Date: Wed, 08 Dec 1999 11:35:45 +0100 From: Reto Keiser To: mersenne@base.com Subject: Mersenne: new (third) facotor of M(M(31)) hi all i've found a new factor of M(M(31)) using Mfac 2.27. i am not absolutely sure if it was already found by someone else, but with regard to Will Edgingtons list, the factor isn't found yet. The factor is 242557615644693265201 ( 2*k*M31 +1 ) using a k of 56474845800 ( 112949691600 ( 2*k in Mfac )) cheers Reto
Congratulations, Ernst!
That is quite a nice find!

Alex

Last fiddled with by akruppa on 2005-06-21 at 05:39 Reason: typo

2005-06-20, 20:44   #4
ewmayer
2ω=0

Sep 2002
República de California

2CFE16 Posts

Quote:
 Originally Posted by smh IIRC, Reto used Tony's program. I can't find his anouncement right now. I guess he can answer himself. He frequently hangs around here. This is a thread about MM31 he started last year: http://www.mersenneforum.org/showthread.php?t=2999 How does your program compare (speed) to tony's? Or is it hard to say since it doen't run on x86?
Thanks for the link, SMH - I wasn't aware of that thread - have sent a brief note (and link to this thread) to it, and also to Reto (a.k.a. Biwema). Alex, thanks for the e-mail copy - so credit for 242557615644693265201 should go to "Keiser & Forbes (1999)."

Re. speed, the above thread mentions that a range of roughly 10^12 k's (= 1T in the terminology of the author) needs 10 GHz-days on a p4. (Around 2/3 that much on an Athlon) using Tony's MFAC program. The factor I found yesterday has k = 41448832329225 (~40T), which translates to 400 GHz-days on a p4. I needed just 15 GHz-days (slightly less than one calendar day, running on 16 processors at once) on a mix of Alpha/Itanium. However, my code is at least 30x slower clock for clock on x86 since I've done zero machine-specific optimizations for that platform (I only use it for code debugging and basic testing). With some x86-specific optimizations (mainly to use the FPU to help speed the integer MULs) I expect it could be speeded up by an order of magnitude on that platform, but for now MFAC is still the program of choice for x86 users. (Though I see that the latest version of George Woltman's Prime95 allows trial-factoring exponents as large as "2 billion" - if that means up to 2^31, it could be used as well for M(M31) - I expect it would be much faster than MFAC.)

Last fiddled with by ewmayer on 2005-06-20 at 20:54

 2005-06-20, 22:59 #5 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 1,117 Posts Congratulations, Ernst - a very nice find! Your program is very fast indeed. I have run Leonid Durman's fermat.exe on my 1300 MHz Athlon and near the size of F31, it takes about a day to do a range of 1x10^12. I find it intriguing that there are now 12 known factors of MM13, MM17, MM19, and MM31, but not a single known factor for any of the larger iterated Mersennes. I would think that at least one of MM61, MM89, MM107, and MM127 should have a factor within our reach.
 2005-06-22, 21:13 #6 nuutti   Jan 2003 31 Posts >Though I see that the latest version of George Woltman's Prime95 allows >trial-factoring exponents as large as "2 billion" - if that means up to 2^31, it >could be used as well for M(M31) - I expect it would be much faster than >MFAC.) I tested prime95 little and it is able to factor only up to 2 billion. No more. Screenshot included. Yours, Nuutti Attached Thumbnails   Last fiddled with by nuutti on 2005-06-22 at 21:14
2005-06-23, 09:45   #7
ET_
Banned

"Luigi"
Aug 2002
Team Italia

10010100111102 Posts

Quote:
 Originally Posted by nuutti >Though I see that the latest version of George Woltman's Prime95 allows >trial-factoring exponents as large as "2 billion" - if that means up to 2^31, it >could be used as well for M(M31) - I expect it would be much faster than >MFAC.) I tested prime95 little and it is able to factor only up to 2 billion. No more. Yours, Nuutti
How did you bypass the control that fixes exponents to test to 79,300,000? :surprised

Luigi

 2005-06-23, 11:05 #8 garo     Aug 2002 Termonfeckin, IE 5·19·29 Posts The latest version does not have that control.
2005-06-23, 12:43   #9
ET_
Banned

"Luigi"
Aug 2002
Team Italia

2×2,383 Posts

Quote:
 Originally Posted by garo The latest version does not have that control.
I have 24.12 rc2 of June 21st 2005. It still does...at least for Test, P-1 and ECM from Advanced Menu. It works fine adding the line "Factor=xxxxxxx,yy" to the worktodo.ini file.

Also, putting the line

in the worktodo.ini file, The program correctly detects primes above 2,000,000,000.

Luigi

Last fiddled with by ET_ on 2005-06-23 at 12:49

 2005-06-23, 14:03 #10 nuutti   Jan 2003 378 Posts I put Factor=1999999973,76 in worktodo.ini file. 2^31-1 = 2147483647 does not work. Nuutti
 2005-06-23, 15:39 #11 Prime95 P90 years forever!     Aug 2002 Yeehaw, FL 22·1,789 Posts You can try "AdvancedFactor=2147483647,2147483647,start_bit_level,end_bit_level". I'd be curious to know if prime95 can find the known factors. Last fiddled with by Prime95 on 2005-06-23 at 15:42

 Similar Threads Thread Thread Starter Forum Replies Last Post ewmayer Mlucas 116 2020-07-23 09:24 Raman Game 1 - ♚♛♝♞♜♟ - Shaolin Pirates 0 2013-03-26 02:57 philmoore Five or Bust - The Dual Sierpinski Problem 22 2010-01-01 00:23 fetofs GMP-ECM 1 2006-05-30 04:32 SO7783 Software 6 2006-04-15 14:38

All times are UTC. The time now is 17:46.

Fri Sep 25 17:46:01 UTC 2020 up 15 days, 14:56, 0 users, load averages: 1.66, 1.51, 1.46