## Posts Tagged ‘**Factorisation**’

## Critical Factors

Prime numbers are the building blocks of integers. Any positive integer is either the product of two or more prime numbers, or a prime number itself.

6 is the product of 2 and 3.

943 is the product of 23 and 41.

44,467 is the product of 53 and 839.

These numbers each took about ten seconds to calculate – I just drew prime numbers out of a list and multiplied them together.

So tell me: which pair numbers did I multiply together to get the number 47,124,299?

There is only one answer to this question, and in one sense it is easy to find: simply divide 47,124,299 by each prime number in turn; if the result is itself prime, there is the answer. But armed with the same tool as me – a pocket calculator – it would take you days to find the answer to a number I generated in seconds. If you and I were in a race, I would have a clear advantage – and the bigger the primes I chose, the harder your job would be.

The fast factorisation of numbers has been a problem for thousands of years, and we still aren’t very good at it. Granted, my computer could find the prime factors of 47,124,299 in a nanosecond or two, but this is a measure of computational speed, not cleverness. It is still exhaustively checking off the primes, one by one, just as someone would have done on paper a thousand years ago.

This asymmetry is exploited in the area of public-key cryptography, one of the most powerful forms of encryption that exists that doesn’t involve weird quantum effects of spinning electrons.

If you want to use public-key cryptography, you choose two large prime numbers *p* and *q* – gigantic numbers, hundreds of digits long – and multiply them together to create an even bigger number, *N*. You would then be free to advertise this number *N* to anyone who wants it; one might list different people’s *N*s in something like a phone book, free for people to look up.

To send you a message *M*, I would have to look up your *N*, and perform a simple calculation involving *M* and *N*. The outcome of this one-way function is the encrypted message. This can then be transmitted to you, and nobody – *not even me* – could convert the encrypted message back to *M*.

The only person who can read the message is you, *because you know what p and q are*. You alone on Earth know the prime factors of *N*, and that means only you can perform the reverse maths that decrypts the message.

Of course, *N* is public, and anybody could work out *p* and *q* from *N* simply by exhausting the possible primes. As we have seen, this is simple, but time-consuming: at present sizes of commercially available *p*s and *q*s, factorising an *N *would take the combined computing power of the entire planet several billion years.

REFERENCES

Simon Singh, *The Code Book*

At the time of writing, the largest known prime was 2^{43112609} – 1. The number can be found written out fully here.