The best description is in Riesel 94, p 124-129, where both the simple case

mod(k,3)<> 0 and the more complex case where mod(k,3)=0 are desribed.

Torbjorn Alm

Tranholmsvagen 3

SE-178 32 Ekero, Sweden

+46 8 560 307 51

torbjorn.alm@... <mailto:

torbjorn.alm@...>

There are 10 types of people in this world, those who can read binary and

those who can't.

-----Original Message-----

From: Phil Carmody [mailto:

thefatphil@...]

Sent: den 30 december 2002 14:54

To: primenumbers

Subject: Re: [PrimeNumbers] Lucas-Lehmer proofs?

--- "David Broadhurst <

d.broadhurst@...>" <

d.broadhurst@...>

wrote:

> I seem to have a hole in my math.

This should be a FAQ. It gets guys on sci.crypt all the time.

> Where is the reference that a Lucas-Lehmer test

> can prove primality of k*2^n-1,

> as opposed to being merely a Lucas PrP test

> in Q(sqrt(3)) ?

<<<

It is also easy to give a test paralleling Pocklington's theorem using Lucas

sequences. This was first done by D. H. Lehmer in 1930 (in the same article

he introduced the Lucas-Lehmer test: [Lehmer30]). See [BLSTW88] or [BLS75]

or ... for more information on these tests.

>>>

The Lehmer-Pocklington (a la Riesel) tests are frequently refered to as

Lucas-Lehmer tests by peole who don't care for minutiae.

> Help, please!

There's always the source, I guess. Is there anything which looks like a

Pocklington step?

However, I reckon that as finding an element with maximal order is

non-deterministic, it ought to be able to provoke a Pocklington test into

having different running times for different numbers. And given that only

one prime factor, 2, is being considered, the running times should be

integer

multiples of a LPRP test time.

Does that make sense?

If so, every number runs in the same time, I'd _guess_ that this is a SLPRP

test, and David's diagnosis is realised.

Phil

=====

The answer to life's mystery is simple and direct:

Sex and death. -- Ian 'Lemmy' Kilminster

__________________________________________________

Do you Yahoo!?

Yahoo! Mail Plus - Powerful. Affordable. Sign up now.

http://mailplus.yahoo.com
Unsubscribe by an email to:

primenumbers-unsubscribe@yahoogroups.com
The Prime Pages :

http://www.primepages.org/
Your use of Yahoo! Groups is subject to

http://docs.yahoo.com/info/terms/