20050620, 19:51  #1 
∂^{2}ω=0
Sep 2002
República de California
2^{2}×2,939 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 nextlarger 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 doubleMersenne number M(M31) (where we write factors as q = 2*k*p+1, with p = 2^311) 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 wellknown special form of primeexponent Mersenne factors along with the property q == +1 (modulo 8) (which follows from 2 being a quadratic residue modulo any 2^n1 with odd exponent n) and a smallprime sieve (using primes <= 611957) to eliminate over 90% of the resulting candidate q's. The surviving factor candidates were tested using a fast lefttoright binary powering algorithm and a 96bit Montgomerystyle modmul. ("96bit" 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 highlevel C implementation with small assemblycode macros to calculate 64x64=>128bit 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 GHzdays 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 doubleMersennes is maintained by will Edgington at http://www.garlic.com/~wedgingt/MMPstats.txt . 
20050620, 20:14  #2  
"Sander"
Oct 2002
52.345322,5.52471
29×41 Posts 
Quote:
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? 

20050620, 20:17  #3  
"Nancy"
Aug 2002
Alexandria
4643_{8} Posts 
I dug this out from my old Inbox files (good thing I'm such a data hog!)
Quote:
That is quite a nice find! Alex Last fiddled with by akruppa on 20050621 at 05:39 Reason: typo 

20050620, 20:44  #4  
∂^{2}ω=0
Sep 2002
República de California
2^{2}×2,939 Posts 
Quote:
Re. speed, the above thread mentions that a range of roughly 10^12 k's (= 1T in the terminology of the author) needs 10 GHzdays 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 GHzdays on a p4. I needed just 15 GHzdays (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 machinespecific optimizations for that platform (I only use it for code debugging and basic testing). With some x86specific 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 trialfactoring 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 20050620 at 20:54 

20050620, 22:59  #5 
"Phil"
Sep 2002
Tracktown, U.S.A.
19×59 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. 
20050622, 21:13  #6 
Jan 2003
31 Posts 
>Though I see that the latest version of George Woltman's Prime95 allows
>trialfactoring 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 Last fiddled with by nuutti on 20050622 at 21:14 
20050623, 09:45  #7  
Banned
"Luigi"
Aug 2002
Team Italia
4,861 Posts 
Quote:
Luigi 

20050623, 11:05  #8 
Aug 2002
Termonfeckin, IE
2^{4}·173 Posts 
The latest version does not have that control.

20050623, 12:43  #9  
Banned
"Luigi"
Aug 2002
Team Italia
12FD_{16} Posts 
Quote:
Also, putting the line AdvancedFactor=1999999973,2000000099,50,60 in the worktodo.ini file, The program correctly detects primes above 2,000,000,000. Luigi Last fiddled with by ET_ on 20050623 at 12:49 

20050623, 14:03  #10 
Jan 2003
31_{10} Posts 
I put
Factor=1999999973,76 in worktodo.ini file. 2^311 = 2147483647 does not work. Nuutti 
20050623, 15:39  #11 
P90 years forever!
Aug 2002
Yeehaw, FL
73·113 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 20050623 at 15:42 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Nextgen Odroid announcement  ewmayer  Mlucas  116  20200723 09:24 
Black's twenty fourth move  Raman  Game 1  ♚♛♝♞♜♟  Shaolin Pirates  0  20130326 02:57 
Fourth probable prime found, one to go!  philmoore  Five or Bust  The Dual Sierpinski Problem  22  20100101 00:23 
Subscribing to announcement thread  fetofs  GMPECM  1  20060530 04:32 
Preliminary iMac duocore Intel RESULTS.TXT  SO7783  Software  6  20060415 14:38 