Recommend
19 
 Thumb up
 Hide
18 Posts

BoardGameGeek» Forums » Everything Else » Chit Chat

Subject: Prime numbers. I finally get the attraction. rss

Your Tags: Add tags
Popular Tags: [View All]
¡dn ʇǝƃ ʇ,uɐɔ ı puɐ uǝllɐɟ ǝʌ,ı
Canada
Chestermere
Alberta
flag msg tools
Life lesson: Hamsters are NOT diswasher safe.
badge
There are 10 types of people-- those who understand binary, and those who don't.
Avatar
mbmbmbmbmb
Watching a youtube video about prime numbers and security encryption may not be your idea of a good use of time, but I’ve always wondered why people get so hot and bothered over huge prime numbers.
Why, if someone discovers a prime number that is 2 ^77232917 – 1, does everyone celebrate for a few days and then try to find out what the next biggest one is? Surely we have enough?

That’s a really big number, by the way. For comparison, just 2 ^56 = 72,057,594,037,927,936.
I know that isn’t a prime number, since it divides by 2, and even just subtracting 1 doesn’t make it prime, because then it would end in 5 and that is thus divisible by 5.

But as a hypothetical example, it still helps to explain things. 72,057,594,037,927,935 is still a very large number.
If I asked you to divide it by 5, when you pull out your calculator and tell me what the answer is, it would only take you a few seconds.
If I asked you to find all of its possible factors, though, you’d be a while. There are 256 ways to multiply whole numbers together and get that answer. If it were a prime number, then there would only be one answer (1 x the number itself) and you’d take a long time with your calculator to verify that.

To make this easier to understand, here is the example demonstrated in the video.
Is 13 a prime number? Test it out: 13/2 is not a whole number. 13/3 is not a whole number. Etc.
In mere moments you can say with certainty that it is. And that the prime number before it is 11.
Now multiply those two prime numbers together. You’ll get 143. It can be discovered in a second.

If I ask you, instead, to find the only two numbers that make up 143 when multiplied together—other than 1 x 143, which is obviously discounted—then it takes you a fair bit longer to figure that out. Especially when using the “brute force” method of checking every number to see if the result is whole (143/2, 143/3, 143/4…).

It turns out that multiplying any 2 numbers together is easy but dividing all of the factor possibilities into the sum, to find those two unique numbers, takes a lot longer.
And that is the important bit.
___________________________________________________________________

So then. What if you are a bank, and they need to make sure that access to your account is secure?
They tell you that your ID number is 13, and your access number is 11. If you can provide those two numbers to them then the bank can check on it easily, because they secretly know that your actual secure access number is 143.
And there is only one way to get that, so only you can be 13 x 11.

If a computer hacker ever found out what the bank’s secure codes were, then they could work back and find out that 13 x 11 is the one identity for 143. Now if they find out that you are #13, they know your access code.
Obviously there are a lot more than a dozen people who use the bank, so each person needs a unique ID and a unique access key and the bank has to store, and keep secret, all of the secure access “products” of those numbers.
So you’ll need a lot of bigger numbers to do that.

That’s why 72,057,594,037,927,935 is a huge number to you and me, but not as much to a computer.
So let’s say that you write a computer program to find out what those 256 factors are. Once the program is written—and it can be as simple as dividing the original number by a continuous series of smaller prime numbers, to see if you get a whole number result—then that calculation will take the computer several microseconds to finish, but you’d have results practically instantly. Having 256 ways to access the same number is not secure so even though it is big, it isn’t unique enough.

If the actual product was two large prime numbers multiplied together, then that is far more secure, as long as those numbers are big enough to slow down a computer. Having to check on 2 ^77232917 – 1 possibilities would take a computer years to accomplish. Decades if you don’t have a supercomputer with specialized software.
21 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Wendell
United States
Yellow Springs
Ohio
flag msg tools
Si non potes reperire Berolini in tabula, ludens essetis non WIF.
badge
Hey, get your stinking cursor off my face! I got nukes, you know.
Avatar
mbmbmbmbmb
A prime post, indeed
9 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Plaid Dragon
United States
Austin
Texas
flag msg tools
badge
Avatar
mbmbmbmbmb
Prime response....
4 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Mystery McMysteryface
United States
Florida
flag msg tools
Avatar
mbmbmbmbmb
Uh.....o..kay. ?

