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

LLR Version 3.7.0 released

Expand Messages
  • Jean Penné
    Hi All, The new LLR 3.7.0 Version is now available on the GIMPS directory! It contains as a new important feature an efficient primality proving test for the
    Message 1 of 7 , Apr 3 12:09 PM
    • 0 Attachment
      Hi All,

      The new LLR 3.7.0 Version is now available on the GIMPS directory!

      It contains as a new important feature an efficient primality proving
      test for the Gaussian-Mersenne norms.

      Mike Oakes originated this search in the early 1970, and discovered
      most of the above-titanic GM primes presently known (nevertheless, the
      actual record, GM(991961) , has been discovered by Boris Iskra in
      November 2005).
      These numbers may be proven prime by the Proth theorem test, but the k
      multiplier value beeing an exponential function of p, it would
      require using the gwnums in generic mode...
      Following a suggestion by Harsh Aggarwal, I implemented, in the new
      version LLR3.7.0, a much more efficient method :
      The starting point is the Aurifeuillian factorization of M(p) = 4^p+1 :

      M(p) = 4^p+1 = (2^p + 2^((p+1)/2) + 1)(2^p - 2^((p+1)/2) + 1)

      One of these two factors is the norm N(p) of GM(p) = (1±i)^p - 1

      Now, the idea is to run the Proth algorithm, but doing the squarings
      modulo M(p), and then doing the modulo N reduction only on the final
      result. Then, the performances for a given p may be approximatively
      the same as for a Lucas-Lehmer test with exponent 2*p.
      In order to make this prime search really efficient, it is however
      necessary that the prime exponent candidates would be sieved enough by
      prefactoring, so I adapted the George Woltman's "factor32.asm" for
      4^p+1 factoring, and this new code is included in LLR to eliminate the
      candidates having a non trivial factor, before doing the Proth test.
      The factoring upper limit is dependent on the exponent size, and can
      reach 86 bits, as for GIMPS.
      Also, an option allows to use the LLR program for a factoring-only job.
      For example, to use this option for prefactoring candidates up to 40
      bits factor, add the line "FacTo=40" in the llrxxxx.ini file.

      I think we have now an efficient tool, and that the time for a
      systematic search for Gaussian-Mersenne primes has arrived!

      Beside this new feature, the new LLR is identical as 3.6.2 version,
      with only some secondary corrections and error recovery improvings :

      -The InterimResidues and InterimFiles options have been added, and work
      exactly as in Prime95/Mprime.

      -The rounding error recovery has been improved.

      -When an error opening output file occurs, the current result is now
      saved in the Log file.

      -A wrong order bug on Lucky plus and Lucky minus tests has been fixed.

      You may read the Readme.txt file for more precisions.

      I wish this work would help you for many big prime discoveries in the
      near future!

      Best Regards,
      Jean
    • mikeoakes2@aol.com
      ... That s great news, Jean! I had a job to find it from your instructions on the GIMPS directory . Using google, I homed in on the file LLR370.zip at this
      Message 2 of 7 , Apr 4 10:34 AM
      • 0 Attachment
        Jean Penné <jpenne@...> wrote:

        >The new LLR 3.7.0 Version is now available on the GIMPS directory!
        >
        >It contains as a new important feature an efficient primality proving
        >test for the Gaussian-Mersenne norms.

        That's great news, Jean!

        I had a job to find it from your instructions "on the GIMPS directory".
        Using google, I homed in on the file LLR370.zip at this page:
        http://www.mersenne.org/gimps/
        which must be it, yes?

        It would be really nice if the search for Gaussian Mersennes was revived. I devoted a lot of time to it some years back, and have no more cycles to spare.
        One of you guys with a classroom-ful of PCs?...

        >(nevertheless, the
        >actual record, GM(991961) , has been discovered by Boris Iskra
        >in November 2005).

        It's really unfortunate that Chris has to put the "?" aginst this entry:-
        123f 2^991961-2^495981+1 298611 x28 2005
        Gaussian Mersenne norm 36?

        The reason is that Boris has never stated whether this is the next one to:
        1156 2^364289-2^182145+1 109662 p58 2001
        Gaussian Mersenne norm 35
        or not, in spite of having been asked, on and off list.

        Without an answer, there seems no real alternative to someone sweeping that intermediate range, which may well be duplicted effort.

        There is exactly the same problem about his "Eisenstein Mersenne" record:
        152f 3^534827-3^267414+1 255178 x28 2005

        Is it the /next/ one after this:
        891 3^255361-3^127681+1 121839 p96 2002
        or not?

        Are you listening, Boris...?

        -Mike Oakes
      • Jean Penné
        ... Yes, indeed! I am sorry for this too vague info... ... revived. I hope (and think) it will be the case! ... I know that! ... possibly... ... entry:- ...
        Message 3 of 7 , Apr 4 11:29 AM
        • 0 Attachment
          --- In primenumbers@yahoogroups.com, mikeoakes2@... wrote:

          > That's great news, Jean!
          >
          > I had a job to find it from your instructions "on the GIMPS directory".
          > Using google, I homed in on the file LLR370.zip at this page:
          > http://www.mersenne.org/gimps/
          > which must be it, yes?

          Yes, indeed! I am sorry for this too vague info...

          >
          > It would be really nice if the search for Gaussian Mersennes was
          revived.

          I hope (and think) it will be the case!

          > I devoted a lot of time to it some years back,

          I know that!

          >and have no more cycles to spare.
          > One of you guys with a classroom-ful of PCs?...
          >

          possibly...

          > >(nevertheless, the
          > >actual record, GM(991961) , has been discovered by Boris Iskra
          > >in November 2005).
          >
          > It's really unfortunate that Chris has to put the "?" aginst this
          entry:-
          > 123f 2^991961-2^495981+1 298611 x28 2005
          > Gaussian Mersenne norm 36?
          >
          > The reason is that Boris has never stated whether this is the next
          one to:
          > 1156 2^364289-2^182145+1 109662 p58 2001
          > Gaussian Mersenne norm 35
          > or not, in spite of having been asked, on and off list.
          >
          > Without an answer, there seems no real alternative to someone
          sweeping that intermediate range, which may well be duplicted effort.

          If you agree,
          I think I can do this job, having already prefactored the corresponding
          candidates up to 40 bits factors, so it would not be too time consuming.

          Regards,
          Jean
        • Paul Underwood
          ... Thanks very much, Jean, for a significant speed up over version 3.6.2 on some P4s at 2.6M bits (321). For example, at 2.5GHz I have noticed the times for a
          Message 4 of 7 , Apr 11 2:38 PM
          • 0 Attachment
            --- In primenumbers@yahoogroups.com, Jean Penné <jpenne@...> wrote:
            >
            > Hi All,
            >
            > The new LLR 3.7.0 Version is now available on the GIMPS directory!
            >

            Thanks very much, Jean, for a significant speed up over version 3.6.2
            on some P4s at 2.6M bits (321). For example, at 2.5GHz I have noticed
            the times for a test dropping from 4:30 hours to 3:50 hours,

            Paul
          • eharsh82
            Hi, I just wanted to mention the following:- The algorithm described in LLR3.7 can be extended to several other forms of numbers. In short, all forms that are
            Message 5 of 7 , Apr 22 4:41 PM
            • 0 Attachment
              Hi,
              I just wanted to mention the following:-

              The algorithm described in LLR3.7 can be extended to several other
              forms of numbers. In short, all forms that are factors of k*a^n+-1,
              where k can be 1 to a positive integer can be tested faster than PFGW
              using this algorithm.

              I think that the PIES project will benefit from the algorithm if Phll
              wants to implement it.

              (May be Dr. Cadwell can post the algorithm on his Gaussian Mersenne
              webpage, so other people can understand and improve on it)


              Thanks, Harsh




              --- In primenumbers@yahoogroups.com, Jean Penné <jpenne@...> wrote:
              >
              > Hi All,
              >
              > The new LLR 3.7.0 Version is now available on the GIMPS directory!
              >
              > It contains as a new important feature an efficient primality proving
              > test for the Gaussian-Mersenne norms.
              >
              > Mike Oakes originated this search in the early 1970, and discovered
              > most of the above-titanic GM primes presently known (nevertheless, the
              > actual record, GM(991961) , has been discovered by Boris Iskra in
              > November 2005).
              > These numbers may be proven prime by the Proth theorem test, but the k
              > multiplier value beeing an exponential function of p, it would
              > require using the gwnums in generic mode...
              > Following a suggestion by Harsh Aggarwal, I implemented, in the new
              > version LLR3.7.0, a much more efficient method :
              > The starting point is the Aurifeuillian factorization of M(p) = 4^p+1 :
              >
              > M(p) = 4^p+1 = (2^p + 2^((p+1)/2) + 1)(2^p - 2^((p+1)/2) + 1)
              >
              > One of these two factors is the norm N(p) of GM(p) = (1±i)^p - 1
              >
              > Now, the idea is to run the Proth algorithm, but doing the squarings
              > modulo M(p), and then doing the modulo N reduction only on the final
              > result. Then, the performances for a given p may be approximatively
              > the same as for a Lucas-Lehmer test with exponent 2*p.
              > In order to make this prime search really efficient, it is however
              > necessary that the prime exponent candidates would be sieved enough by
              > prefactoring, so I adapted the George Woltman's "factor32.asm" for
              > 4^p+1 factoring, and this new code is included in LLR to eliminate the
              > candidates having a non trivial factor, before doing the Proth test.
              > The factoring upper limit is dependent on the exponent size, and can
              > reach 86 bits, as for GIMPS.
              > Also, an option allows to use the LLR program for a factoring-only job.
              > For example, to use this option for prefactoring candidates up to 40
              > bits factor, add the line "FacTo=40" in the llrxxxx.ini file.
              >
              > I think we have now an efficient tool, and that the time for a
              > systematic search for Gaussian-Mersenne primes has arrived!
              >
              > Beside this new feature, the new LLR is identical as 3.6.2 version,
              > with only some secondary corrections and error recovery improvings :
              >
              > -The InterimResidues and InterimFiles options have been added, and work
              > exactly as in Prime95/Mprime.
              >
              > -The rounding error recovery has been improved.
              >
              > -When an error opening output file occurs, the current result is now
              > saved in the Log file.
              >
              > -A wrong order bug on Lucky plus and Lucky minus tests has been fixed.
              >
              > You may read the Readme.txt file for more precisions.
              >
              > I wish this work would help you for many big prime discoveries in the
              > near future!
              >
              > Best Regards,
              > Jean
              >
            • Phil Carmody
              ... _If_ you can quantitatively detail the benefits I ll look at it. I already use a combination of DWTs which include _no wastage at all_. You only make FFTs
              Message 6 of 7 , Apr 23 2:28 AM
              • 0 Attachment
                --- eharsh82 <harsh@...> wrote:
                > Hi,
                > I just wanted to mention the following:-
                >
                > The algorithm described in LLR3.7 can be extended to several other
                > forms of numbers. In short, all forms that are factors of k*a^n+-1,
                > where k can be 1 to a positive integer can be tested faster than PFGW
                > using this algorithm.
                >
                > I think that the PIES project will benefit from the algorithm if Phll
                > wants to implement it.

                _If_ you can quantitatively detail the benefits I'll look at it.

                I already use a combination of DWTs which include _no wastage at all_.
                You only make FFTs larger if you don't have modular reduction for
                free anyway. The new LLR technique adds _significant_ wastage.

                PIES could most benefit from not being written in pure portable C.
                (And only being a few tens of kilobytes of code at that.)
                The Prime95 libraries that LLR uses contain large quantities of
                exceptionally optimised hand-coded assembly. However, the interface
                looked like a train-wreck, I just didn't want to touch it.

                An FFT that's 1.5x faster than my version of DJBFFT could beat my
                current implementation by using this 'short cut'. However, if I had
                an FFT which was 1.5x faster, then this 'short cut' would be
                significantly slower.

                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
              • George Woltman
                ... You ll be glad to know that the interface was improved last year. It is now just an automobile accident.
                Message 7 of 7 , Apr 23 6:54 AM
                • 0 Attachment
                  At 05:28 AM 4/23/2006, you wrote:
                  >The Prime95 libraries that LLR uses contain large quantities of
                  >exceptionally optimised hand-coded assembly. However, the interface
                  >looked like a train-wreck, I just didn't want to touch it.

                  You'll be glad to know that the interface was improved last year. It is
                  now just an automobile accident.
                Your message has been successfully submitted and would be delivered to recipients shortly.