2 years? for only 768 bits? that's ridiculously long.. and you guys want to tackle 1024? good luck. let me know if i can help though, i'll gladly install a program on my computer if it won't give me any hassle.

Heh. If only we had access to a TOP500 supercomputer or have some Omni@home project requiring all the spare CPU of the entire TI community. Yeah, I like this BOINC idea.

Actually, if would be awesome if we can crack a RSA-1024 because the biggest RSA number ever factored was RSA-768... Even RSA, at one time, had a challenge about factoring their keys. http://en.wikipedia.org/wiki/RSA_Factoring_Challenge

the 1024 bit key has a $100,000 prize. We should apply whatever we do here and win it.

That's been withdrawn.



I hate to be a party pooper, but the computer power required to do something like this is inconceivable.


at each bit increase, time taken to compute doubles.
768 took 2 years.
769 would take 4 years.
770 would take 8 years.
771 would take 16 years.

etc...



1024-bit, given current tech, would be completely infeasible. You'd have better luck with the power supply flickering techniques.

Edit: a little bit more of perspective

1024-bit RSA Signatures are what the Xbox 360 uses to prevent unsigned code from being ran. That's a multi-million, probably into the billion, design cost that selected RSA-1024 as the signature method of choice. They designed the system to be viable for 10 years as of 2005. Assuming that the computing power in 2015(and that we don't die in 2012) is powerful enough to crack one in 2 years(which is a big assumption), the nspire would likely be replaced or on the verge of replacement, going off of TI's previous release cycles.

I only think that people would more or less be willing to do it if all the had to do was put a program on their computer, that could easily be uninstalled by removing one file.

Well, that's the case with a Perl script, a Java class / archive or a C/C++ program pre-compiled for the most common platforms

wouldn't it be best to start at sqrt(n) and work either up or down (both if adventuresome) because don't the factors usually have about half as many digits as n? so, they'd be closer to sqrt(n) than 3 or n/3.

Definitely. Besides, that's what both Perl scripts are doing: they start working on numbers whose size is near from 512 bits.

Also, for anyone thinking about Trial Division, I promise it won't work.  If you write a program that starts with three, and adds two to every number after that, it will take absolutely forever.

Yes, exhaustive TF is going to take forever, but it may produce a miracle. TF'ing the Nspire's 1024-bit RSA keys is a challenge comparable to playing at the national and international lotteries (well, the odds to win the factorization are even extremely lower than winning any lottery) - but that does not stop millions of people all over the world playing at the lotteries

Will you set [a BOINC project] up, Lionel?

No. As I wrote above, and as you repeated, TF is almost hopeless.
Together, we can spend several CPU-years in total on TF-ing the 1024-bit numbers with random integers of 480-512 bits. But we don't need a BOINC project for such a low effort (in distributed computing measurement).

If we use the GNFS, how in the world will we find a computer powerful enough to solve the matrix?

Indeed, and we would also need to find the algorithms that were used for RSA-768 but remain, AFAICT, unpublished so far. But it may be insufficient: in order to scale up three orders of magnitude, those algorithms are likely to require further improvements.

1024 bits is 128 bytes. That is a big number. It would be impossible with a ti-84.

It's entirely possible to divide 1024-bit integers by 512-bit integers on TI-Z80 calculators - but that would be orders of magnitude slower on a calculator than on a moder PC, all the more the Z80 does not have division / modulo instructions.
(the irony of a TI-Z80, TI-68k or Nspire calculator factoring a 1024-bit RSA key by TF would feel extremely bitter to TI )

Anyway, one positive thing about this is that it could maybe spark interest from non-calc communities as well

Indeed. But the serious factoring community would probably (and rightfully) frown upon spending an unreasonable amount of effort TF'ing a 1024-bit number.

I hate to be a party pooper, but the computer power required to do something like this is inconceivable.

Between others, I have pooped the party before you did, don't worry

The rule of thumb (which I saw on MersenneForum) for the formula just posted by bwang is that the amount of work necessary for GNFS doubles every five-six digits.



Tribal, could you post somewhere your C conversion of the Perl script ? TIA
[EDIT: grammar.]

I think the TI-Nspire is going to be the last "true" graphic calculator made by TI.

As you aren't using a mechanical calculator, I think we won't be using graphic calculators any more in 10 years.

What we'll be using will be a little portable computer (netbook? pocketPC? PDA? phone?...) with a non-math oriented OS, but running a math-software.

That might not be the case for TI. They've been making graphing calcs for a while now that were at least intended to just do math , so they'll probably just make their own little portable thing that only runs their own software.

For the moment here's some ideas that would really hit TI where it hurts:

Apply for a job as a software developer at TI and "accidentally" release their secrets. [We really need a ninja smiley]

Amass an army of nSpires, all linked with their USB port to factor the key. [TI-81s would've been better, but they don't have link ports]

have you ever wondered if the government (or RSA Laboratories) has a list of all these factors for all these keys somewhere for security purposes?

Actually, technically the nspire is just that: a common netbook-style processor (granted, a fairly weak one)

If they wanted the nspire to be some fancy handheld computer, they could do it with one OS release. The OS currently used on the nspire is one made for mininetbooks anyways, so it would take minimal effort.


Better yet, fb39, get an army of 81s with all their keypads hacked to talk to each other, and crack it.


Edit: Oh, btw I'm leaving on another trip, won't be back until tuesday night. Sorry!


I was thinking: if we used ndless, could we ever access the area of the memory to change the factor required? We could make our own rsa key and replace ti's (making a key takes like 3 seconds)