Mabby, you did something I never thought possible--you completely disappointed me. soblue
4 
 Thumb up
0.02
 tip
 Hide
  • [+] Dice rolls
Geeky McGeekface
United States
Manassas
Virginia
flag msg tools
designer
badge
Best hobby, with the best people in the world. Gaming is the best!
Avatar
mbmbmbmbmb
Math is a harsh mistress, MMB.
10 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Andy Andersen
United States
Michigan
flag msg tools
badge
Avatar
mbmbmbmbmb
Math. You can't live with it, you can't live without it.
3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Serious? Lee
United States
Coppell
Texas
flag msg tools
badge
Lost in thought.
Avatar
mbmbmbmbmb
EgorjLileli wrote:
Uh.....o..kay. ?

Mabby, you did something I never thought possible--you completely disappointed me. soblue

Why? He wasn't being irrational at all.
8 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Kyle
Canada
Toronto
flag msg tools
Show me something that beats a natural 20 and I'll show you hateful lies.
badge
We've taken care of everything...
Avatar
mbmbmbmbmb
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Thomas Decru
Belgium
flag msg tools
Avatar
MABBY wrote:
It turns out that multiplying any 2 numbers together is easy but dividing all of the factor possibilities into the sum, to find those two unique numbers, takes a lot longer.
And that is the important bit.

Small caveat, but we are not sure about this part, we just assume it to be true. We don't really know that factorizing is a hard problem, it may be that mankind just hasn't found how to solve it efficiently. Actually, anyone who could prove that it is a hard problem (and this can be made mathematically very precise) would win $1,000,000 from the Clay Mathematics Institute.

Moreover, once we got to new kinds of computer models like quantum computers, we already know it can be efficiently done.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Mystery McMysteryface
United States
Florida
flag msg tools
Avatar
mbmbmbmbmb
Larry Levy wrote:
Math is a harsh mistress, MMB.


I love Math, but not his OP!! shake

There is such a thing as too much Math.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Andy Leber
Canada
Orillia
ON
flag msg tools
Yin
badge
Yang
Avatar
mbmbmbmbmb
Spamz wrote:
MABBY wrote:
It turns out that multiplying any 2 numbers together is easy but dividing all of the factor possibilities into the sum, to find those two unique numbers, takes a lot longer.
And that is the important bit.

Small caveat, but we are not sure about this part, we just assume it to be true. We don't really know that factorizing is a hard problem, it may be that mankind just hasn't found how to solve it efficiently. Actually, anyone who could prove that it is a hard problem (and this can be made mathematically very precise) would win $1,000,000 from the Clay Mathematics Institute.

Moreover, once we got to new kinds of computer models like quantum computers, we already know it can be efficiently done.


Hmm, I don't even understand this. If we have to prove it's hard, then it's hard. Just because one day it might be easy doesn't mean it isn't hard today.

Was it then easy to make an automobile in medieval times? Imperfect example I guess because it required tools, and not just the mind. But still, it almost seems like trying to prove a negative.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Thomas Decru
Belgium
flag msg tools
Avatar
Holmes108 wrote:
Spamz wrote:
MABBY wrote:
It turns out that multiplying any 2 numbers together is easy but dividing all of the factor possibilities into the sum, to find those two unique numbers, takes a lot longer.
And that is the important bit.

Small caveat, but we are not sure about this part, we just assume it to be true. We don't really know that factorizing is a hard problem, it may be that mankind just hasn't found how to solve it efficiently. Actually, anyone who could prove that it is a hard problem (and this can be made mathematically very precise) would win $1,000,000 from the Clay Mathematics Institute.

Moreover, once we got to new kinds of computer models like quantum computers, we already know it can be efficiently done.


Hmm, I don't even understand this. If we have to prove it's hard, then it's hard. Just because one day it might be easy doesn't mean it isn't hard today.

Was it then easy to make an automobile in medieval times? Imperfect example I guess because it required tools, and not just the mind. But still, it almost seems like trying to prove a negative.

