Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.2 9/18/84; site linus.UUCP Path: utzoo!linus!bs From: bs@linus.UUCP (Robert D. Silverman) Newsgroups: net.math Subject: Mersenne Primes Message-ID: <576@linus.UUCP> Date: Mon, 30-Sep-85 08:09:37 EDT Article-I.D.: linus.576 Posted: Mon Sep 30 08:09:37 1985 Date-Received: Wed, 2-Oct-85 10:08:09 EDT Distribution: net Organization: The MITRE Corporation, Bedford, MA Lines: 29 The exponents for the thirty known Mersenne primes are: 1,2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,9941,11213, 19937,21701,23209,44497,86243,132049,216091 A number of the form 2^p - 1 is prime iff its rank of apparition in the sequence: 2 2 x = x - 2 n+1 n Is p-2 where x = 4. 0 That is to say 2^p -1 is prime iff the p-2 term in the above sequence is divisible by 2^p-1. Thus, to do the prime test one need only compute the sequence mod 2^p - 1 and see if the p-2 term is zero. One can compute the sequence with just multiplication and addition by noting that: n n n 2 A + B = (2 - 1)A + B + A = B + A mod (2 - 1) One 'merely' needs a very fast routine which will multiply 65,000 digit numbers. I believe that Mr. Slowinski, who found the prime, uses some sort of fast fourier transform multiplication routine. Bob Silverman (they call me Mr.9) Brought to you by Super Global Mega Corp .com