> 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:
Go to Luke's Mersenne bibliography page at
http://www.scruznet.com/~luke/biblio.htm
You will find an article by Edouard Lucas at
http://www.scruznet.com/~luke/lit/lit_068s.htm
and Lehmer's article "On Lucas's Test for the Primality of Mersenne's
numbers" at http://www.scruznet.com/~luke/lit/lit_007s.htm
> 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).
In summary Lucas gave two theorems for 2^(4k+/-1)-1. For N = 2^(4q+1)-1
use the familiar sequence 4, 14, 194, .... For N = 2^(4q+3)-1 use the
sequence 3, 7, 47, ..., which is correct. See R.E.Powers announcements of
primality of M89 (Lucas incorrectly gave it as composite) at
http://www.scruznet.com/~luke/lit/lit_002.txt and for M107 at
http://www.scruznet.com/~luke/lit/lit_003s.htm. For M89 Powers uses the
sequence 4, 14, 194, ... and for M107 he uses 3, 7, 47, ....
In Lehmer's paper he states that the sequence 4, 14, 194, ... can be
used for both cases. There is some question if Lucas' proof is complete,
Lehmer gives both a sufficient and necessary proof of the Lucas test.
> 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?
For starting values we can use 4, 52, 724, ..., U{n}, ..., where U{n} =
14 U{n-1} - u{n-2} and 10, 970, 95050, ..., V{n}, ..., where V{n} = 98
V{n-1} - V{n-2}. Also there are 2^(p-2) starting values that depend upon
p. For example to test 2^5-1 we could use the starting values 4, 9, 10,
11, 20, 21, 22, or 27.
Also see my post to the list in the (defunct) mail archives
http://www2.netdoor.com/~acurry/mersenne/archive3/0679.html
> To prove that M(127) (Or M127, whichever refers to 2^127 - 1, not the 127th
> Mersenne prime) is prime,
M(p) is usually the pth Mersenne number and Mp is 2^p-1 in the
literature. Though occasionally M(p) is used as 2^p-1 on the list. It
could cause confusion only for small p. Is M(3) 2^3-1 or 2^5-1?
> did Lucas use his test by hand? I know he did it by
> hand, at the very least.
I don't know about Lucas. Read some of the articles in Luke's
bibliography, it is a wonderful history. Lehmer and Uhler used desk
calculators. Uhler made many calculations of logarithms and powers,
see for example http://www.scruznet.com/~luke/lit/lit_019.htm
Though poor Uhler had been doing LL-tests in the gap between M127 and
M521.
> I posted a message on sci.math a while ago. The response was deafening. If
> anyone on the list would like to add to the voluminous (har har har) response
> I've received, I'd be grateful. It can be found at:
> http://www.dejanews.com/getdoc.xp?AN=450576076
> I don't wish to add to the size of the list digest unduly.
STL137 asks in his post if there is a test similiar to the LL test for
numbers of the form 2^N-k where k=3,5,7,.... A primality test of the
Lucasian type depends on the factorization of N+1, so I guess not.
However, for some k*2^N-1 there is a primality test that uses the familiar
S{n} = S{n-1}^2-2 differing only in the starting value S{0}. See
Riesel, "Prime Numbers and Computer Methods of Factorization" for example.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
