As you can probably deduce, this is about RSA

Here's the idea. Instead of trying to find primes, what about eliminating many non-primes? the calculation is much faster, since, if you do it in a reasonable way, you are dividing an extremely large number by a fairly small one (probably max of 32768 or so, at least at first) instead of two extremely large ones.

Once you eliminate, say, 30-50% (not counting even numbers ) of all the non-primes, any method of testing would be much faster. Plus, you can manage it in a very community-friendly way, by having one computer test all of the numbers for one number as a factor, gradually moving up the list itself.

Here's an example with very low numbers, but expandable.

original list, 1-50
cut out evens (divide by two)
take lowest number on list (3) and divide all remaining, looking for non-decimal divisions
this gives 9, among others, that you then remove from the list
from there, you move to 5, being next on the list, knowing both 5 and 3 are primes.

Repeat until you reach the point that it would be better just to use the remaining numbers in an algorithm.

For a community-based version: Server has a database with all said numbers (it might be practical to start higher than one )
Server gets a request from a PC, sends lowest number and list.
Server gets another request, sends next lowest number and the same list (since the first results aren't back yet)
First returns results, server removes nonprimes from list (if the current lowest untested is nonprime, it bumps it to the next one, no point in dividing by nonprimes)
Second returns results, server removes any remaining nonprimes that were missed by the first, ignores those already removed.

What do you think?

I know it's been said before, but I'ma say it again:

It's mathematically impossible to find the primes for these numbers within our lifetimes using current hardware.

The idea of starting now would not work, you'd have barely made a dent by the time that hardware that could do this within a reasonable time exists. Chances are that we'll all be on to the prizm by then anyways.

It'd be less effort to break into TI and steal the keys.

At the risk of sounding dumb and annoying but what is this RSA and prime numbers and all that thing about? I tried to go through the other topic but didn't have time and got lost, I think. It was a while ago. So just thought I'd ask.

The nspire OS is signed with an RSA signature, the base of which is computed off of two very very large prime numbers. Get those prime numbers and you can compute your own, making your own OS for the nspire, but they're ridiculously unfathomably large.

Quote from: meishe91 on November 06, 2010, 02:33:31 am

At the risk of sounding dumb and annoying but what is this RSA and prime numbers and all that thing about? I tried to go through the other topic but didn't have time and got lost, I think. It was a while ago. So just thought I'd ask.

The nspire OS is signed with an RSA signature, the base of which is computed off of two very very large prime numbers. Get those prime numbers and you can compute your own, making your own OS for the nspire, but they're ridiculously unfathomably large.

What's an RSA signature? Just like the thing that keeps people from creating new OS's or hacking it or something?

RSA is a method of encrypting so that people who shouldn't know the answer don't. There are basically three classes of encryption methods: noncryptographic methods, such as the MD5 Hash, Weakly Cryptographic methods, such as SHA-1 which are suspected of being faulty, and strong cryptographic methods, such as RSA as well as ElGamal. When a method provides strong encryption, it is exceedingly difficult to break provided that it is used correctly. With RSA, you generate two large primes, then compute several additional numbers related to those primes and use those to encrypt the data such that no one who doesn't know the decryption key can reasonably decipher the message. TI, however, went overboard and used ridiculously large primes, making a brute force crack essentially impossible. The only real way to crack the code would be to exploit a flaw in the algorithm used to create it. Unfortunately, RSA is very secure and has been extensively tested over the years by some of the most knowledgeable people in the field.

Ah ok, thanks guys.

Aww....

So, if i found it I'm assuming you would accuse me of somehow getting it from TI?

If you found it and it worked, we wouldn't really care how you got it.

This.

Although I'd have my suspicions.