The Standing Invitation

Posts Tagged ‘Cryptography

Critical Factors

leave a comment »

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 Ns 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 ps and qs, factorising an N would take the combined computing power of the entire planet several billion years.


Simon Singh, The Code Book

At the time of writing, the largest known prime was 243112609 – 1. The number can be found written out fully here.


Written by The S I

August 27, 2011 at 11:59 pm