An international team of mathematicians announced in May that they had factored a 307-digit number—a record for the largest factored number and a feat that suggests Internet security may be on its last legs.
“Things are becoming less and less secure,” says Arjen Lenstra, a computer scientist at the École Polytechnique Fédérale (EPFL) in Switzerland, who organized the effort.
Messages in cyberspace are encrypted with a random 1,024-bit number generated by multiplying two large primes together. But if hackers using factorization can break the number into its prime multipliers, they can intercept the message. Factorization currently takes too long to be a serious threat, but that may soon change.
Lenstra and his colleagues chose the number (21,039 – 1), which weighs in at 1,017 bits—slightly less than the 1,024-bit numbers used to secure Internet messages. His team used the special number field sieve, a filtering method first suggested by John Pollard in 1988, to find the factors.
For a hacker using a single computer, the job would have required a hundred years of processing time. By sharing the load over about 500 computers, however, Lenstra and his collaborators reduced that time to six months.
Although Lenstra’s number is close in size to those used for online security, he estimates that it would be more than a thousand times as difficult to crack a random 1,024-bit number. He says it could happen in the next decade, though, in light of rapidly accelerating technology.
Go to the next story: 39. Plants Using Quantum Computers