When two young mathematicians announced last week they had cracked a 155-digit number that could be used to ferry top-secret coded messages over telephone lines, many diplomats, spies and wheeler-dealers who use cryptographic systems probably felt a pang of dread.
Such systems rely on mathematical processing of very large numbers to make it hard for eavesdroppers to find out what is being said. In particular, one of the most elegant and secure cryptosystems in the world -- the so-called RSA Cryptosystem -- is based on the fact that it is almost impossible, even with extremely powerful computers, to break really monster numbers down into their component parts.
Those component parts are called prime numbers. Such numbers can be divided evenly only by 1 and themselves, like 3, 5, 7, 11 and so on. The right prime numbers can be used as keys to decipher messages written on the basis of a particular enormous number. If calculating these numbers becomes easy, codes used worldwide to hide military and business secrets suddenly could become transparent.
But number theorists, startled by the feat of Arjen Lenstra of Bellcore and Mark Manasse of Digital Equipment Corp., focused this week on the very particularity of the number they cracked. In the view of many experts, the pair's technique may have worked with that number because it is a special, well-known so-called "rarefied" number, called "the ninth Fermat" after the 17th-century French lawyer and mathematician Pierre Fermat who put it together. These experts say the technique might not work with other jumbo numbers.
"It's an absolutely ridiculous assertion" to say the pair's accomplishment threatens the RSA Cryptosystem and other such coding techniques, said Jim Bizdos, president of California-based RSA
Security Corp. He challenged Len- stra and Manasse to tackle a number of his choosing. "I would be happy to discuss a large bet if these two gentlemen are interested," he said.
The process Lenstra and Manasse used is called factoring -- finding the prime numbers that can be multiplied together to produce the large figure. The factors of 15, for example, are 3
5. The factors of 105 are 3
7. Monstrous Calculations
Finding the factors of small numbers is work for schoolchildren and pocket calculators. But because there are infinitely more prime numbers than there are atoms in the universe, finding the factors of big numbers becomes maddeningly difficult, if not impossible, even with the brute force of today's largest supercomputers.
But Lenstra and Manasse's number was a special case. The ninth Fermat has a well-known structure: it is composed of a small number, multiplied by itself many times and then lowered by 1.
Because Lenstra and Manasse knew this, they had clues to the puzzle. They used a new method of factoring, called the number field sieve, which was developed by British mathematician John Pollard and then modified by Lenstra and his brother, Hendrik Lenstra of the University of California at Berkeley. The number field sieve proved especially adept at factoring numbers like the ninth Fermat.
Even so, Lenstra and Manasse had help from 200 researchers around the world, who volunteered the services of about 1,000 computers. These ground away on the puzzle by remote control for months while their masters slept, or at any time the computers were not otherwise in use. Still, solving the problem took the equivalent of 275 years of computing time.
Ronald Rivest of the Massachusetts Institute of Technology, who invented the RSA cryptosystem with MIT colleagues Adi Shamir and Leonard Adleman in the late 1970s (RSA stands for their last initials), said last week that "the practical ramifications" of the Lenstra and Manasse feat "were nonexistent." How an RSA Code Works
The RSA cryptosystem is built upon one idea: the practical impossibility of factoring most jumbo numbers. The system works like this:
Bankers, diplomats, scientists, warriors and spies do not like other people eavesdropping on their communications. So they encrypt their messages. They start by choosing known prime numbers and multiplying them to get a 155-digit number, an easy process compared to the reverse operation. That becomes what is called the "public" key. The "secret" key is derived from the prime numbers that are factors of the 155-digit number.
First, the sender uses a computer to turn the message into a string of numbers, such as A = 01, B = 02, C = 03. The message also can be turned into a string of binary numbers, which makes computers happy. Then the sender uses the public key of the intended receiver and a standard formula to encrypt the numbered message. To decode the "cryptotext" the recipient needs to know the prime number factors of the public key.
Many users of RSA choose public keys that are 155 digits long, because a number with 155 decimal places is equivalent to a number with 512 bits, which is easy for computers to handle. But again, there are many, many prime numbers that can be factors of many different 155-digit numbers.
Most crypto-experts say the RSA system remains secure. "I'm willing to put my money where my numbers are," Bidzos said.
Lenstra and Manasse may take the bet that Bizdos offered and try to factor a number he provides. Lenstra believes their number field sieve may soon be generalized enough to do that as well as to pursue other quarry on mathematicians' "most wanted" list. Perhaps they will even crack the 129-digit number known as the "MIT Challenge," which was published in Scientific American 12 years ago, with a symbolic offer of $100 to anyone who could factor it.
"The $100 is still in the bank collecting interest," Rivest said. But even Rivest is resigned to the possibility that the MIT Challenge might soon be met. Lenstra and colleagues cracked a general 111-digit number last year and are busy now on a 116-digit number.
But a general number of 155 digits? Mathematicians have begun to shy away from the word "impossible."