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

Re: Largest fake prime number holds 300 billion digits

Expand Messages
  • 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 1 of 6 , Mar 14 5:34 PM
    • 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 2 of 6 , Mar 14 5:47 PM
      • 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 3 of 6 , Mar 15 2:19 AM
        • 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 4 of 6 , Mar 15 5:09 AM
          • 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.