Fun Number Theory Facts

[FloppusMaximus]

Dear community,

I have been politely asked to remove the former contents of this post.

[brandonw]

What are you trying to tell us here? It doesn't look like a key.

[FloppusMaximus]

(redacted)

[Weregoose]

My God, it's... it's...!

I have no clue what it is.

It is "inspiring?"

Nope. Wrong number of bits.

[FloppusMaximus]

Nope, sorry. (I don't know if anyone has even figured out what the public keys are for the Nspire. Anyway, they'd presumably be 1024 bits, somewhat beyond the reach of current computers and algorithms. At a rough guess, ignoring the fact that the software doesn't exist yet, and ignoring the vast amount of storage required, it would take my PC about 4 million years to factor a 1024-bit number.)

This one is for the TI-83+.

[brandonw]

Oh my good lord...

You need to explain how you did this. Now. To somebody.

EDIT: I just confirmed this is what I think it is. This needs to go to ticalc.org. Are you being intentionally cryptic about this and want to stay unknown?

This is big. Very big. History-in-the-making big.

EDIT 2: How long have you had this? Did you actually get it? Who did it? How was it done? I didn't convert it to hex properly the first time, that's why I didn't pick up on it. I can't believe this has been sitting here for two days and no one noticed it.

I'm probably not going to sleep from excitement.

[tr1p1ea]

I always admired your genius Floppy, but this is just ... i cant even find the right words to ...

Im purplexed as to how on earth ...

Fantastic!

[NanoWar]

WHAT?

[ztrumpet]

I also have no clue as to what this is. Can you please tell us?

[Graphmastur]

HOW!! I want to know how you did that!!! Seriously!!!

EDIT: Oh, and by the way, for those who don't understand what that is, see brandonw's website. (brandonw.net)

This is awesome!!! The walls that TI put up are finally coming down with free83p, and other things like this!!!

[Michael]

Well done, Benjamin! You must give us details and stop being so mysterious! :)

Factoring a 512-bit RSA key should take about 8400 MIPS-years. In 2001, with only Pentium IIIs, such a feat seemed well beyond what one person could do. But according to wikipedia, a Core 2 Extreme Q9770 has 49161 MIPS (this number is not going to match up perfectly with factorization MIPS). Quite a monumental increase in power, although still 2 nonstop, 24/7 months of an expensive PC if these rough numbers are correct.

For interesting reading, this article describes the first time a 512-bit RSA key was factored: http://www.interesting-people.org/archives...8/msg00070.html
The main part of that effort took 3.5 months on about 300 computers.

[brandonw]

Yes, and however this was done...if it was done in a semi-practical way, we need to use this to crack the other keys as well, such as 0102 (and 0002, and 000A, and 010A...)

[Graphmastur]

We need someone to write a tutorial on how to build an OS. Or at least document the steps you use when you release your os, brandon.

This would be awesome!! Everyone could have their own OS!!!

[ztrumpet]

I just saw what this actually is! No Way!!
Way to go Floppus Maximus!!

Edit: Does this mean what this says? http://brandonw.net/ If so kudos to all involved!

Edit x2: How long/hard will it be to build your own OS?

[Graphmastur]

[NanoWar]

Wow, I can't believe this. I mean Brandon just got owned - ONE week after the release of Free83P, haha.

[DigiTan]

More funny 'weird' than funny 'haha.' Did they collaborate or something?

[FloppusMaximus]

Whoa! OK, let's take them one at a time.

How did I do this? With the best tools I could find for the job. The best algorithm for factoring really large general numbers (i.e., numbers without any special properties) is the general number field sieve. The best currently-available implementation of the GNFS consists of a combination of the GGNFS and Msieve projects. It's really the guys behind these tools who deserve the credit for making this possible. While it does take a bit of work to get the tools set up correctly, most of what I did was sitting around waiting for it to finish, and every once in a while, telling the script to try another filtering run. :)

Some fun statistics:
- The factorization took, in total, about 1745 hours, or a bit less than 73 days, of computation. (I've actually been working on this since early March; I had a couple of false starts and haven't been able to run the software continously.)
- My CPU, for reference, is a dual-core Athlon64 at 1900 MHz.
- The sieving database was 4.9 gigabytes and contained just over 51 million relations.
- During the "filtering" phase, Msieve was using about 2.5 gigabytes of RAM.
- The final processing involved finding the null space of a 5.4 million x 5.4 million matrix.

Oh, and how long have I had this? About two days now. The job finished on Wednesday afternoon, I tested out the result with PongOS, then I came here to tell you all about it. :)

The other keys will come in their time, I'm sure. If anybody else would like to try factoring one of them, just let me know so we don't step on each other's toes. I haven't started working on any of them yet; I think I'll probably try 0102 next, but I could be persuaded otherwise.

I'm still rather amused that this happened at almost the same time Free83P was released. Great minds think alike...

[Michael]

I presume you followed a document like this then?: http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html

I'm amazed it was only 73 days. I knew the programs did all of the work, but I never realized just how fast CPUs have become.

[FloppusMaximus]

Yes, that's a pretty good overview of the process. At the time, I had to adjust the sieving parameters by hand. But the factMsieve script has been improved a bit since I started this job; at this point it might just work to fire and forget. (Still not a good idea... you shouldn't start a job this big without having at least some idea of what you're doing.)