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

Re: Largest Ordinary Prime?

Expand Messages
  • paulunderwooduk
    ... PFGW was exploited for the inital search for a PRP because of it s gain in speed in this respect -- for 2^n+-k (k
    Message 1 of 22 , Oct 1, 2002
    • 0 Attachment
      --- Carl Devore wrote:
      > On Mon, 30 Sep 2002, David Broadhurst wrote:
      > > Ordinary it ain't, since it was possible, with a huge
      > > effort by Paul Underwood, Bouk de Water, Paul Leyland
      > > and myself, to factorize 30.08% of N+1=2^15*(2^64680-1)
      > > and hence to prove N prime using Konyagin-Pomerance.
      >
      > Also, major efficiency gains can be realized for simple arithmetic
      > with a
      > number with such a sparse binary representation. Whether the code
      > actually exploited those efficiencies I don't know.

      PFGW was exploited for the inital search for a PRP because of it's
      gain in speed in this respect -- for 2^n+-k (k< about 43 bits.) I
      used Prime95.exe to try and find factors of 2^32340-1 and 32340+1 and
      this uses DFT I think. Paul Leyland also ran some ECM curves with
      this program. I think David and Bouk used ECM.exe -- I don't know if
      this uses the effiency. Does Pari-GP?

      Paul
    • paulunderwooduk
      ... Yes the signs are important for these trinomials. The most genral case I have is x^n+-x^k-1 (x,n,k all positive integers x 1,n 2,n k 0 and discounting
      Message 2 of 22 , Oct 1, 2002
      • 0 Attachment
        --- Marcel Martin wrote:
        >
        > In a previous post, I wrote:
        > >>2^64695-2^15-1 19476 x43 2002 Unmentionable!
        >
        > >It could be archived as "3-bit prime".
        >
        > That's anywhat. I didn't take in account the minus signs :-))
        >

        Yes the signs are important for these trinomials. The most genral
        case I have is x^n+-x^k-1 (x,n,k all positive integers x>1,n>2,n>k>0
        and discounting Mersenne and "Fermat-type" (2^n+1) numbers. Call the
        trinomial f. I have not found a composite f:f|x^f-x. For instance
        this for f=x^3-x-1 passes 5 rounds of Miller Rabin at least for all
        x<19700000001 (1007728207 PrPs).

        I forgot to say in my previous post that Primo was used for proving
        the primailty of some of the factors of N+1. I used bc for my
        arithmetic ;)

        Paul
      • David Broadhurst
        N=2^64695-2^15-1 is prime. Paul Underwood discovered that N is probably prime, as part of a large trawl of candidates of his favourite form f(a,b)=2^a-2^b-1
        Message 3 of 22 , Oct 1, 2002
        • 0 Attachment
          N=2^64695-2^15-1 is prime.

          Paul Underwood discovered that N is
          probably prime, as part of a large trawl
          of candidates of his favourite form
          f(a,b)=2^a-2^b-1
          with large a and small b.

          Bouk de Water observed that
          N+1=2^15*(2^64680-1)
          is highly composite, since
          64680=2*2*2*3*5*7*7*11
          has 96 divisors.

          Moreover he found the 1012-digit prime
          p1012=gcd(phi(4*8085,2),2^8085-2^4043+1)
          which divides N+1.

          By late July, David Broadhurst had used ecm-gmp on
          all of 11 remaining composite cofactors of
          {Phi(d,2);d|64680} (and their Aurifeuillian parts,
          when d=4 mod 8) which had less than 600 digits,
          making 1800 attempts on each of these 11 at B1=10^6,
          i.e. p35 level. This took O(100) GHz-days of effort.

          Working on largest cofactor,
          Paul Leyland found that
          p26=13304801278785221502712801
          divides Phi(64680,2) with more than 4000 digits.

          At this stage we lacked 221 digits of factorization,
          and Paul Leyland contemplated using NFS on the
          smallest composite, with 162 digits, if another
          50 digits could be found with ECM.

          In the event, NFS was not needed.
          Paul Underwood used prime95 to find 2 large
          factors of N+1=2^15*(2^64680-1), namely

          p43=1974132723329736593062151838364049346634561
          p41=37131299037462589694325096898604106162577

          with the second leaving a 154-digit prime
          in the now completed factorization of the
          Aurifeuillian factor

          gcd(phi(4*1617,2),2^1617+2^809+1)=
          6469*1346555145625865869*p38*p41*p154

          where

          p38=10816328089875303012806778969765211273

          had already been found by ecm-gmp.

          We now had 30.08% factorization of the
          digits of N+1, sufficient for a
          Konyagin-Pomerance proof.

          The actual primality proving was easy:
          about a quarter of an hour of pfgw,
          for the Lucas tests,

          Primality testing 2^15*(2^64680-1)-1
          [N+1, Brillhart-Lehmer-Selfridge]
          Calling Brillhart-Lehmer-Selfridge
          with factored part 30.08%
          2^15*(2^64680-1)-1 is Lucas PRP!
          (1060.780000 seconds)

          and then a few minutes of Pari-GP to complete
          the proof using the pair of Konyagin-Pomerance
          cubics of Theorem 4.2.9 of the book by
          Crandall and Pomerance. The code for this
          was written by David Broadhurst and had been
          checked by Andy Steward in the course of
          proving primality of (3048^3121-1)/3047.

          We also used 90 minutes of Primo to prove primality
          of the prime factors of N+1, the largest known
          being p1012, above.

          By no stretch of the imagination is

          N=2^64695-2^15-1

          an "ordinary" prime. It is extraordinary
          by the circumstance that it _just_ permitted
          a Konyagin-Pomerance proof by factorization of N+1,
          using cyclotomic and Aurifeuillian theory and
          the best factoring engines available.

          At 19476 decimal digits, it holds the record
          for a very special type of proof:
          "easy after much difficult factoring".

          The previous record of this type was held
          by Fibonacci(81839) with 17103 digits.

          The record for proving a _truly_ ordinary prime
          still stands at 5020 digits:

          http://www.znz.freesurf.fr/pages/primotop20.html

          David Broadhurst
        • David Broadhurst
          ... Err, it seems to me that it has all bits but one set to 1: ? b=binary(2^64695-2^15-1); ? print(sum(k=1,64695,b[k])) 64694 It is a base-2 near repunit ,
          Message 4 of 22 , Oct 1, 2002
          • 0 Attachment
            Marcel:

            > What I meant is that we cannot call
            > 2^64695-2^15-1 a "3-bit prime".
            > Because of the minus signs, it
            > has 63951 bits set to 1, not just 3.

            Err, it seems to me that it has all bits but
            one set to 1:

            ? b=binary(2^64695-2^15-1);
            ? print(sum(k=1,64695,b[k]))
            64694

            It is a "base-2 near repunit",
            just one bit-change
            away from being a Mersenne.

            David
          • David Broadhurst
            ... Not really. Everyone knows that Hans is doing something huge, well above 6k digits. So why spend cycles to become a poor second in 2003 :-? David
            Message 5 of 22 , Oct 1, 2002
            • 0 Attachment
              Marcel:
              > >The record for proving a _truly_ ordinary prime
              > >still stands at 5020 digits
              > And this is somewhat surprising.
              Not really.
              Everyone knows that Hans is doing something huge,
              well above 6k digits.
              So why spend cycles to become a poor second in 2003 :-?
              David
            • Jon Perry
              ... But it is: 2^15[2^64680-1]-1 and perhaps this may yield a name. Jon Perry perry@globalnet.co.uk http://www.users.globalnet.co.uk/~perry/maths BrainBench
              Message 6 of 22 , Oct 1, 2002
              • 0 Attachment
                >What I meant is that we cannot call
                >2^64695-2^15-1 a "3-bit prime". Because of the minus signs, it
                >has 64694 bits set to 1, not just 3.

                But it is:

                2^15[2^64680-1]-1

                and perhaps this may yield a name.

                Jon Perry
                perry@...
                http://www.users.globalnet.co.uk/~perry/maths
                BrainBench MVP for HTML and JavaScript
                http://www.brainbench.com

                T
              • David Broadhurst
                ... That was unfortunate. I had a registered Titanix (thanks!) which did all the batch except the p1012 and then used latest Primo 2.0.0 beta3 for this, the
                Message 7 of 22 , Oct 1, 2002
                • 0 Attachment
                  Marcel:
                  > I didn't take in account that kind of Primo use
                  > when I set the limitations of the new version
                  > (to prevent the use of Primo by companies).
                  That was unfortunate.
                  I had a registered Titanix (thanks!)
                  which did all the batch except the p1012
                  and then used latest Primo 2.0.0 beta3
                  for this, the biggest.
                  David
                • David Broadhurst
                  ... On July 2 he told that he had done 2173 bits of something big: http://groups.yahoo.com/group/primeform/message/2621 On Sept 21 he told that he had recently
                  Message 8 of 22 , Oct 1, 2002
                  • 0 Attachment
                    Marcel:

                    > Maybe Hans told of it elsewhere,

                    On July 2 he told that he had done 2173 bits
                    of something big:

                    http://groups.yahoo.com/group/primeform/message/2621

                    On Sept 21 he told that he had recently gotten
                    below 20 kilobits:

                    http://groups.yahoo.com/group/primeform/message/2720

                    Putting these together, it is probable
                    that he started above 7k decimal digits.

                    But it seems that Marcel did not like
                    the idea of me cross-posting the inference?

                    > I wondered 'Why did he do that?'.

                    Because I like trying to solve
                    publicly posted puzzles.

                    David
                  • David Broadhurst
                    ... There is good reason to suppose from http://groups.yahoo.com/group/primeform/message/2719 that Hans s target was posted by him as a PrP at
                    Message 9 of 22 , Oct 1, 2002
                    • 0 Attachment
                      > Because I like trying to solve
                      > publicly posted puzzles.

                      There is good reason to suppose from

                      http://groups.yahoo.com/group/primeform/message/2719

                      that Hans's target was posted by him as a PrP at

                      http://www.worldofnumbers.com/undulat.htm

                      So then one may take the hinted data:

                      1) processor about 1.5 GHz AMD
                      2) 2173 bits done before July 2
                      3) below 20 kilobits by Sept 21

                      Next one differentiates my notional

                      hours=(bits/3000)^4.5/(speed/GHz)

                      to guess a notional rate of

                      1000*(3000/22000)^3.5 ~ 1 bit/hour

                      at 1.5 GHz with around 22 kilobits left.

                      There were slightly more than
                      1800 hours between messages.

                      So notional starting number of bits is about

                      2173 + 1800 + 20000 ~ 24000

                      Then one asks which of the PrPs

                      (75*10^6249-57)/99
                      (14*10^6343-41)/99
                      (74*10^6815-47)/99
                      (32*10^6959-23)/99
                      (15*10^7233-51)/99
                      (72*10^7595-27)/99
                      (12*10^7809-21)/99
                      (18*10^8315-81)/99

                      is closest to 24 kilobits?

                      I bet on

                      (15*10^7233-51)/99

                      with 24025 bits,
                      which Hans discovered
                      to be PrP on 4 Jun 2001.

                      He will be ever so pleased if
                      I have failed to solve the puzzle:-)

                      At 1.5 GHz we might expect to know in

                      (20000/3000)^4.5/1.5/24/30 ~ 5 months time.

                      My best bet:
                      the 24 kilobit smoothly undulating prime
                      (15*10^7233-51)/99
                      by the end of February,
                      provided the gods of the
                      dreaded backtracks don't intervene.

                      David (in puzzle solving mode)
                    • Andy Steward
                      Firstly, congratulations to Paul, Paul, David and Bouk. Secondly, DAMN. I had this great idea while I was on holiday about ten days ago. It appears to be much
                      Message 10 of 22 , Oct 3, 2002
                      • 0 Attachment
                        Firstly, congratulations to Paul, Paul, David and Bouk.

                        Secondly, DAMN. I had this great idea while I was on holiday
                        about ten days ago. It appears to be much the the same idea that
                        you guys had a long while earlier ;-)

                        I used my experience in trying to prove Gigantic GRUs to model
                        how many digits of prime factors I would expect to extract from
                        a cyclotomic factor of a given size given the amount of ECM work
                        I have done on such factors to date (about 7-10 GHz hours on each
                        composite on average, though some I've just started and a few have
                        had thousands of hours).

                        I then generated a list of promising composite exponents c such that
                        2^c-1 gave a decent chance of being useful in proving 2^a - 2^b +/- 1
                        where c=a-b. 64680 came out at 19.85%, so your 30% indicates how much
                        more work you did on it (and a bit of luck). I reckon the best few
                        exponents of around the same size are: 65520, 75600, 69300, 83160,
                        73920, 70560 then 64680.

                        Another thought I had was to use 2^c-1 where it's a Mersenne prime
                        ... or c=2p, 3p etc where 2^p-1 is a Mersenne prime: diminishing
                        returns but worth a try for small multiples.

                        Ah well, I'll stick to the GRUs.

                        Good luck,
                        Andy
                      • David Broadhurst
                        ... Then recall that Paul U restricted his search of 2^a-2^b-1 to b
                        Message 11 of 22 , Oct 4, 2002
                        • 0 Attachment
                          Andy:

                          > I reckon the best few exponents of around
                          > the same size are: 65520, 75600, 69300,
                          > 83160, 73920, 70560 then 64680.

                          Then recall that Paul U restricted his
                          search of 2^a-2^b-1 to b<=40.

                          So that gives 280 chances for those 7
                          values of c=a-b, whereas
                          ln(N) ~ ln(2^70000) = 50,000,
                          giving you odds of order 100:1 against.

                          It's neat that one of your 280 showed up,
                          with b=15, and even neater that Bouk's eagle
                          eyes spotted it in Henri's pages.

                          PS: How's the latest GRU cooking?

                          Remember that Phil has just offered
                          double the usual extra bits,
                          if/when you need them :-)

                          Also Paul L was holding NFS cycles
                          in reserve for 2^15*(2^64680-1)-1
                          which we didn't need. So maybe
                          you could do something really
                          impressive with another 150 digits
                          from him, in some strategic place :-?

                          Best wishes

                          David
                        • paulunderwooduk
                          ... b
                          Message 12 of 22 , Oct 4, 2002
                          • 0 Attachment
                            > > I reckon the best few exponents of around
                            > > the same size are: 65520, 75600, 69300,
                            > > 83160, 73920, 70560 then 64680.
                            >
                            > Then recall that Paul U restricted his
                            > search of 2^a-2^b-1 to b<=40.
                            >

                            b<44 actually. Also a<100000.

                            Bouk suggests having a look at 118080.

                            I will find minimal PrPs for all the suggestions at the end of the
                            month; also for 2^a-2^b+1. ;-)

                            Paul
                          • Andy Steward
                            ... Did you mean 110880? I get an expected factorisation of 18.4% for that one, but only 9.7% for 118080. By my model, 110880 is the most promising exponent in
                            Message 13 of 22 , Oct 5, 2002
                            • 0 Attachment
                              Paul Underwood wrote:

                              > Bouk suggests having a look at 118080.

                              Did you mean 110880? I get an expected factorisation of
                              18.4% for that one, but only 9.7% for 118080. By my model,
                              110880 is the most promising exponent in (85680,750000]

                              Here's a list of exponents where each entry has a higher
                              expected factorisation yield than any larger:

                              Exponent, factors, expectation
                              1680,40,100.00%
                              1740,24,96.33%
                              1890,32,95.48%
                              2100,36,94.98%
                              2520,48,91.05%
                              2640,40,88.53%
                              2940,36,88.41%
                              3360,48,86.53%
                              3780,48,82.88%
                              3960,48,80.44%
                              4200,48,79.05%
                              4620,48,78.67%
                              5040,60,78.06%
                              5460,48,71.49%
                              5880,48,69.92%
                              6120,48,69.12%
                              7560,64,68.14%
                              7920,60,63.67%
                              9240,64,62.61%
                              10080,72,61.54%
                              10920,64,56.45%
                              12600,72,53.33%
                              13860,72,52.73%
                              15120,80,51.39%
                              16380,72,46.94%
                              18480,80,46.48%
                              20160,84,43.47%
                              21840,80,41.16%
                              27720,96,39.70%
                              30240,96,36.29%
                              32760,96,35.11%
                              36960,96,31.72%
                              37800,96,30.69%
                              40320,96,28.96%
                              41580,96,28.95%
                              42840,96,28.73%
                              55440,120,28.00%
                              65520,120,24.39%
                              75600,120,21.10%
                              83160,128,21.05%
                              85680,120,19.43%
                              110880,144,18.40%
                              131040,144,15.89%
                              138600,144,15.06%
                              166320,160,14.15%
                              171360,144,12.41%
                              196560,160,12.14%
                              221760,168,11.37%
                              240240,160,10.17%
                              277200,180,9.96%
                              332640,192,8.95%
                              360360,192,8.35%
                              393120,192,7.64%
                              415800,192,7.26%
                              443520,192,6.75%
                              471240,192,6.43%
                              480480,192,6.31%
                              498960,200,6.29%
                              554400,216,6.21%
                              556920,192,5.47%
                              720720,240,5.39%
                              739200,192,4.09%
                              742560,192,4.08%
                              748440,192,3.93%
                              749700,162,3.33%

                              HTH,
                              Andy
                            • Bouk de Water
                              ... 110880 it should be indeed. Moreover because phi(36960,2) is a prp. 36960 * 2 = 73920 2^73920-1 is already BLS 36960 * 3 = 110880 2^110880-1 is about 1300
                              Message 14 of 22 , Oct 5, 2002
                              • 0 Attachment
                                --- Andy Steward <aads@...> wrote:
                                > Paul Underwood wrote:
                                >
                                > > Bouk suggests having a look at 118080.
                                >
                                > Did you mean 110880? I get an expected factorisation of
                                > 18.4% for that one, but only 9.7% for 118080. By my model,
                                > 110880 is the most promising exponent in (85680,750000]

                                110880 it should be indeed. Moreover because phi(36960,2) is a prp.

                                36960 * 2 = 73920

                                2^73920-1 is already BLS

                                36960 * 3 = 110880

                                2^110880-1 is about 1300 digits short for Konyagin-Pomarance.

                                Bouk.

                                __________________________________________________
                                Do you Yahoo!?
                                Faith Hill - Exclusive Performances, Videos & More
                                http://faith.yahoo.com
                              • Phil Carmody
                                ... Not yet... ;-) Phil ===== First rule of Factor Club - you do not talk about Factor Club. Second rule of Factor Club - you DO NOT talk about Factor Club.
                                Message 15 of 22 , Oct 5, 2002
                                • 0 Attachment
                                  --- Bouk de Water <bdewater@...> wrote:
                                  > Moreover because phi(36960,2) is a prp.
                                  ^^^
                                  > 36960 * 2 = 73920
                                  >
                                  > 2^73920-1 is already BLS

                                  Not yet... ;-)

                                  Phil



                                  =====
                                  First rule of Factor Club - you do not talk about Factor Club.
                                  Second rule of Factor Club - you DO NOT talk about Factor Club.
                                  Third rule of Factor Club - when the cofactor is prime, or you've trial-
                                  divided up to the square root of the number, the factoring is over.

                                  __________________________________________________
                                  Do you Yahoo!?
                                  Faith Hill - Exclusive Performances, Videos & More
                                  http://faith.yahoo.com
                                • David Broadhurst
                                  ... True, oh sage. But 2312 digits would be a mere bagatelle for primo. More significantly what a would make 2^a*(2^73920-1)-1 PrP? On average you have to
                                  Message 16 of 22 , Oct 5, 2002
                                  • 0 Attachment
                                    Phil:

                                    > Not yet... ;-)

                                    True, oh sage.

                                    But 2312 digits would be
                                    a mere bagatelle for primo.

                                    More significantly what "a" would make
                                    2^a*(2^73920-1)-1
                                    PrP?

                                    On average you have to wait a long time
                                    and by then 2^a gives you most of BLS anyway,
                                    thus eroding you factorization work.

                                    It was Paul U's a=15 that was really notable in

                                    2^15*(2^64680-1)-1

                                    David
                                  • Andrey Kulsha
                                    ... [snip] ... To be precise, 239 phi-factors and 5.895144%: http://groups.yahoo.com/group/primenumbers/files/Factors/m720720.zip Best, Andrey [Non-text
                                    Message 17 of 22 , Oct 13, 2002
                                    • 0 Attachment
                                      Andy Steward wrote:

                                      > Here's a list of exponents where each entry has a higher
                                      > expected factorisation yield than any larger:
                                      >
                                      > Exponent, factors, expectation
                                      [snip]
                                      > 720720,240,5.39%

                                      To be precise, 239 phi-factors and 5.895144%:

                                      http://groups.yahoo.com/group/primenumbers/files/Factors/m720720.zip

                                      Best,

                                      Andrey


                                      [Non-text portions of this message have been removed]
                                    Your message has been successfully submitted and would be delivered to recipients shortly.