Search :
Summer 1994

Research Magazine > ARCHIVE > Summer 94 > Article

Divide and Conquer
by David Hart

When mathematicians say "big," they mean BIG. Ross Perot's paycheck? Child's play. After all, you can write down Perot's net worth in only 10 digits. For mathematicians, the largest known prime number is really BIG: (2ë859,433)-1. It would take about 45 pages to write its 258,716 digits. Now that's big.

When you deal with numbers that big, up in the neighborhood of infinity, even the seemingly simple questions you asked in grade school become enormously complex.

For instance, is a number prime? If not, what are its factors? A prime number, of course, is a number that is divided evenly only by 1 and itself, and there are lots of them -- infinitely many, to be exact. The Greek mathematician Euclid proved this more than 2,000 years ago. If a number has factors other than 1 and itself, it's called composite.

Since prime numbers are the building blocks of all other numbers, it's no wonder mathematicians like UGA's Carl Pomerance and Andrew Granville spend time pondering them.

Prime numbers, which Granville studies, are important in modern data encryption algorithms that can be used to encode confidential bank transactions. Pomerance, studies "smooth numbers" -- very composite numbers, so to speak. They are composites with lots of small prime factors, and they can be used to crack computer codes.

"Until recently, smooth numbers were considered little more than a curiosity," said Enrico Bombieri of the Institute for Advanced Study in Princeton. "Professor Pomerance has shown quite effectively that they play a significant role in mathematics."

"Even though  [smooth numbers] have been studied for a good part of this century, within the past 15 years they've found a lot of applications," Pomerance said. "In particular, they've found applications in factoring algorithms."

Granville, on the other hand, seeks prime numbers among the more numerous composites. Granville and Dr. John Friedlander of the University of Toronto discovered you might not always find primes where you'd expect.

The question they posed was: How large a range of numbers should you look at to be sure it contains some primes? Mathematicians had agreed on the right size for several hundred years, so it was a big surprise when, in 1985, UGA math professor Helmut Maier showed that rarely, yet infinitely often (which only makes sense in the logic of infinity), this expectation was wrong.

"It had been thought  Maier's [idea] was very isolated," Granville said. "We realized you can apply it all over the place."

Granville and Friedlander applied this realization to work by Bombieri, who was awarded the Fields Medal -- the math equivalent of the Nobel Prize -- for showing that primes almost always occur within the expected range of numbers. Since it was almost always true, no one expected any exceptions. By applying Maier's idea, Granville and Friedlander proved these expectations wrong.

Prime numbers and smooth numbers came together when Granville, Pomerance and Associate Professor W.R. "Red" Alford collaborated to solve an 80-year-old problem: Are there infinitely many Carmichael numbers -- certain composites that masquerade as primes? There are, the trio proved in 1992.

"Smooth numbers were used in the proof," Pomerance said. "We considered prime numbers such that one less than the prime was smooth. It turns out that if we used  [such primes], then it was relatively simple to show that they could multiply together to produce Carmichael numbers."

On the heels of that work, they have described how Carmichael-like numbers can be constructed to trick "lazy" computer algebra programs. These programs always use the same conditions to test prime numbers, so it's possible to build numbers that slip by.

"What we do is we show that  [these programs] really are junk; in fact, there are numbers that are not prime that those computer languages will say, `This is a prime,'" Granville said.

Prime numbers and smooth numbers came together again at this year's International Congress of Mathematicians in Zurich, where Granville and Pomerance were invited to speak about their work.

"It is very rare to have two speakers in closely related fields from the same university, and this in itself shows the high degree of recognition in international circles obtained by the number theory group at the University of Georgia," Bombieri said.

Now, does all this affect, say, Ross Perot's checkbook? Not directly, at least not yet. However, you never know when such basic research will add up to something big.

"People studied  [number theory] for over 2,000 years just for it's own sake, and then some idiot goes and makes it practical," Granville quipped. "And now we're in hot demand and half our graduate students are funded by the National Security Agency because they need mathematicians."

-For more information go to http://www.math.uga.edu/~red/ or e-mail red@math.uga.edu or http://www.math.uga.edu/~andrew/ and andrew@math.uga.edu or http://www.math.uga.edu/~carl/ and carl@math.uga.edu

Return to Summer 1994 Index

Research Communications, Office of the VP for Research, UGA
For comments or for information please e-mail the editor: rcomm@uga.edu
To contact the webmaster please email: ovprweb@uga.edu