Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] Yet another Lucas-Lehmer like primality test ?

Expand Messages
  • Phil Carmody
    ... Welcome to the list. ... Yes, one that s been used by several before you. ... I m not familiar with it. I suspect that it s not a proven result as a
    Message 1 of 3 , May 5, 2007
    • 0 Attachment
      --- j_chrtn <j_chrtn@...> wrote:
      > Hello,

      Welcome to the list.

      > I recently found the following statements :
      >
      > Let L(k) be the Lucas sequence L(0)=2, L(1)=1, L(k+2) = L(k+1) + L(k)
      >
      > Let M(n, p) = (n+1)^p - n^p for n >= 1 and p prime >= 3 (M(n,p) can
      > be viewed as a generalization of Mersenne's number).

      Yes, one that's been used by several before you.

      > 1/ Let n >= 1 such that n mod 5 is 0, 2 or 4
      > Then :
      >
      > M(n, p) is prime if and only if M(n, p) divides L((n+1)^p) - L(n^p
      > + 1)
      >
      >
      > 2/ Let n >= 1 such that n mod 5 is 1 or 3 and let p prime >= 3 such
      > that p mod 4 is 1
      > Then :
      >
      > M(n, p) is prime if and only if M(n, p) divides L((n+1)^p) - L(n^p
      > + 1)
      >
      >
      > It follows an efficient primality test for M(n, p) just like the well
      > known Lucas-Lehmer test for Mersenne's numbers.
      >
      > I would like your feedback on this. Is it a known result ?

      I'm not familiar with it. I suspect that it's not a proven result as a
      primality test. It might well be a compositeness test (Probable Primality
      test). The way primiality proofs almost always work is that they limit the
      size and form of divisors of the number in question (e.g. if you prove they're
      all greater than the square root of the number, then you're sorted). I don't
      see how satisfying your criterion alone says anything about the size of
      divisors.

      Aside - who is recording these primes, I don't think it's one of Jens' or
      Steven's forms, is it?

      Phil

      () ASCII ribbon campaign () Hopeless ribbon campaign
      /\ against HTML mail /\ against gratuitous bloodshed

      [stolen with permission from Daniel B. Cristofani]

      __________________________________________________
      Do You Yahoo!?
      Tired of spam? Yahoo! Mail has the best spam protection around
      http://mail.yahoo.com
    • j_chrtn
      Hi Phil, ... (k) ... can ... (n^p ... such ... (n^p ... well ... as a ... Primality ... limit the ... prove they re ... sorted). I don t ... size of ... Well,
      Message 2 of 3 , May 5, 2007
      • 0 Attachment
        Hi Phil,

        --- In primenumbers@yahoogroups.com, Phil Carmody <thefatphil@...>
        wrote:
        >
        > --- j_chrtn <j_chrtn@...> wrote:
        > > Hello,
        >
        > Welcome to the list.
        >
        > > I recently found the following statements :
        > >
        > > Let L(k) be the Lucas sequence L(0)=2, L(1)=1, L(k+2) = L(k+1) + L
        (k)
        > >
        > > Let M(n, p) = (n+1)^p - n^p for n >= 1 and p prime >= 3 (M(n,p)
        can
        > > be viewed as a generalization of Mersenne's number).
        >
        > Yes, one that's been used by several before you.
        >
        > > 1/ Let n >= 1 such that n mod 5 is 0, 2 or 4
        > > Then :
        > >
        > > M(n, p) is prime if and only if M(n, p) divides L((n+1)^p) - L
        (n^p
        > > + 1)
        > >
        > >
        > > 2/ Let n >= 1 such that n mod 5 is 1 or 3 and let p prime >= 3
        such
        > > that p mod 4 is 1
        > > Then :
        > >
        > > M(n, p) is prime if and only if M(n, p) divides L((n+1)^p) - L
        (n^p
        > > + 1)
        > >
        > >
        > > It follows an efficient primality test for M(n, p) just like the
        well
        > > known Lucas-Lehmer test for Mersenne's numbers.
        > >
        > > I would like your feedback on this. Is it a known result ?
        >
        > I'm not familiar with it. I suspect that it's not a proven result
        as a
        > primality test. It might well be a compositeness test (Probable
        Primality
        > test). The way primiality proofs almost always work is that they
        limit the
        > size and form of divisors of the number in question (e.g. if you
        prove they're
        > all greater than the square root of the number, then you're
        sorted). I don't
        > see how satisfying your criterion alone says anything about the
        size of
        > divisors.

        Well, you're right: at this time, I have unfortunately not been able
        to prove these assertions. However, as far as I know Lucas-Lehmer
        test is based on the rank of apparition of a given prime P in the
        Fibonacci or Lehmer extension sequences and the relationships between
        these sequences and their companion Lucas or Lehmer extension
        sequences. I suspect that my two statements above may be proved the
        same way ...


        >
        > Aside - who is recording these primes, I don't think it's one of
        Jens' or
        > Steven's forms, is it?

        I don't know if someone officially records this form of primes. I
        just know that we (Mike Oakes, Predrag Minovic, myself and maybe
        other people) have recorded many PRP of this form to Henri Lifchitz
        probable primes page.

        The largest known PRP of this form (which is my current record) is
        10^282493-9^282493.

        J-L.
      Your message has been successfully submitted and would be delivered to recipients shortly.