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

Re: [PrimeNumbers] Lucas-Lehmer proofs?

Expand Messages
  • David Broadhurst <d.broadhurst@open.ac.u
    ... It s just that I was born with a suspicious mind. However, it does appear that the code L2 issued by Chris Caldwell needs clarification. It may be that it
    Message 1 of 17 , Dec 30, 2002
    • 0 Attachment
      > It does look like it does what it says on the tin,
      > and that's a LL test.
      > And your diagnosis, and assumed prognosis,
      > seems correct David.
      > If so, very astutely spotted.
      It's just that I was born with a suspicious mind.
      However, it does appear that the code L2
      issued by Chris Caldwell needs clarification.
      It may be that it is "faster than Nash and Gallot"
      in issuing certificates because those
      certificates are not proofs?
      I see that Jean Penne' has just joined us.
      Maybe he can clear this up for us?
      David
    • jpyah2001 <j_penne@club-internet.fr>
      ... You are right ! The pure Lucas Lehmer algorithm works only for k == 1 ! The LLR program implements a slightly more complex one ; I named it Lucas Lehmer
      Message 2 of 17 , Dec 30, 2002
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, "David Broadhurst
        <d.broadhurst@o...>" <d.broadhurst@o...> wrote:
        > I seem to have a hole in my math.
        >
        > 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)) ?
        >
        > Crandall-Pomerance Theorem 4.2.6 is
        > fine for the Mersennes, at k=1.
        >
        > But how were these
        >
        > 9999 889133*2^105000-1 31615 L2 02 #20021229070941
        > 9999 351369*2^105000-1 31614 L2 02 #20021229070941
        > 9999 729957*2^105000-1 31615 L2 02 #20021229070941
        > 9999 129243*2^105000-1 31614 L2 02 #20021229070941
        > 9999 213597*2^105000-1 31614 L2 02 #20021229070941
        > 9999 831969*2^105000-1 31615 L2 02 #20021229070941
        > 9999 702777*2^105000-1 31614 L2 02 #20021229070941
        > 9999 469257*2^105000-1 31614 L2 02 #20021229070941
        > 9999 890307*2^105000-1 31615 L2 02 #20021229070941
        > 9999 565155*2^105000-1 31614 L2 02 #20021229070941
        >
        > proven by Jean Penné using a Lucas-Lehmer test?
        >

        You are right ! The pure Lucas Lehmer algorithm works only
        for k == 1 ! The LLR program implements a slightly more complex
        one ; I named it "Lucas Lehmer Riesel" because the reference
        were I found it is a paper by Hans Riesel :

        "Lucasian Criteria for the Primality of N=h*2^n-1"
        Mathematics of Computation, Vol. 23 #108, pp. 869-875, Oct. 1969

        The whole theory is explained in this paper.

        Indeed, if you submit a Mersenne number to LLR, it proves
        it primality with the Lucas Lehmer algorithm, but in this
        case, mprime or prime95 are much faster, due to half smallest
        FFT length, and free modular reduction...
        I hope these details will help you!

        > Please excuse me if my ignorance is showing.
        >
        > Help, please!
        >
        > David Broadhurst
      • David Broadhurst <d.broadhurst@open.ac.u
        ... Thanks Jean. I ll have to wait until I m back at work to read that. Sorry to raise doubts! David
        Message 3 of 17 , Dec 30, 2002
        • 0 Attachment
          > "Lucasian Criteria for the Primality of N=h*2^n-1"
          > Mathematics of Computation, Vol. 23 #108, pp. 869-875, Oct. 1969
          Thanks Jean. I'll have to wait until I'm back at work to read that.
          Sorry to raise doubts!
          David
        • Phil Carmody
          ... Riesel cites himself[1969] and Bosma[1993] in PNaCMfF 2nd Ed, I m using Riesel, not C&P, as my reference. Torbjorn s pointer is the right one. Maybe the
          Message 4 of 17 , Dec 30, 2002
          • 0 Attachment
            --- "David Broadhurst <d.broadhurst@...>" <d.broadhurst@...> wrote:
            > > "Lucasian Criteria for the Primality of N=h*2^n-1"
            > > Mathematics of Computation, Vol. 23 #108, pp. 869-875, Oct. 1969
            > Thanks Jean. I'll have to wait until I'm back at work to read that.
            > Sorry to raise doubts!

            Riesel cites himself[1969] and Bosma[1993] in PNaCMfF 2nd Ed, I'm using
            Riesel, not C&P, as my reference. Torbjorn's pointer is the right one.
            Maybe the first edition predates Bosma, but both versions postdate his own
            1969 paper.

            In the section 'Primality Tests for Integers of the Form N=h.2^n-1, when
            3!|h', the first sentence is
            "In order to satisfy (4.76) we need as usual to require that (D/N)=-1."

            Nowhere after that is that (D|N)=-1 condition removed.
            The examples that Riesel himself give have the following
            kronecker(12,p)
            5*2^14-1 -1
            5*2^248-1 -1
            7*2^177-1 -1
            11*2^246-1 -1
            17*2^150-1 -1
            So he doesn't appear to have relaxed he (D|N) condition.

            Furthermore, in the following section, 'Primality Tests for N=h.2^n-1, when
            3|h', he does say
            "...
            so that it is impossible to find a value of D that is a quadratic non-residue
            ..."

            So (D|N) does still seem vital, and -1 at that.

            Are we men or mice - why aren't we looking for pseudoprimes? Reading and
            number-crunching can take place in parallel, surely!

            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
          • Shane <TTcreation@aol.com>
            Is there a status on the primes N= k*2^p -1, that use a mersenne prime exponent p? ie, Is 79 13466917 Prime or composite ? I am sieving and testing small
            Message 5 of 17 , Dec 30, 2002
            • 0 Attachment
              Is there a status on the primes N= k*2^p -1, that use a mersenne
              prime exponent p? ie, Is 79 13466917 Prime or composite ?
              I am sieving and testing small k=1-100, but I want to test only
              unknown N, any help is appreciated as always.




              This would make for a great collaborative effort, much like that of
              GIMPS! Is there a name for this form?
              Shane F.
            • jpyah2001 <j_penne@club-internet.fr>
              ... For the numbers of this form, p needs not to be prime for N beeing prime (unlike Mersenne primes !). I don t know if p beeing a Mersenne prime exponent
              Message 6 of 17 , Dec 31, 2002
              • 0 Attachment
                --- In primenumbers@yahoogroups.com, "Shane <TTcreation@a...>"
                <TTcreation@a...> wrote:
                >
                > Is there a status on the primes N= k*2^p -1, that use a mersenne
                > prime exponent p? ie, Is 79 13466917 Prime or composite ?
                > I am sieving and testing small k=1-100, but I want to test only
                > unknown N, any help is appreciated as always.
                >
                >
                >

                For the numbers of this form, p needs not to be prime for N
                beeing prime (unlike Mersenne primes !). I don't know if p
                beeing a Mersenne prime exponent increases the probability
                for N to be prime (in fact, I don't believe that)...

                >
                > This would make for a great collaborative effort, much like that of
                > GIMPS! Is there a name for this form?

                Yes, indeed, and the presieving using programs such as NewPgen
                is essential, to reduce the number of "big tests" you have to do.

                I don't know if this form has an official name (I know only that
                k*2^n+1 primes are called Robinson primes). Riesel primes would
                be fair, if not already used for other numbers.

                Jean Penné
              • David Broadhurst <d.broadhurst@open.ac.u
                ... I read that, thanks. Riesel frankly admits The only thing to do is to try different values of D and later Bosma seemed to arrive at the same conclusion.
                Message 7 of 17 , Jan 6, 2003
                • 0 Attachment
                  Jean:

                  > "Lucasian Criteria for the Primality of N=h*2^n-1"
                  > Mathematics of Computation, Vol. 23 #108, pp. 869-875, Oct. 1969

                  I read that, thanks. Riesel frankly admits
                  "The only thing to do is to try different values of D"
                  and later Bosma seemed to arrive at the same conclusion.

                  So I guess you programmed some such trial-and-error method,
                  which is in any case very cheap. I also guess that
                  your proof is about twice as fast as PFGW,
                  since you have only a Lucasian squaring to do for the
                  Riesel form k*2^n-1, while a pfgw -tp proof,
                  being written for *much* more general purposes,
                  does twice as much work, in the corresponding
                  quadratic number field.

                  Hope I have it right now. Nice work by you!

                  David
                • Phil Carmody
                  ... With source available, there s no need to guess. Marcel kindly poited out to me where theclever D-finding is, it s in riesel.c, IIRC, which Is why I missed
                  Message 8 of 17 , Jan 6, 2003
                  • 0 Attachment
                    --- "David Broadhurst <d.broadhurst@...>" <d.broadhurst@...> wrote:
                    > Jean:
                    >
                    > > "Lucasian Criteria for the Primality of N=h*2^n-1"
                    > > Mathematics of Computation, Vol. 23 #108, pp. 869-875, Oct. 1969
                    >
                    > I read that, thanks. Riesel frankly admits
                    > "The only thing to do is to try different values of D"
                    > and later Bosma seemed to arrive at the same conclusion.
                    >
                    > So I guess you programmed some such trial-and-error method,

                    With source available, there's no need to guess. Marcel kindly poited out to
                    me where theclever D-finding is, it's in riesel.c, IIRC, which Is why I
                    missed it while initially looking at the main loop. The comments are quite
                    fun - it is trial and error, but thus far no number hasn't been satisfiable,
                    it appears.

                    > which is in any case very cheap. I also guess that
                    > your proof is about twice as fast as PFGW,
                    > since you have only a Lucasian squaring to do for the
                    > Riesel form k*2^n-1, while a pfgw -tp proof,
                    > being written for *much* more general purposes,
                    > does twice as much work, in the corresponding
                    > quadratic number field.

                    It's clever, isn't it?

                    > Hope I have it right now. Nice work by you!

                    Indeed.

                    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
                  • jpyah2001 <j_penne@club-internet.fr>
                    Hi David, ... Yes, I use the tables made by Hans Riesel ; Until now, it has always succeeded to find a value for v1, but I think I am a little lucky ! So, I am
                    Message 9 of 17 , Jan 6, 2003
                    • 0 Attachment
                      Hi David,

                      > So I guess you programmed some such trial-and-error method,
                      > which is in any case very cheap.

                      Yes, I use the tables made by Hans Riesel ; Until now, it has
                      always succeeded to find a value for v1, but I think I am
                      a little lucky !
                      So, I am working to improve the gen_v1 function, avoiding
                      to use tables.
                      Nevertheless, I can prove that the v1 finding can always
                      fail :
                      For the first condition (D/N) == -1, Riesel shows that D must
                      not divide 2*h, so, given a finite set of D's, if I choose
                      a common multiple of these D's as the value of k, none of
                      these D will be good !

                      I also guess that
                      > your proof is about twice as fast as PFGW,
                      > since you have only a Lucasian squaring to do for the
                      > Riesel form k*2^n-1, while a pfgw -tp proof,
                      > being written for *much* more general purposes,
                      > does twice as much work, in the corresponding
                      > quadratic number field.

                      It is possible, but I did not make a benchmark comparison
                      recently.

                      >
                      > Hope I have it right now. Nice work by you!

                      Yes, you are right, and thank you for your remarks.

                      Regards,
                      Jean
                    Your message has been successfully submitted and would be delivered to recipients shortly.