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

Largest fake prime number holds 300 billion digits

Expand Messages
  • paulunderwooduk
    http://www.newscientist.com/article/dn23171-largest-fake-prime-number-holds-300-billion-digits.html Does anybody volunteer to run BPSW on this number?
    Message 1 of 6 , Mar 14, 2013
    • 0 Attachment
      http://www.newscientist.com/article/dn23171-largest-fake-prime-number-holds-300-billion-digits.html

      Does anybody volunteer to run BPSW on this number? Presumably, it is a Carmichael number,

      Paul
    • djbroadhurst
      ... http://arxiv.org/pdf/1203.6664.pdf ... David
      Message 2 of 6 , Mar 14, 2013
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        "paulunderwooduk" <paulunderwood@...> wrote:

        > Presumably, it is a Carmichael number

        http://arxiv.org/pdf/1203.6664.pdf

        > We have constructed a Carmichael number with 10,333,229,505 prime factors

        David
      • djbroadhurst
        ... Let a=2^(2^57885161-1)-1 and b=(a+2)/3. Then N=a*b is 2-PRP. Is N a BPSW PRP? Who could possibly tell? Who might ever care? David
        Message 3 of 6 , Mar 14, 2013
        • 0 Attachment
          --- In primenumbers@yahoogroups.com,
          "paulunderwooduk" <paulunderwood@...> wrote:

          > Does anybody volunteer to run BPSW on this number?

          Let a=2^(2^57885161-1)-1 and b=(a+2)/3. Then N=a*b is 2-PRP.
          Is N a BPSW PRP? Who could possibly tell? Who might ever care?

          David
        • Phil Carmody
          ... Yeah, but you can t believe everything they say, as they also say Current records for Carmichael numbers with many prime factors go to Loh and Niebuhr
          Message 4 of 6 , Mar 14, 2013
          • 0 Attachment
            --- On Fri, 3/15/13, djbroadhurst <d.broadhurst@...> wrote:
            > "paulunderwooduk" <paulunderwood@...> wrote:
            >
            > > Presumably, it is a Carmichael number
            >
            > http://arxiv.org/pdf/1203.6664.pdf
            >
            > > We have constructed a Carmichael number with 10,333,229,505 prime factors

            Yeah, but you can't believe everything they say, as they also say
            """
            Current records for Carmichael numbers with many prime factors
            go to Loh and Niebuhr [9] at 1101518 prime factors and an
            unpublished computation by the first two authors at 19565300
            prime factors.
            """

            Pah! I'm pretty sure that MJOS & I announced out record-breaking Carmichaels either here (or on NMBRTHRY?) whenever it was (8-10 years ago?). I've got to admit, it was too easy and mathematically boring (just a simple big-steps-baby-steps discrete logarithm) so we didn't bother wasting time pushing the limit as far as the algorithm (and storage capacity for the table of small primes) would go - that would just be handle-turning.

            Hmm, even google can't find that - but I ain't senile, I do remember doing it! I still have the code and and some early runs on my machine:

            $ ls -al mjos/mjos.txt
            -rw-r----- 1 phil phil 4439 Nov 30 2002 mjos/mjos.txt
            $ ls -al mjos/known/car24.tbz
            -rw-r--r-- 1 phil phil 4768781 May 20 2004 mjos/known/car24.tbz
            $ bunzip2 < $! | wc -l
            1521430

            That's bigger than the Loh one, at least, and confirms the timescale I was thinking about (the .tbz was almost certainly created by me when cleaning up after the files were no longer current). I don't think Markku-Juhani ever gave me the output of his larger runs (he had access to his uni cluster), so they're lost. But I as I have the code, I could recreate them, they nearly double in size with each step. More

            However, 10,333,229,505 is a truly momentous, I cannot imagine how many more doublings of our problem size would be necessary to reach that far. Even hundreds of millions of small primes would have been pushing the limits of any single machine I have access to today.

            So this is almost certainly a serious algorithmic breakthrough, and not just handle-turning. I shall give it a more thorough read tomorrow.

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

            [stolen with permission from Daniel B. Cristofani]
          • djbroadhurst
            ... http://tech.groups.yahoo.com/group/primenumbers/message/11058 David
            Message 5 of 6 , Mar 15, 2013
            • 0 Attachment
              --- In primenumbers@yahoogroups.com,
              Phil Carmody <thefatphil@...> wrote:

              > I'm pretty sure that MJOS & I announced out record-breaking
              > Carmichaels either here (or on NMBRTHRY?) whenever it was
              > (8-10 years ago?).

              http://tech.groups.yahoo.com/group/primenumbers/message/11058

              David
            • Phil Carmody
              ... Wow, if it was 200 times larger, then we did push it all the way to its limits. I d forgotten that Markku-Juhani had done that, I don t have his logs. He
              Message 6 of 6 , Mar 15, 2013
              • 0 Attachment
                --- On Fri, 3/15/13, djbroadhurst <d.broadhurst@...> wrote:
                > Phil Carmody <thefatphil@...> wrote:
                > > I'm pretty sure that MJOS & I announced out record-breaking
                > > Carmichaels either here (or on NMBRTHRY?) whenever it was
                > > (8-10 years ago?).
                >
                > http://tech.groups.yahoo.com/group/primenumbers/message/11058

                Wow, if it was 200 times larger, then we did push it all the way to its limits. I'd forgotten that Markku-Juhani had done that, I don't have his logs. He did have access to part of what was once the 7th largest machine in the world when he was found that. A bit of a rewrite (we'd need more than 32 bits) would have been necessary to go any further. 6 Moore's Law doublings does indicate that a 6-billion factor Carmichael should be possible with the same algorithm on a cluster in 2013. With more-distributed computing, perhaps even more. The long boring bit that grows at O(n) is embarassingly parallel, and the "clever" bit (what Loh overlooked) only grows at O(sqrt(n)).

                Phil
              Your message has been successfully submitted and would be delivered to recipients shortly.