The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
Let’s go to Wolfram Alpha and see if we can get them to do the heavy lifting.
My query:
largest prime factor of 600851475143
The answer?”
6857
It turns out finding the answer to this one is not very hard. If you recall,however, the reason I’m doing these problems is not just to find solutions. Solutions are easy. I’m trying to find a deeper meaning in these problems specifically and in these math topics in general.
So the bigger question is “Why do we care about prime factors?”.
Prime numbers, of course, are those whole numbers that can only be divided by themselves and 1. Prime factors are the factors of any number that happen to be prime. So is there something special about primes apart from their indivisibility?
It turns out that there’s a practical use for prime factors and that’s in cryptography (from the Greek for “secret writing”). This is the field that deals with (generally speaking) encoding and decoding messages. If you’ve ever bought something online, then the transaction was encrypted using some form of cryptographic protocol.
Here’s the thing: encrypting or decrypting requires a key. Since we’re talking about computers here, the key is essentially a number. Also, to make it harder for would-be attackers to guess your key, it needs to be a really, really, REALLY big number. I mean, I’m talking huge. Just imagine the biggest number you can think of. An encryption key is bigger. As big as this, for example:
The really good encryption, the kind that you use to buy that salad spinner on Amazon.com uses two keys, one public and one secret. The public key is an enormous number like the one pictured above. The secret key consists of the two prime numbers that are the factors of the public key. Obviously if someone could easily get hold of both sets of keys, the game is over for any transactions encrypted using those keys. So if you already have the public key (that’s why it’s called the public key after all), why not just pull out the two prime factors?
It turns out that calculating prime factors is part of a class of mathematical problem known as NP, which stands for Nondeterministic Polynomial. These are problems whose answers are easy to verify but hard to calculate.
The classic example of an NP problem is The Traveling Salesman. Here’s how it works:
Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?
Now if we start with a list of two cities, we can answer this question very quickly. However, as we add cities, the problem gets much harder much faster. Simply put, we have to check every possible combination of routes so the solution takes longer and longer the more cities we have to visit.
That’s why this works. Calculating prime factors becomes much, much harder as the number you’re factoring gets bigger. The ‘master key’ we’re talking about here is SO huge that figuring out its prime factors is nearly impossible in any kind of reasonable time (we’re talking centuries here). Add to that the fact that the keys can be set to expire after a given period of time and they can also be cancelled at any time, cracking this kind of encryption is…well, let’s just say you should probably clear your schedule.
So one of the big reasons that people spend a lot of time and money on working with prime factors is that if you could come up with a way of breaking numbers down into their prime factors more quickly, that would make cracking encryption much, much easier and as a result, much more likely to happen.
That would also mean the end of e-commerce as we know it.
We Hate Math 