FW: [PrimeNumbers] Lucas-Lehmer proofs?
- 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.
SE-178 32 Ekero, Sweden
+46 8 560 307 51
There are 10 types of people in this world, those who can read binary and
those who can't.
From: Phil Carmody [mailto:thefatphil@...]
Sent: den 30 december 2002 14:54
Subject: Re: [PrimeNumbers] Lucas-Lehmer proofs?
--- "David Broadhurst <d.broadhurst@...>" <d.broadhurst@...>
> 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
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
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.
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.
Unsubscribe by an email to: email@example.com
The Prime Pages : http://www.primepages.org/
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/