You are correct that proving this is similar to proving a negative. From a mathematical point of view, that's definitely not an impossibility though. The phrase "if we have to prove it's hard, then it's hard" is wrong however. Because hard in this instance has a very exact mathematical meaning. There's an entire field dedicated to study the complexity of such problems, and there's a reason why there's a million dollar reward attached to one of the more prominent unanswered questions.

The thing I was getting at however, is that it's technically possible for someone to write an efficient algorithm tomorrow on a single piece of paper, and with that compromise the security of a lot of protocols (including bank accounts). Now the vast majority of scientists in that field believe that no such thing can/will happen, and that it will always be a hard problem, but it is nothing more than a conjecture at this time. Your analogy fails because automobiles would be a technological advancement, and it would take decades to adjust roads, infrastructure, distribute cars, etcetera. Solving prime factorization would have a lot of downsides attached to it in the short term by for example causing a massive amount of security breaches (both of financial and other nature).

Anyway, this was just a nuance to the original post saying "It turns out that..."
6 
 Thumb up
0.25
 tip
 Hide
  • [+] Dice rolls
Matt
United States
Central Coast
California
flag msg tools
0110100110010110
badge
Avatar
mbmbmbmbmb
Holmes108 wrote:
Was it then easy to make an automobile in medieval times? Imperfect example I guess because it required tools, and not just the mind. But still, it almost seems like trying to prove a negative.


The analogy of this today is quantum computing. Some security experts are concerned that if quantum computers with large computing storage (qubits) are perfected, they might be able to crack these large factoring problems almost immediately. Goodbye, internet security.

(Quantum computing is a pretty deep rabbit-hole, too. But it's pretty cool!)

Your application of the idea to "proving factoring is hard" is interesting. We don't know if factoring is hard or easy, but right now, yes, it's very difficult. However, once somebody finds an easy way to solve it the problem will ALWAYS be easy, and that's what worries people.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Geeky McGeekface
United States
Manassas
Virginia
flag msg tools
designer
badge
Best hobby, with the best people in the world. Gaming is the best!
Avatar
mbmbmbmbmb
EgorjLileli wrote:
Larry Levy wrote:
Math is a harsh mistress, MMB.


I love Math, but not his OP!! shake

There is such a thing as too much Math.



I have no idea what you're talking about. So just imagine there's a picture of a bunny with a pancake on its head.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Matt
United States
Central Coast
California
flag msg tools
0110100110010110
badge
Avatar
mbmbmbmbmb
Okay, I can't resist. Aside from the applications to cryptography, the primes are really freaking amazing in their own right.

To a 'math-y' person like me, it is earth-shatteringly cool that they emerge from such a simple set of rules (multiplication over the positive integers), and such a simple question ("in how many ways can you represent a given number as the product of other numbers?"), and yet they resist any attempts to find basic patterns in them or answer very simple questions about them.

Any time you try to study something interesting about primes you end up following in the footsteps of some true mathematical giants, and encountering some problems that are extremely easy to state, but somewhere between "terrifyingly difficult" and "impossible" to solve.

And the kicker is that many of those questions have a brute force way to solve them, ("just divide be every number up to q") but those methods are SO impractical (the universe will end in heat death before you could finish) that they really aren't considered "solutions."

I have SO many books on my bookshelf that deal with number theory, prime factorization, and related topics, and it isn't even close to my area of specialization.

Primes rule!
4 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
I like board games more than most people.
United States
Northlake
Illinois
flag msg tools
badge
When I die I want people to look at the condition of my games and say, "Man, he really played these alot."
Avatar
mbmbmb
I have an infinite number of monkeys and an infinite number of computers.

Nothing is hard for me (except cleaning up monkey crap.)
4 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Geeky McGeekface
United States
Manassas
Virginia
flag msg tools
designer
badge
Best hobby, with the best people in the world. Gaming is the best!
Avatar
mbmbmbmbmb
Might I suggest an infinite number of Clorox Wipes?
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
jos horst
Netherlands
groningen
groningen
flag msg tools
mbmbmbmbmb
kjamma4 wrote:
I have an infinite number of monkeys and an infinite number of computers.

Nothing is hard for me (except cleaning up monkey crap.)

All it takes is to train a finite fraction of your monkey population to do the cleaning up.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.