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

Re: [PrimeNumbers] RE: Largest Ordinary Prime?

Expand Messages
  • Carl Devore
    ... Also, major efficiency gains can be realized for simple arithmetic with a number with such a sparse binary representation. Whether the code actually
    Message 1 of 22 , Sep 30, 2002
    • 0 Attachment
      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.
    • 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 2 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 3 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 4 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 5 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 6 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 7 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 8 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 9 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 10 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 11 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 12 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 13 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 14 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 15 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 16 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 17 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 18 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.