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: Re: Mersenne Primes (in general) Message-ID: <579@linus.UUCP> Date: Wed, 2-Oct-85 09:22:43 EDT Article-I.D.: linus.579 Posted: Wed Oct 2 09:22:43 1985 Date-Received: Fri, 4-Oct-85 03:38:19 EDT References: <359@faron.UUCP> Distribution: net Organization: The MITRE Corporation, Bedford, MA Lines: 42 > 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) Sorry about the typo in the last posting: The proper prime testing sequence should be: 2 x = x - 2 n+1 n My previous posting mistakenly had an exponent 2 on the left hand side. Bob Silverman (they call me Mr. 9) Brought to you by Super Global Mega Corp .com