RSA-129...what's the big deal?

17 Dec 2003

      Derek Atkins reports to us:
...
We are happy to announce that
RSA-129 = 1143816257578888676692357799761466120102182967212423625625618429\
          35706935245733897830597123563958705058989075147599290026879543541
        = 3490529510847650949147849619903898133417764638493387843990820577 *
          32769132993266709549961988190834461413177642967992942539798288533
Of course. What else could it be?

First, to check your result, firing up Mathematica 2.2 gives:

Timing[3490529510847650949147849619903898133417764638493387843990820577

32769132993266709549961988190834461413177642967992942539798288533]

{0.0666667 Second, 11438162575788886766923577997614661201021\

   829672124236256256184293570693524573389783059712356395870\

   5058989075147599290026879543541}

That is, it took MMA only 0.066 second, mostly overhead, to multiply
your two factors to the product you gave.

But much more interesting is seeing how long MMA's "FactorInteger"
function takes to find the factors:

Timing[FactorInteger [11438162575788886766923577997614661201021\

   829672124236256256184293570693524573389783059712356395870\

   5058989075147599290026879543541]]

{4194 Second,

{{3490529510847650949147849619903898133417764638493387843990820577, 1}, 

{32769132993266709549961988190834461413177642967992942539798288533, 1}}}

So, this took slightly longer, 4194 seconds, or a bit over an hour,
but MMA had no problem factoring this number. Why such a big deal?

MMA was even able to extract the magic words:

ExtractMagicWords [%]

{ NOTE THAT THE TIMING ABOVE HAS A CERTAIN DATE VALUE }

You people at the universities sure do know how to waste taxpayer
money!

--Tim May

P.S. My congratulations. No practical use to factor just one such
number, given 10^72 particles in the Universe, but the methods used to
harness so many machines may be useful in all kinds of problems.

-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^859433 | Public Key: PGP and MailSafe available.
"National borders are just speed bumps on the information superhighway."

RSA-129...what's the big deal?

tcmay＠netcom.com