## Largest fake prime number holds 300 billion digits

Expand Messages
• 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
• ... http://arxiv.org/pdf/1203.6664.pdf ... David
Message 2 of 6 , Mar 14, 2013
• 0 Attachment
"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
• ... 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
"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
• ... 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
> "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 ﬁrst 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]
Message 5 of 6 , Mar 15, 2013
• 0 Attachment
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?).

David
• ... 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