# Priming for a lucky strike.

Priming for a lucky strike

Mersenne primes hold a special place in the never-ending pursuit of larger and larger prime numbers-numbers divisible only by themselves and 1. Expressed in the form 2p-1, where the exponent p itself is a prime number, Mersenne numbers have a structure that makes it relatively easy to check whether even enormous numbers truly can't be factored. The largest prime yet found-the 30th Mersenne prime-has 65,050 digits when p=216,091 (SN:9/28/85, p.199).

This week, two computer experts found the 31st Mersenne prime. But to their surprise, the newly discovered prime number falls between two previously known Mersenne primes. It occurs when p=110,503, making it the third-largest Mersenne prime known.

"To tell the truth," says Walter N. Colquitt of the Houston Area Research Center in The Woodlands, TEx., "I didn't expect to find anything." Colquitt, working with computer consultant Luther Welsh Jr. of El Toro, Calif., had written a computer program and organized a systematic search of Mersenne numbers in the hope of finding a record-breaking prime.

This time, because he had only a limited amount of time available on an NEC SX-2 supercomputer, Colquitt decided to run some smaller candidates to be sure that nothing had been missed in previous searches. Only Mersenne numbers with exponents up to 103,000 had been exhaustively searched in the past, says Colquitt. Later efforts had been "shotgun" affairs that covered only narrow ranges of large numbers. The new Mersenne prime falls within one of the gaps.

The supercomputer, running a program written completely in FORTRAN, took only about 11 minutes to confirm that 2110,503-1 is a prime number. "That's an incredibly fast time," says David Slowinski, formerly with Cray Research, Inc., in Minneapolis and now a student at Carnegie-Mellon University in Pittsburgh. "They (must) have some very good trick to get such a fast time." Slowinski himself has discovered several Mersenne primes and plans to check Colquitt and Welsh's result.

"We tried different multiplication algorithms," says Welsh. "The program, as it stands now, is fairly decent, although it's not as fast as it could be."

"If you're going to look for prime numbers," says Colquitt, "you're probably going to learn more about multiplication than you want to know. You also have to be systematic-and you have to be lucky and pray a little bit."

Are there more Mersenne primes lurking in the gaps? "I have absolutely no idea," says Colquitt. "Thousands of them are untested yet."

Mersenne primes hold a special place in the never-ending pursuit of larger and larger prime numbers-numbers divisible only by themselves and 1. Expressed in the form 2p-1, where the exponent p itself is a prime number, Mersenne numbers have a structure that makes it relatively easy to check whether even enormous numbers truly can't be factored. The largest prime yet found-the 30th Mersenne prime-has 65,050 digits when p=216,091 (SN:9/28/85, p.199).

This week, two computer experts found the 31st Mersenne prime. But to their surprise, the newly discovered prime number falls between two previously known Mersenne primes. It occurs when p=110,503, making it the third-largest Mersenne prime known.

"To tell the truth," says Walter N. Colquitt of the Houston Area Research Center in The Woodlands, TEx., "I didn't expect to find anything." Colquitt, working with computer consultant Luther Welsh Jr. of El Toro, Calif., had written a computer program and organized a systematic search of Mersenne numbers in the hope of finding a record-breaking prime.

This time, because he had only a limited amount of time available on an NEC SX-2 supercomputer, Colquitt decided to run some smaller candidates to be sure that nothing had been missed in previous searches. Only Mersenne numbers with exponents up to 103,000 had been exhaustively searched in the past, says Colquitt. Later efforts had been "shotgun" affairs that covered only narrow ranges of large numbers. The new Mersenne prime falls within one of the gaps.

The supercomputer, running a program written completely in FORTRAN, took only about 11 minutes to confirm that 2110,503-1 is a prime number. "That's an incredibly fast time," says David Slowinski, formerly with Cray Research, Inc., in Minneapolis and now a student at Carnegie-Mellon University in Pittsburgh. "They (must) have some very good trick to get such a fast time." Slowinski himself has discovered several Mersenne primes and plans to check Colquitt and Welsh's result.

"We tried different multiplication algorithms," says Welsh. "The program, as it stands now, is fairly decent, although it's not as fast as it could be."

"If you're going to look for prime numbers," says Colquitt, "you're probably going to learn more about multiplication than you want to know. You also have to be systematic-and you have to be lucky and pray a little bit."

Are there more Mersenne primes lurking in the gaps? "I have absolutely no idea," says Colquitt. "Thousands of them are untested yet."

Printer friendly Cite/link Email Feedback | |

Title Annotation: | 31st Mersenne prime number found |
---|---|

Author: | Peterson, I. |

Publication: | Science News |

Date: | Feb 6, 1988 |

Words: | 416 |

Previous Article: | FDA to evaluate fat substitute. |

Next Article: | Good-deed viruses stop mouse diabetes. |

Topics: |