If you were asked to multiply the following two big prime numbers, you might find it a bit tiring to do by hand (although it is definitely achievable), and you could get an answer in a fraction of a second using a computer.
If on the other hand you were asked which two prime numbers were multiplied to get the following big number, you’d have a lot more trouble!
(If you do find the answer, let us know! We’d be very interested to hear about it!)
Creating an RSA code involves doing the multiplication above, which is easy for computers.
If we could solve the second problem and find the multiples for a big number, we'd be able to crack an RSA code.
However, no one knows a fast way to do that.
This is called a "trapdoor" function – it's easy to go into the trapdoor (multiply two numbers), but it's pretty much impossible to get back out (find the two factors).
So why is it that despite these two problems being similar, one of them is "easy" and the other one is "hard"?
Well, it comes down to the algorithms we have to solve each of the problems.
You have probably done long multiplication in school by making one line for each digit in the second number and then adding all the rows together.
We can analyse the speed of this algorithm, much like we did in the algorithms chapter for sorting and searching.
Assuming that each of the two numbers has the same number of digits, which we will call ("Number of digits"), we need to write rows.
For each of those rows, we will need to do around multiplications.
That gives us little multiplications.
We need to add the rows together at the end as well, but that doesn’t take long so lets ignore that part.
We have determined that the number of small multiplications needed to multiply two big numbers is approximately the square of the number of digits.
So for two numbers with 1000 digits, that’s 1,000,000 little multiplication operations.
A computer can do that in less than a second!
If you know about Big-O notation, this is an algorithm, where is the number of digits.
Note that some slightly better algorithms have been designed, but this estimate is good enough for our purposes.
For the second problem, we’d need an algorithm that could find the two numbers that were multiplied together.
You might initially say, why can’t we just reverse the multiplication?
The reverse of multiplication is division, so can’t we just divide to get the two numbers?
It’s a good idea, but it won’t work.
For division we need to know the big number, and one of the small numbers we want to divide into it, and that will give us the other small number.
But in this case, we only know the big number.
So it isn’t a straightforward long division problem at all!
It turns out that there is no known fast algorithm to solve the problem.
One way is to just try dividing by every number that is less than the number (well, we only need to go up to the square root, but that doesn’t help much!).
There are billions of billions of billions of numbers we need to check.
Even a computer that could check 1 billion possibilities a second isn’t going to help us much with this!
If you know about Big-O notation, this is an algorithm, where n is the number of digits – even small numbers of digits are just too much to deal with!
There are slightly better solutions, but none of them shave off enough time to actually be useful for problems of the size of the one above!
The chapter on complexity and tractability looks at more computer science problems that are surprisingly challenging to solve.
If you found this stuff interesting, do read about complexity and tractability when you are finished here!