Printer Friendly

Cranking out primes: tracking down a long-lost factoring machine.

It looks like a cross between an antique music box and an old-fashioned, hand-cranked phonograph. But no music emanates from the contraption.

Instead, this ingenious mechanical device operates as a number sieve. It automatically sifts through arrays of numbers to identify certain patterns. From these data, mathematicians can determine whether a given number is a prime or the product of two or more primes multiplied together.

Constructed 75 years ago, it also represents the first known, successful attempt to automate the factoring of whole numbers. Until three researchers tracked down the machine recently, few people knew of its existence. Now, this unique device can take its proper place in the history of computational number theory.

"It is a very interesting piece of mathematical history, and it is a beautifully designed machine," says computer scientist and mathematician Hugh C. Williams of the University of Manitoba in Winnipeg, who assisted in the search.

The hunt began in 1989, when Jeffrey Shallit of the University of Waterloo in Ontario came across an article about the machine in an obscure 1920 French journal. The author of the report was Eugene Olivier Carissan, an officer in the French infantry and amateur mathematician, who had designed the factoring apparatus. Shallit immediately recognized the importance of Carissan's work. The article indicated that Carissan had developed number sieve technology several years before Derrick H. Lehmer, the U.S. mathematician generally credited with being the first to design and build machines for solving problems in number theory (SN: 11/20/93, p.331).

Shallit, joined by Williams and Francois Morain of the Ecole Polytechnique in Palaiseau, France, decided to look for the Carissan factoring machine. "All of us spent a lot of time searching," Shallit says.

For a long time, their efforts were unsuccessful. The company that had fabricated the machine was out of business. There was no hint of the apparatus in any museum or library.

Finally, the researchers turned to a computerized database of all telephone subscribers in France to obtain the names and addresses of people with the surname Carissan. Their computer search turned up 85 candidates. Shallit wrote a letter to each one, hoping for news of the invention but expecting little success.

Soon afterward, Morain received a phone call from a daughter of Eugene Carissan. The machine still existed, tucked away in a drawer at an astronomical observatory in Floirac, near Bordeaux.

When Morain visited the observatory and located the factoring machine, he found it was still in good shape. "I was able to program up a small problem, and the machine solved it successfully," Morain says.

Shallit, Williams, and Morain have described the machine and their efforts to locate it in an article submitted to THE MATHEMATICAL INTELLIGENCER.

Slightly larger than one of today's laptop computers, the Carissan device consists of a set of 14 rings that can rotate concentrically atop rollers mounted on a wooden base. Made of brass, each ring has a different diameter, with gear teeth on its underside and a particular number of equally spaced steel studs screwed into its top. Taken together, the assembled rings look like a prickly phonograph record.

To use the apparatus to factor a given number, an operator would cap certain studs on each ring, following a mathematical recipe that involves a form of trial division, or sieving. The idea is to divide by numbers smaller than the given number to look for a particular set of remainders. The rings are then mounted on rollers in such a way that studs on different rings would be lined up in a special way beneath an armature resembling the arm of a phonograph.

As the operator turned a handle, the rings would rotate at different rates. Capped studs, which protrude higher than uncapped studs, would brush against the armature. If capped studs from all 14 rings did this simultaneously, an electric circuit would be completed and the operator, wearing a headset, would hear a click. He or she would then read off a number from a counter. This number constituted part of the solution of the factoring problem.

Rotating the crank at two revolutions per minute, an operator could process 35 to 40 numbers per second. In this way, Carissan took just 10 minutes to prove that 708,158,977 is a prime number. He was even able to factor a 13-digit number.

This may seem like a modest achievement compared to the 129-digit behemoths that computer scientists can factor nowadays (SN: 5/7/94, p.292), but it represented a significant advance at the time.

Carissan had plans for upgrading his machine. One improvement involved attaching a small electric motor to drive the apparatus.

It appears, however, that no additional work was ever done on the machine. Carissan died in 1925, and his family ended up entrusting his invention to an astronomer at the Floirac observatory.

Last June, Carissan's remarkable factoring machine found a new home at the Conservatoire National des Arts et Metiers in Paris.
COPYRIGHT 1994 Science Service, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 1994, Gale Group. All rights reserved. Gale Group is a Thomson Corporation Company.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Carissan's factoring machine
Author:Peterson, Ivars
Publication:Science News
Article Type:Cover Story
Date:Oct 1, 1994
Previous Article:Exercising reduces breast cancer risk.
Next Article:The nuclides in town: does danger lurk in low-level radioactivity in sewage?

Related Articles
Try a tempo run.

Terms of use | Privacy policy | Copyright © 2022 Farlex, Inc. | Feedback | For webmasters |