mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Operazione Doppi Mersennes

Reply
 
Thread Tools
Old 2005-06-20, 19:51   #1
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2×13×443 Posts
Default 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 .
ewmayer is offline   Reply With Quote
Old 2005-06-20, 20:14   #2
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts
Default

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.

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?
smh is offline   Reply With Quote
Old 2005-06-20, 20:17   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

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 <rkeiser@stud.ee.ethz.ch>
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
akruppa is offline   Reply With Quote
Old 2005-06-20, 20:44   #4
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2CFE16 Posts
Default

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
ewmayer is offline   Reply With Quote
Old 2005-06-20, 22:59   #5
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

1,117 Posts
Default

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.
philmoore is offline   Reply With Quote
Old 2005-06-22, 21:13   #6
nuutti
 
Jan 2003

31 Posts
Default

>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
Click image for larger version

Name:	screen.GIF
Views:	596
Size:	4.1 KB
ID:	611  

Last fiddled with by nuutti on 2005-06-22 at 21:14
nuutti is offline   Reply With Quote
Old 2005-06-23, 09:45   #7
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

10010100111102 Posts
Default

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
ET_ is offline   Reply With Quote
Old 2005-06-23, 11:05   #8
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

5·19·29 Posts
Default

The latest version does not have that control.
garo is offline   Reply With Quote
Old 2005-06-23, 12:43   #9
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2×2,383 Posts
Default

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

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 2005-06-23 at 12:49
ET_ is offline   Reply With Quote
Old 2005-06-23, 14:03   #10
nuutti
 
Jan 2003

378 Posts
Default

I put
Factor=1999999973,76
in worktodo.ini file.

2^31-1 = 2147483647 does not work.


Nuutti
nuutti is offline   Reply With Quote
Old 2005-06-23, 15:39   #11
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

22·1,789 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Next-gen Odroid announcement ewmayer Mlucas 116 2020-07-23 09:24
Black's twenty fourth move Raman Game 1 - ♚♛♝♞♜♟ - Shaolin Pirates 0 2013-03-26 02:57
Fourth probable prime found, one to go! philmoore Five or Bust - The Dual Sierpinski Problem 22 2010-01-01 00:23
Subscribing to announcement thread fetofs GMP-ECM 1 2006-05-30 04:32
Preliminary iMac duo-core Intel RESULTS.TXT 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.