Purdue News

May 1997

Number crunchers zero in on record-large number

WEST LAFAYETTE, Ind. -- Purdue University researcher Samuel Wagstaff is directing scientists around the world in a game of mathematical "Jeopardy," using powerful computers to divide and conquer numbers that have more than 100 digits.

Results from the latest round, factoring a record-setting 167-digit number, may help simplify some mathematical theorems and help scientists develop secret codes for computer security.

"The fact that we can factor a number of this size shows that we can factor other numbers of that size," says Wagstaff, a professor of computer sciences. "Knowing the limits of such factorizations is essential to developing secure codes and ciphers."

Factoring a number involves finding two other whole numbers that can be multiplied together to form it. For example, five and seven are factors of 35.

Most people can easily identify the factors of numbers with two or three digits, says Wagstaff, who compares the process of finding factors to the popular television game show "Jeopardy," where players are given the answers and must guess what the questions are. In the example above, the answer is "35," and the question is "what is 7x5?"

"The interesting thing is, we play this game with numbers that have more than 100 digits," he says.

Wagstaff coordinates a worldwide effort to whittle away at these large numbers. The massive enterprise includes dozens of mathematicians and computer experts, hundreds of computers and thousands of machine hours.

The largest number ever to be factored previously had 162 digits and was solved in 1994.

The recently factored 167-digit number is from Wagstaff's "10 Most Wanted" list of some of the most challenging numbers to factor. Wagstaff says the list is comprised of "hard" numbers, those with no known factors that scientists already have spent thousands of hours trying to solve. Once the factors to a number are identified, the results are sent back to Wagstaff, who crosses the number off his list and adds a new one.

Wagstaff has been keeper of this list and other challenging numbers for more than 15 years. In 1983, he and four other mathematicians wrote a book on the subject. Though 90 percent of the book is filled with numbers and tables, it sold more than 1,000 copies and has been the best seller among more than 100 books on contemporary mathematics published by the American Mathematical Association.

"That's a lot of copies for an esoteric math book," Wagstaff says.

The book was updated in 1988, and Wagstaff is working to update a third edition, which will be available in one or two years.

The record-setting number is the last in a long series of numbers that are derived from the formula (3n - 1), where n is an odd number less than 350.

The abbreviated version of the 167-digit number looks like (3349 - 1)/2, which tells us that the number is derived by multiplying 3 times itself 349 times, subtracting 1 and dividing by 2. The full number reads
1637901955805366239217413015
4670449583923965684832704024
9837817092396946863513212041
5650964922608054197182470755
5797144568969073877772973038
883717449030628887379284041

Until recently, no one knew any factors for the number, Wagstaff says. By whittling away at the possible factors -- a process that required approximately 100,000 computer hours -- his international group found that the number is the product of an 80-digit number multiplied by an 87-digit number.

With a minimum of 80 digits, even the factors can be unwieldy. Wagstaff says the co-authors are scrambling to find a new format for the third edition of their book so that the factors can fit onto a single line of text.

"Non-mathematicians use hyphens to extend text onto a second line, but hyphens are minus signs in the mathematics world," he says.

Wagstaff says much of the interest in factoring large numbers stems from its practical application -- cryptography. Cryptography is the art of writing or deciphering messages in code.

He notes that one way cryptographers can create unbreakable codes is by multiplying two large numbers, such as 100 digits each, to get a number that is too large to factorize easily. Another way to develop codes is to use factorizations to develop secret keys to a code.

"In choosing keys for a code, you want to choose numbers that are large enough so that nobody can figure them out, but small enough so that you can encipher and decipher reasonably quickly," Wagstaff says. "Large numbers with two prime factors are ideal for developing such codes."

Factorizations of large numbers may be especially useful for one particular type of code, called the Rivest-Shamir-Adleman, or RSA, cryptosystem, whose security relies on the difficulty of factoring. The RSA code is used in electronic cash transactions and to sign contracts by electronic mail. It also can be used to send the key for another cipher or to authenticate a message.

In addition, Wagstaff says codes based on large factorizations will someday allow consumers to shop with an "electronic wallet," which will consist of a computer disk or a smart card that contains nothing but series of very large numbers coded to ensure that the electronic cash is spent only once. To pay for items, cards will be run through a store's computer, which will automatically deduct the proper amount.

"Charge cards are used a similar manner, but electronic cash can be used just like dollar bills, so you are not identified and there is no record that you spent the money," he says. "The coding from the large numbers serves a security purpose, so if you try to spend the money twice, codes from the two transactions can be combined to identify you."

The factorizations of large numbers also can be useful in discovering new mathematical theorems and properties, Wagstaff says.

"These numbers come up in solving all kinds of mathematical problems," he says. "For example, they can be used in proving that certain large prime numbers really are prime."

A prime number is one that can be evenly divided only by itself or the number one.

"If you have a very big prime number, like 1,000 digits, it is often difficult to prove it is a prime number. But if you can factor that number, minus one, into its prime factors, then you have proof that the number is prime," Wagstaff says.

He says that most of us learn to factor numbers in school using a "hit-or-miss" method, checking first to see if the number is divisible by two, and then working our way through a series of small prime numbers such as 3, 5, 7, and so on.

In the late 1960s, scientists began to develop better methods to approach such calculations. Using computers, researchers developed a series of algorithms, or sets of rules, to tackle large numbers.

For the past two years, Wagstaff has coordinated efforts among a group of mathematicians and computer experts who use an algorithm called the Number Field Sieve to factor large numbers. The Number Field Sieve is the first factoring algorithm to use higher mathematics, Wagstaff says.

Other principal researchers of the group are Marije Elkenbracht-Huizing of the Center for Science Computing in Amsterdam; Peter Montgomery of Microsoft Corp. in San Rafael, Calif.; Robert Silverman of RSA Inc. in Boston; and Richard Wackerbarth, a computer consultant in Austin, Texas.

In addition to the core group, the effort relies on volunteers from around the world who contribute the "spare time" of a large number of workstations to perform the necessary calculations. Each volunteer controls anywhere from 10 to 100 computers. By dividing the work among many computers, calculations can be carried out in a fraction of the time that would be needed to perform the task on one computer, Wagstaff says.

The volunteers run a computer program written by Montgomery and Silverman to carry out various computations. They then send the partial results to Wackerbarth in Texas, who forwards them to Wagstaff, who does more processing on the results at Purdue. Wagstaff then sends his information to Elkenbracht-Huizing in Amsterdam, who completes the job.

Wagstaff and his group are now working to close in on some of the other "most wanted" numbers, which range from 118 digits to 195 digits.

"At this point, a 200-digit number still looks out of reach," he says. "But within the next few years, we will be able to crack such numbers."

Source: Samuel Wagstaff, (765) 494-6022; e-mail, ssw@cs.purdue.edu
Writer: Susan Gaidos, (765) 494-2081; e-mail, susan_gaidos@purdue.edu
Purdue News Service: (765) 494-2096; e-mail, purduenews@purdue.edu

Photo Caption:

Purdue computer expert Samuel Wagstaff shows how a 167-digit number can be divided into its two prime factors. He led a worldwide effort to factor the record-setting number. (Purdue News Service Photo by David Umberger)

Color photo, electronic transmission, and Web and ftp download available. Photo ID: Wagstaff/Number