Special Purpose Factoring Devices

   A journey from Bicycle to Quantum Computers

Computational Number Theory Project
Math 583e, University of Washington
Spring 2009

Old School Factoring

Most of the SPDs from the past were built upon the basic factoring idea by Fermat which was called the Difference of Squares method. The algorithm and an idea to design a special purpose hardware based on this method is as follows.

Difference of Squares Method

Idea: To factor , try to find such that
Algorithm: Set and iterate through until is a square (call that )

Designing a Machine

For a small set of primes , manually find the values of such that is square mod and mark those values on a wheel (can be replaced by chains, gears etc with variable rotation period) with positions. Then turn the wheels simultaneously, which actually iterates through the values, such that a set of markings line up. By congruence conditions with respect to the individual primes and Chinese Remainder Theorem, you may expect the desired solution , though it may take quite a while to show up.

There were a few 'good' machines built in this line. Let us take a look at the best hardware configurations in business before the advent of computers. Though some of these machines are termed as 'sieves', they do not fall under the rigorous category of sieves, as we know them now. This document calls the machines by their historic names though.

 

Machine à Congruences (Carissan, 1919)

In this case, there were 14 concentric brass rings with studs on each ring. The studs were capped to represent the condition   square mod . These caps will trigger a switch for their respective rings. There were 14 switches in series, one on each ring, and when all of the switches would ring, an alarm would go off, indicating solution for .

Factored in 18 minutes. Last seen in 1920, after which the only prototype disappeared. Came back to public attention in 1992 through Discovery of a lost factoring machine by Shallit, Williams and Morain.

 

Lehmer Sieves (1930s)

About D.H.Lehmer 

Derrick H. Lehmer (1905-1991) [photo beside], professor at UC Berkeley and his father Derrick N. Lehmer (1867-1938), a leading number theorist, built computing machines to solve mathematical “sieve” problems.

The three machines shown here demonstrate the variety of approaches the Lehmers used in building simple but powerful computing devices. The metal version could check 5,000 combinations per second, a record that was only beaten by computers in the 1960s.

Bicycle Chain Sieve

Same idea a Carissan, but a lot faster and motorized instead of manually driven. 

The "bicycle chain" sieve was made in 1926. Essentially the machine consisted of a number bicycle chains (the number used depended on how big the first set of number was). The values of certain remainders of interest are represented by a rod sticking out of the side of specific links in each chain. As the chains rotate around the drive axle at the top, these rods will close small electrical switches. When all switches get closed at once, this signals that a solution has been found to the specific problem being considered.

This could factor

Gear Sieve

Same idea as before but faster photo-electric implementation. First time that flip-flop was used in a computing device.

The geared sieve dates from 1932. It is made up of gears of different sizes representing numbers in exactly the same way that the bicycle chains. Holes in each gear represented various remainders when these numbers were divided by others and they could be plugged up with toothpicks to only leave a certain set of these numbers open. A bright light on one side of the machine would shine on the gears and, if the holes lined up, then it would reach the other side and trip a flip-flop attached to the photocell. The output of the flip-flop was amplified and would be used to stop the motor spinning the wheels – thus allowing you to see the solution to the problem.

Factorization of in 12 seconds and in a few seconds as well.

 

Modern Times

1970's can easily be called the 'renaissance' of factoring. With the proposal of Morrison and Brillhart, A method of Factoring and Factoring of F7 in 1975, the basic principle of factoring large numbers changed dramatically. Though it was a formalization of an original idea by Kraitchik (1920), this initiated formal modern day factoring sieve, which was periodically improved by Dixon (Dixon's algorithm), Pomerance (Quadratic Sieve), Davis and Holdridge (changing polynomials in QS) and Montgomery (Multi-Polynomial QS). A new idea by Pollard (1988) suggested the use of algebraic fields and eventually the formal version of Number Field Sieve was formulated by A. Lenstra and H. Lenstra in 1993.

Most of the modern day SPDs deal with facilitating the NFS or certain part of the same. In the next section, we will take a look at the new sieving idea and the development of state-of-the-art special purpose devices to facilitate NFS.

<< Prev: Factoring Problem Next: Modern Day SPDs >>