Author Topic: Idea for prime finding....  (Read 12628 times)

0 Members and 6 Guests are viewing this topic.

Offline willrandship

  • Omnimagus of the Multi-Base.
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2953
  • Rating: +98/-13
  • Insert sugar to begin programming subroutine.
    • View Profile
Idea for prime finding....
« on: November 06, 2010, 01:01:47 am »
As you can probably deduce, this is about RSA :P

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 :P) 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 :P)
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?

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: Idea for prime finding....
« Reply #1 on: November 06, 2010, 02:17:05 am »
Server has a database with all said numbers

There happen to be about 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 or 1e154 numbers to store and search through.  Thats around 1e147 terabytes of memory to store all of these numbers.  This is some seriously huge amounts of data we are talking here.

Offline Netham45

  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2103
  • Rating: +213/-4
  • *explodes*
    • View Profile
Re: Idea for prime finding....
« Reply #2 on: November 06, 2010, 02:30:32 am »
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.
Omnimaga Admin

Offline meishe91

  • Super Ninja
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2946
  • Rating: +115/-11
    • View Profile
    • DeviantArt
Re: Idea for prime finding....
« Reply #3 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.
Spoiler For Spoiler:



For the 51st time, that is not my card! (Magic Joke)

Offline Netham45

  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2103
  • Rating: +213/-4
  • *explodes*
    • View Profile
Re: Idea for prime finding....
« Reply #4 on: November 06, 2010, 02:35:59 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.
« Last Edit: November 06, 2010, 02:41:33 am by Netham45 »
Omnimaga Admin

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: Idea for prime finding....
« Reply #5 on: November 06, 2010, 02:39:42 am »
As you can probably deduce, this is about RSA :P

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.

That method is known as the Sieve of Eratosthenes. It works, but it's one of the most inefficient ways to eliminate the primes. Basically, you're brute forcing the answer and RSA was designed to circumvent such methods.
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline meishe91

  • Super Ninja
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2946
  • Rating: +115/-11
    • View Profile
    • DeviantArt
Re: Idea for prime finding....
« Reply #6 on: November 06, 2010, 02:40:41 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?
Spoiler For Spoiler:



For the 51st time, that is not my card! (Magic Joke)

Offline Netham45

  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2103
  • Rating: +213/-4
  • *explodes*
    • View Profile
Re: Idea for prime finding....
« Reply #7 on: November 06, 2010, 02:43:05 am »
What's an RSA signature? Just like the thing that keeps people from creating new OS's or hacking it or something?

It's like a signature on a check, it just verifies that the OS came from TI, and hasn't been altered.

Also, some math fun:

Assuming that every single person on earth(using 6,697,254,041, what google returns) has a computer with 4GB of ram and a 250GB HDD, you'd have 1,701,102,526,414,000 MB of storage.

Based off of Bboy's calculations, you'd need
1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 MB of storage.

That isn't even including the totally overwhelming number of flops you'd need
« Last Edit: November 06, 2010, 02:48:19 am by Netham45 »
Omnimaga Admin

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: Idea for prime finding....
« Reply #8 on: November 06, 2010, 02:51:22 am »
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.
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline Netham45

  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2103
  • Rating: +213/-4
  • *explodes*
    • View Profile
Re: Idea for prime finding....
« Reply #9 on: November 06, 2010, 02:56:54 am »
There is a line between encryption and signing, though.

RSA can be used for encryption, but in this case, it's just used to verify that the OSes haven't been tampered with, or acting as signing them.

iirc, the OSes just have some sort of weird compression on them, no actual encryption.
Omnimaga Admin

Offline meishe91

  • Super Ninja
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2946
  • Rating: +115/-11
    • View Profile
    • DeviantArt
Re: Idea for prime finding....
« Reply #10 on: November 06, 2010, 02:58:29 am »
Ah ok, thanks guys.
Spoiler For Spoiler:



For the 51st time, that is not my card! (Magic Joke)

Offline Netham45

  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2103
  • Rating: +213/-4
  • *explodes*
    • View Profile
Re: Idea for prime finding....
« Reply #11 on: November 06, 2010, 03:01:33 am »
Ah ok, thanks guys.

no problem.


@willrandship, basically, any method there is right now would just take amazing amounts of resources that just don't exist.
Omnimaga Admin

Offline willrandship

  • Omnimagus of the Multi-Base.
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2953
  • Rating: +98/-13
  • Insert sugar to begin programming subroutine.
    • View Profile
Re: Idea for prime finding....
« Reply #12 on: November 07, 2010, 12:13:31 am »
Aww....

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

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: Idea for prime finding....
« Reply #13 on: November 07, 2010, 04:58:36 pm »
If you found it and it worked, we wouldn't really care how you got it.

EDIT: In fact, I would be happier if you got it from TI ;-)
« Last Edit: November 07, 2010, 04:59:06 pm by graphmastur »

Offline Netham45

  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2103
  • Rating: +213/-4
  • *explodes*
    • View Profile
Re: Idea for prime finding....
« Reply #14 on: November 08, 2010, 12:26:22 am »
If you found it and it worked, we wouldn't really care how you got it.

This. :P

Although I'd have my suspicions.
Omnimaga Admin