# Major-league factoring on a low budget.

Major-league factoring on a low budget

There's more than one way to crack a tough number. Last month, a group of researchers, using dozens of computers scattered across three continents, split a particularly difficult 100-digit number into its two prime-number factors (SN: 10/22/88, p.263). A few weeks later, William R. (Red) Alford of the University of Georgia in Athens finished factoring a 95-digit number. Although he didn't set a new factoring record, Alford managed to accomplish the factorization using about 100 personal computers -- the most humble members of the computing family -- to collect the data he needed. Only four years ago, the best anyone could do, even with a supercomputer, was to factor a hard 71-digit number.

Although Alford used the same factoring method as the international group, his success depended on a highly sophisticated computer program designed to push each microcomputer to its limit. With no network connecting the machines, Alford himself carried data-packed floppy disks from computer to computer, taking four months to gather the information he needed to do the final factoring step on a larger computer. For the final step, he had access to a newly developed algorithm for dealing with large matrices, which allowed him to complete the last step in half the time the larger international group needed to complete factoring its 100-digit number.

Alford's 95-digit number comes from a list of "most wanted" factorizations. The number, which turns out to have a 44-digit and a 52-digit factor, is the 95-digit remainder after dividing 2.sup.332 + 1 by the numbers 17 and 11,953.

There's more than one way to crack a tough number. Last month, a group of researchers, using dozens of computers scattered across three continents, split a particularly difficult 100-digit number into its two prime-number factors (SN: 10/22/88, p.263). A few weeks later, William R. (Red) Alford of the University of Georgia in Athens finished factoring a 95-digit number. Although he didn't set a new factoring record, Alford managed to accomplish the factorization using about 100 personal computers -- the most humble members of the computing family -- to collect the data he needed. Only four years ago, the best anyone could do, even with a supercomputer, was to factor a hard 71-digit number.

Although Alford used the same factoring method as the international group, his success depended on a highly sophisticated computer program designed to push each microcomputer to its limit. With no network connecting the machines, Alford himself carried data-packed floppy disks from computer to computer, taking four months to gather the information he needed to do the final factoring step on a larger computer. For the final step, he had access to a newly developed algorithm for dealing with large matrices, which allowed him to complete the last step in half the time the larger international group needed to complete factoring its 100-digit number.

Alford's 95-digit number comes from a list of "most wanted" factorizations. The number, which turns out to have a 44-digit and a 52-digit factor, is the 95-digit remainder after dividing 2.sup.332 + 1 by the numbers 17 and 11,953.

Printer friendly Cite/link Email Feedback | |

Title Annotation: | microcomputers used in mathematical factoring |
---|---|

Publication: | Science News |

Date: | Nov 12, 1988 |

Words: | 264 |

Previous Article: | Tying together math and macromolecules. |

Next Article: | Hiding the atmosphere of Mars. |

Topics: |