# A mighty number falls

##### May 21, 2007

Mathematicians and number buffs have their records. And today, an international team has broken a long-standing one in an impressive feat of calculation.

On March 6, computer clusters from three institutions – the EPFL, the University of Bonn and NTT in Japan -- reached the end of eleven months of strenuous calculation, churning out the prime factors of a well-known, hard-to-factor number that is a whopping 307 digits long.

"This is the largest 'special' hard-to-factor number factored to date," explains EPFL cryptology professor Arjen Lenstra. (The number is 'special' because it has a special mathematical form -- it is close to a power of two.) The news of this feat will grab the attention of information security experts and may eventually lead to changes in encryption techniques.

Although it is relatively easy to identify huge prime numbers, factoring, or breaking a number down into its prime components, is extremely difficult. RSA encryption, named for the three individuals who devised the technique (Ronald Rivest, Adi Shamir and Leonard Adleman), takes advantage of this. Using the RSA method, information is encrypted using a large composite number, usually 1024 bits in size, created by multiplying together two 150-or-so digit prime numbers. Only someone who knows those two numbers, the "keys", can read the message. Because there is a vast supply of large prime numbers, it's easy to come up with unique keys. Information encrypted this way is secure, because no one has ever been able to factor 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.

The international team factored the current 307-digit behemoth using the "special number field sieve," a method devised in the late 1980s by Lenstra (then at Bellcore), his brother Hendrik, then a professor at UC Berkeley, English mathematician John Pollard and Mark Manasse from DEC. The 11-month job took a century of computer time.

A feat like this would have been unthinkable back in 1990 when Lenstra started applying number theory and distributed computing to the task of breaking factoring records. Increased computer power and refined computational techniques have raised the bar, and will continue to do so. "We have more powerful computers, we have come up with better ways to map the algorithm onto the architecture, and we take better advantage of cache behavior," Lenstra explains.

Is the writing on the wall for 1024-bit encryption" "The answer to that question is an unqualified yes," says Lenstra. For the moment the standard is still secure, because it is much more difficult to factor a number made up of two huge prime numbers, such as an RSA number, than it is to factor a number like this one that has a special mathematical form. But the clock is definitely ticking. "Last time, it took nine years for us to generalize from a special to a non-special hard-to factor number (155 digits). I won't make predictions, but let's just say it might be a good idea to stay tuned."

Source: Ecole Polytechnique Fédérale de Lausanne

## Recommended for you

#### One percent of the population is responsible for 63 percent of violent crime convictions

Dec 06, 2013

The majority of all violent crime in Sweden is committed by a small number of people. They are almost all male (92%) who early in life develops violent criminality, substance abuse problems, often diagnosed with personality ...

#### Study: The effects of school board makeup on student performance

Dec 06, 2013

School boards are one of the foundations of the American educational system, yet little research exists on their effects on student performance. A University of Kansas professor has published a study showing that when a school ...

#### Discovery of partial skeleton suggests ruggedly built, tree-climbing human ancestor

Dec 05, 2013

A human ancestor characterized by "robust" jaw and skull bones was a muscular creature with a gorilla-like upper body and more adaptive to its environment than previously thought, scientists have discovered.

#### Ancient 'fig wasp' lived tens of millions of years before figs

Dec 05, 2013

A 115-million-year-old fossilized wasp from northeast Brazil presents a baffling puzzle to researchers. The wasp's ovipositor, the organ through which it lays its eggs, looks a lot like those of present-day ...

#### A sudden interest in math: How teachers can motivate their pupils

Dec 05, 2013

The lack of interest in math or natural sciences is one of the most frequently voiced causes for concern in the debate surrounding education, at least in Germany. It has been seen time and again that pupils lose their enthusiasm ...

## More news stories

#### Human ancestor was less-chimp-like than thought: study

The last common ancestor of Man and Ape was not a knuckle-walking, tree-swinging hominid resembling today's chimpanzee, said a study Tuesday challenging some long-held theories of human evolution.

#### One percent of the population is responsible for 63 percent of violent crime convictions

The majority of all violent crime in Sweden is committed by a small number of people. They are almost all male (92%) who early in life develops violent criminality, substance abuse problems, often diagnosed with personality ...

#### New research will allow more reliable dating of major past events

Academics have developed a new method which will allow key past events to be dated more accurately.

#### Oldest hominin DNA sequenced

Using novel techniques to extract and study ancient DNA researchers at the Max Planck Institute for Evolutionary Anthropology in Leipzig, Germany, have determined an almost complete mitochondrial genome sequence ...

#### Blacks happier at work than whites despite fewer friends, less autonomy

Despite working in more routine and less autonomous jobs, having fewer close friends at work, and feeling less supported by their coworkers, blacks report significantly more positive emotions in the workplace than whites, ...

#### New consoles, online games to keep market soaring to 2017

The global video gaming market is set to grow 11.1 percent a year until 2017, boosted by a new generation of consoles and the increasing popularity of online games, according to IDATE digital research and ...

#### Indian government wakes up to risk of Hotmail, Gmail

Worried by US spying revelations, India has begun drawing up a new email policy to help secure government communications, but the man responsible for drafting the rules still regularly uses Hotmail.

#### Peculiar traffic routes suggest hijacking headaches

(Phys.org) —Findings from Internet intelligence company Renesys sound an alert to a hijacking practice in the form of traffic misdirection on the Internet. A November 19 blog on the Renesys site has since ...

#### Calif. health exchange shares data without consent

The California health exchange is giving the names of tens of thousands of consumers to insurance agents without their knowledge.

#### Gene therapy scores big wins against blood cancers

In one of the biggest advances against leukemia and other blood cancers in many years, doctors are reporting unprecedented success by using gene therapy to transform patients' blood cells into soldiers that ...