¡dn ʇǝƃ ʇ,uɐɔ ı puɐ uǝllɐɟ ǝʌ,ı
Canada Chestermere Alberta
Life lesson: Hamsters are NOT diswasher safe.
There are 10 types of people those who understand binary, and those who don't.

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.

Wendell
United States Yellow Springs Ohio
Si non potes reperire Berolini in tabula, ludens essetis non WIF.
Hey, get your stinking cursor off my face! I got nukes, you know.

A prime post, indeed

Plaid Dragon
United States Austin Texas

Prime response....

Mystery McMysteryface
United States Florida

Uh.....o..kay. ?
Mabby, you did something I never thought possibleyou completely disappointed me.

Geeky McGeekface
United States Manassas Virginia
Best hobby, with the best people in the world. Gaming is the best!

Math is a harsh mistress, MMB.

Andy Andersen
United States Michigan

Math. You can't live with it, you can't live without it.

Serious? Lee
United States Coppell Texas
Lost in thought.

EgorjLileli wrote: Uh.....o..kay. ? Mabby, you did something I never thought possibleyou completely disappointed me. Why? He wasn't being irrational at all.

Kyle
Canada Toronto
Show me something that beats a natural 20 and I'll show you hateful lies.
We've taken care of everything...




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.

Mystery McMysteryface
United States Florida

Larry Levy wrote: Math is a harsh mistress, MMB.
I love Math, but not his OP!!
There is such a thing as too much Math.

Andy Leber
Canada Orillia ON
Yin
Yang

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.



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..."

Matt
United States Central Coast California
0110100110010110

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 rabbithole, 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.

Geeky McGeekface
United States Manassas Virginia
Best hobby, with the best people in the world. Gaming is the best!

EgorjLileli wrote: Larry Levy wrote: Math is a harsh mistress, MMB. I love Math, but not his OP!! 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.

Matt
United States Central Coast California
0110100110010110

Okay, I can't resist. Aside from the applications to cryptography, the primes are really freaking amazing in their own right.
To a 'mathy' person like me, it is earthshatteringly 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!

I like board games more than most people.
United States Northlake Illinois
When I die I want people to look at the condition of my games and say, "Man, he really played these alot."

I have an infinite number of monkeys and an infinite number of computers.
Nothing is hard for me (except cleaning up monkey crap.)

Geeky McGeekface
United States Manassas Virginia
Best hobby, with the best people in the world. Gaming is the best!

Might I suggest an infinite number of Clorox Wipes?

jos horst
Netherlands groningen groningen

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.


