From: [EMAIL PROTECTED]
Date sent: Mon, 15 Mar 1999 23:32:30 EST
To: [EMAIL PROTECTED]
Subject: Mersenne: LL testing
> I'm curious, as to the nature of the proof that the LL test can definitively
> prove/disprove the primality of a Mersenne number. The resources I have are
> limited and don't go into depth. Before I search elsewhere, I was wondering if
> anyone on the list could help me:
>
> What were the original details of Lucas' test? And how did Lehmer modify it
> into its current form (at least I know how to perform the LL test in its
> current state).
>
> What are the details of the proof that Lucas' test definitively (dis)proves
> the primality of a Mersenne number? Does the proof change for the Lucas-Lehmer
> test?
Suggest you look at the following references, which I just found by
following links from Chris Caldwell's Web site.
J. W. Bruce, "A really trivial proof of the Lucas-Lehmer test," Amer.
Math. Monthly, April (1993) 370-371. (Proves sufficiency only. See
also M. I. Rosen "A proof of the Lucas-Lehmer test," Amer.
Math. Monthly, 95 (1988) 855-856.)
>
> In the LL test, we start with S(1) = 4. The Prime Page says we can use S(1) =
> 10 and certain other values depending on p. Can anyone clarify this?
Yes, there are a whole list of other starting values for which the LL
Test is valid. However, this don't really assist us a lot. The problem
is that, although the final residual will be zero if the tested number
is prime whichever of the starting values is used, if the number is
composite, the final residual will vary depending on the starting
value (but can't be zero). This makes cross-checking of results
difficult.
>
> To prove that M(127) (Or M127, whichever refers to 2^127 - 1, not the 127th
> Mersenne prime) is prime, did Lucas use his test by hand? I know he did it by
> hand, at the very least.
Very probably. Lucas was working in the time before efficient
calculating machines were in common usage (at any rate, in the
West; the Russians, Chinese and Japanese were using their
different varieties of abacus); Babbage's Difference Engine was
unique, specialised to its task and limited to 20 digits precision, so
would have been of little or no use to Lucas.
My interest in Mersenne primes dates back to a winter afternoon in
early 1965 when, incarcerated in the school library (sports were
abandoned due to the poor weather) I read about the LL Test
somewhere and decided to verify a few (very small) exponents. By
hand, I realised that neither a slide rule nor log tables would be any
help - and *no* schools even dreamt of posessing an electronic
computer!. Aged nearly 12, I was able to complete the verification
of M(31) i.e. 2^31-1 in about 80 minutes. I'm sure my arithmetic
has degenerated to the point where I couldn't possibly repeat the
exercise, but, it does show that hand-calculating the LL Test on
M(127) would be feasible (using "classical" techniques - long
multiplication etc - it would take approx. (127/31)^3 = 70 times as
long to LL test M(127) as M(31)). Tedious but definitely possible.
The fact that you, a $1000 computer and a suitably optimized
program could now do the test in a millisecond or two is irrelevant.
>
> Thanks. Please reply to the list, as if you have an Internet E-mail address,
> my software will auto-block you. AOL members need not worry.
> S.T.L.
Hmm. I prefer to send replies of specific interest to the enquirer
only. I guess there are some other people on the list who might be
interested enough to justify this broadcast?
Suggestion, would you consider changing your filter rules to let
through messages whose subject header contains the key word
"mersenne" irrespective of origin? I doubt many "spammers" would
deliberately change their message format to sneak by that rule.
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
