Fourth known factor of M(M31) (preliminary announcement)

[ewmayer]

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 .

[smh]

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?

[akruppa]

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

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

[ewmayer]

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.)

[philmoore]

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.

[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.
Screenshot included.

Yours,

Nuutti

[ET_]

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

[garo]

The latest version does not have that control.

[ET_]

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

[nuutti]

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

2^31-1 = 2147483647 does not work.


Nuutti

[Prime95]

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.