Why is it so hard to split a big number into its primes?

Splitting a big number into primes is hard because nobody knows a shortcut. Multiplying is easy, but going backwards, finding which primes were multiplied, seems to require searching. For small numbers you can just try dividing by 2, 3, 5 and so on up to the square root. For huge numbers, that search explodes: as the number of digits grows, the work for any ordinary computer rises drastically. No efficient method is known, though nobody has proved one can't exist.

The hardest cases are numbers made by multiplying two large primes of similar size. That's no accident: such numbers are the keys of RSA encryption. If someone found a fast way to factor, RSA would no longer be secure.

The best story is a magazine puzzle. In August 1977, Martin Gardner's column in Scientific American hid a message behind a 129-digit number. It held out until April 1994, when about 600 volunteers lent some 1,600 computers over the Internet to crack it. The secret message read: The Magic Words are Squeamish Ossifrage. By 2015, the same job took about a day and $30 of cloud computing.

The real threat may be quantum. In 1994 Peter Shor found an algorithm that would factor quickly on a quantum computer, but it may need machines with millions of qubits.