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.
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.
|