Mathematicians found the prime factors of a 307 digits number

May 21, 2007 14:51 GMT  ·  By

Mathematics is not so easy, once you get past the "exact change" problem and the yearly taxes. Here's a mathematical record that might sound simple to achieve, until you try it.

An international team of scientists have performed a computational "Herculean Task" and finally found the prime factors of a well-known, hard-to-factor number that is a whopping 307 digits long.

The scientists had been using computer clusters from three institutions, the EPFL, the University of Bonn and NTT in Japan, for 11 months, trying to solve this mathematical problem.

"This is the largest 'special' hard-to-factor number factored to date," explains EPFL cryptology professor Arjen Lenstra. Special numbers have a special mathematical form, close to a power of two. This is a real breakthrough that will most likely draw the attention of information security experts that will start thinking about changing the current encryption methods.

RSA encryption, named after the three individuals who devised the technique (Ronald Rivest, Adi Shamir and Leonard Adleman), takes advantage of the fact that factoring a number, meaning dividing it into its prime components, is extremely difficult.

Encryption methods like this one use a large composite number, usually 1024 bits in size, created by multiplying together two 150-or-so digit prime numbers, so that only the one who knows the two numbers has the encryption key that allows him or her to access the information.

Everybody uses these encryption applications, since nobody ever succeeded at factoring these huge numbers. At least not yet. The most recent factoring record is RSA200, a 200-digit 'non-special' number whose two prime factors were identified in 2005 after 18 months of calculations that took over a half century of computer time.

Since it's much more difficult to factor a number made up of two huge prime numbers (like the RSA method), it seems that for now the standard is still secure, but the experiment has proved, at least in theory, that this 1024 bits encryption method is not such a tough nut to crack, after all.