1. Developments in Technology.

Back

The main technological developments that helped to bring the factor tables

into their present form are listed below in roughly chronological order.

(a) Automatic Multiply and Divide. In about 1925 automatic multiply and

divide operations became available on mechanical calculators in the United States.

This improvement reduced errors and computing time, enough so that hand calculation

in factorization and primality testing could persist until rather recently.

Now, however, even the more accessible calculations are usually done by electronic

computers.

Some who worked by hand on problems relating to bn􀀀1 after 1925 were D. N.

Lehmer, DHL and Emma Lehmer [40], M. Kraitchik [34, 35], P. Poulet [83 and

see 56], H. S. Uhler [105, 106], A. Ferrier [14 to 19], N. G. W. H. Beeger [1],

R. E. Powers [84], E. Gabard [6, 20, 31], and K. R. Isemonger [3, 6, 29, 30, 31].

Their results, usually obtained after long hours of work at a desk calculator, are a

tribute to diligent and careful computation.

(b) The Bicycle-chain Sieve [42, 64]. This machine was built by DHL in 1927

and was the _rst fully automatic machine to be used for factoring and primality

testing. (Prior to this, paper strip methods had been used for hand-sifting [33,

Ch. 2], as well as various stencil devices such as the factor stencils of D. N. Lehmer

[67, 69, 40, p. 336] and the Hollerith card stencils of J. D. Elder [13].) The scanning

rate of the machine was 50 numbers per second, and it produced impressive results

for its day, such as the two factorizations

1020 + 1 = 73:137:1676321:5964848081

2019210335106439 = 25709599:78539161

III B 1 DEVELOPMENTS IN TECHNOLOGY xlviii

these latter being factors of 3111 + 1.

(c) The Photoelectric Number Sieve [10, 48, 49, 50, 64]. This machine was

built in 1932 by DHL and his associates. It used electronics that were advanced for

its time, as well as high-precision gears to carry out the sifting. Among its many

results are the two factorizations

279 􀀀 1 = 2687:202029703:1113491139767

293 + 1 = 32:529510939:715827883:2903110321

and a proof that the cofactor 3011347479614249131 of 295 + 1 is a prime. The

scanning rate of this machine was 5000 numbers per second. For a delightful account

by D. N. Lehmer of the photoelectric number sieve, see [68]. (See the status report

in section V B for more about this machine.)

(d) The ENIAC (Electronic Numerical Integrator and Computer). In [57] and

[62] DHL gave an account of how \during a holiday weekend" this machine produced

85 new factors of 2k _ 1 for k _ 500. (See [56, 63].) Collecting the results was

pleasantly overwhelming|\picking plums at waist height"|considering that a few

new factors would be all that the most industrious hand computer would expect to

_nd in months of labor. Here, then, was already an example of a practice that was to

be repeated over and over again in the decades to follow: letting a computer factor

and test for primality on idle time. Many results in these tables were obtained

on idle time, quite often to the bene_t of the machines which were better left

running than being shut down. (In at least two instances these machine-language

programs, which the machine operators and IBM engineers came to regard as test

programs, detected intermittent hardware failures which had evaded the standard

machine tests.) The vast amount of time spent organizing the extensive output

and the cases to be run, and preparing setups to be run (often throughout the

night) attests to the great interest and pleasure we felt at a time when factoring

and primality testing had not yet been recognized as being relevant to the transfer

of funds or to national security. This persistent involvement over the years has

led to a considerable development in the theory and the practice of factoring and

primality testing.

(e) The SWAC (Standards Western Automatic Computer). This was the _rst

large electronic computer in the western United States (UCLA, 1950). Although

this machine had a memory of only 256 words of 37 bits each (later augmented with

a 4096-word drum), it was a very nice binary machine which allowed for exible bit

manipulation with its four-address system. It had a 16 microsecond cycle time, a

bit-parallel addition taking 4 cycles and a multiplication taking 23. It was directly

suitable for number theory in that it, unlike some more modern general purpose

computers, produced an exact double-word integer product.

Much number theory was done on this machine [70]. At least three programs

run on the SWAC dealt with material in this book. One was a Fermat number

factoring routine written by JLS [95] which discovered factors of 2210+1 and 2216+1

in 1953. The other two were written by Raphael M. Robinson, who caused a mild

sensation by programming a primality test for the Mersenne numbers Mp = 2p 􀀀1

which ran when _rst tried, even though he had never programmed a computer

before. His modest account is given in [90]: \The program was _rst tried on

the SWAC on January 30 [1952], and two new [Mersenne] primes were found that

xlix III B 1 DEVELOPMENTS IN TECHNOLOGY

day (our emphasis), three other primes were found on June 25, October 7, and

October 9" [and see MTAC 6 (1952) 61, 205; 7 (1953) 72]. These were the primes

corresponding to p = 521, 607, 1279, 2203 and 2281. In addition to discovering

this impressive list of new Mersenne primes, the program was used to check the

Mersenne number results found earlier by hand calculation.

The second program of Robinson was used by Robinson and JLS to _nd factors

of the Fermat numbers Fn = 22n + 1. Although the machine was somewhat

unreliable because of its Williams tube electrostatic memory, it was a wonderful

machine with which to reach out beyond human powers. One minute of SWAC

time was roughly equivalent to one year of desk calculator time.

When programmed as a sieve, the SWAC was capable of sifting 100,000 numbers

a minute, only one-third the speed that the photoelectric number sieve had

achieved twenty years earlier.

A charming feature of the SWAC was its loudspeaker which emitted squawks

and noises characteristic of the loops in the running program. After running the

program for a while, the machine operator, who was usually the programmer, could

tell more or less what the computer was doing by just listening to it.

(f) The IBM 701. One of these machines was installed at UC Berkeley in 1954

and was taken out in 1962. Originally it had an electrostaticWilliams tube memory

like the SWAC, but in a short time it was given a magnetic core memory and so

became much more reliable.

Many researchers owe a great deal to Ted Ross, the IBM engineer who made the

701 the reliable machine that it was for its full life at Berkeley. The computer had a

reasonably large memory and a peripheral magnetic drum for slower extra storage.

Its cycle time was 12 microseconds. An addition took 5 cycles, a multiplication or

division 38. It was a _ne machine for number theory, since it gave a double-word

product and an exact quotient and remainder on division. It also had a good set

of \bit-pushing" instructions which facilitated some ingenious machine-language

programming.

The computer could operate at either a full or a half-word level, each word

consisting of 35 bits and a sign. The arithmetic on the machine was in signed

binary, in contrast to the now common twos-complement arithmetic which can be

awkward.

Within a few years of operation, the 701's library of programs had some very

useful software, such as a good symbolic assembler and several types of dumps,

including a snap dump and a couple of trace dumps. There were three magnetic

tape units that gave the system greater exibility in operation. On the other hand,

there was no higher level language and the hardware itself was lacking in many

ways. There was no BCD, no oating-point arithmetic, and there were no index

registers. It was also necessary to program all input-output and all the checking

that went with it. All programs were initially loaded on-line through the card

reader.

Three di_erent projects contributing to these tables were carried out on the

701. In [92] Raphael M. Robinson reported on a direct search for factors using a

di_erence table to generate the sequence of trial divisors. From this search came

several complete factorizations as well as the _rst factors of the Mersenne numbers

M109 and M157.

III B 1 DEVELOPMENTS IN TECHNOLOGY l

In [2], six new factors of 2p 􀀀 1 for p = 163, 181, 193, 229, 239 and 241 were

reported, along with many other factors of Mp obtained by direct search. Because

this search was done at zero priority, a considerable e_ort was made to minimize

the search time by using a succession of divide routines requiring fewer machine

cycles for larger divisors. Whenever the divisor surpassed a certain power of two,

a new program was manually loaded. In [3], another direct search produced many

new factors of the numbers 22p + 1, p prime. This program also keyed the divide

routines to the growing size of the divisors, but this time the program itself kept

track of their size and wrote the routine to be used on the next larger class of

divisors.

DHL also wrote a primality test for numbers 2p _ 2(p+1)=2 + 1 which had no

known prime factors. In this way, for instance, 2379 + 2190 + 1 was discovered

to be a prime. The factoring program completely factored two numbers, namely

283 􀀀 242 +1 and 259 +230 + 1, the latter having been listed as a prime in 1929 by

Kraitchik [35, p. 87].

(g) The IBM 704. This machine was a tremendous improvement over the 701,

with which it was incompatible. It was the _rst of the series of IBM computers|

numbered 704, 709, 7090, 7094|that, like the 701, were excellent for number theory.

Internally they used signed binary arithmetic.

The hardware improvements in the 704 were many. It had, for example, three

index registers, a larger instruction repertoire, BCD mode, oating-point arithmetic,

automatic input-output checking, simpler-to-use magnetic tape drives, and

a more rapid card reader. The assembler was also much improved. As with all the

IBM computers, the 704 was excellently maintained and was very reliable.

A number-theoretic subroutine package for multiple-precision arithmetic was

written in machine-language for this machine by Jerry (G. D.) Johnson, and the

package turned out to be compatible with all the later machines in this series. This

package permitted left and right shifting of binary words and contained the basic

number-theoretic subroutines for signed integers that allowed for their addition,

subtraction, multiplication and division, and also the computation of an (mod m),

the GCD, and the Jacobi symbol.

Several programs based on this package of subroutines were written by JB

and were much used on this project. Among these were a direct-search factoring

program as well as a primality testing program which could determine the primality

of a probable prime N when the complete factorization of N 􀀀1 was known.

The main results obtained on this machine were the discovery of a second factor

of F10 and the factorization of

M101 = 7432339208719:341117531003194129:

The latter was obtained in 1963 by Jerry Johnson, DHL and JB from a direct search

based on a quadratic sieve constructed from quadratic residues in the continued

fraction expansion of

p

mN for various values of m. To produce these residues,

the 704 ran for hundreds of hours without an error! M101 had been the smallest

composite Mersenne number with no known factors, and this factorization had been

sought for decades. It was discovered in only two hours because the sequence of

trial divisors had such large di_erences between consecutive terms.

(h) The Delay-line Sieves (DLS 127, DLS 157) [59, 64, 7]. In December of

1965 the delay-line sieve DLS 127 (\Dick Lehmer's Sieve") [6] began running at UC

li III B 1 DEVELOPMENTS IN TECHNOLOGY

Berkeley. This sieve, which was designed by DHL and made operational through

the good o_ces and e_orts of PaulMorton and Robert Co_n, used electronic delaylines

in place of the earlier bicycle chains and gears. Its scanning rate, as well as

that of the later DLS 157, was 106 numbers per second. The later model, DLS 157,

which is still running, was made from DLS 127 by adding shift registers (instead of

more delay-lines) for the prime moduli from 131 to 157. Both sieves operated on

100 watts of power. (See the status report in section IV B.)

An interesting design problem that had to be solved in building the sieve was

how to save the bit patterns in the delay-lines during their individual sieving when

it was necessary to pause long enough to print out a solution that the sieve had

just discovered. To do this, the individual bit patterns were hooked end to end and

circulated as a serpentine through the whole machine. Whenever the serpentine

had returned to its original position, the individual sieving could then be started

again [64].

Many factorizations and primality tests were done using these sieves. The

notable factorization,

2109 􀀀 255 + 1 = 5:74323515777853:1746518852140345553

was completed on the DLS 127 by a di_erence of squares method. These sieves are

the most rapid we have used, the nearest competitor being a sieve program with

a scanning rate of about 105 numbers per second, written by JB [6] for the IBM

7094.

(i) The IBM 709, 7090, 7094. These machines continued the trend begun

by the 704, the tubes in the 709 being replaced by transistors in the latter two

machines. The 7094 had 7 index registers, and a marvelous and useful array of

machine instructions. The cycle time was 2.18 microseconds, with add, multiply

and divide times of 2, 5 and 8 cycles, respectively.

Careful programming of the data channels on the machine permitted input

and output that were independent of the main processor and parallel to it. There

was also an excellent collection of standard programs for assemblies, dumps, trace

routines, and other debugging aids.

The machines used were primarily those at UC Berkeley, Stanford (thanks

to G. Forsythe) and UCLA. In the latter part of its life, the 7094, which was

owned by UC Berkeley, sat in the basement of the mathematics building. It had

no data channels or maintenance contracts, for it had been superseded by the CDC

6400. Nonetheless, since factoring programs require little input and produce little

output, the 7094 gave JB, JLS, DHL and Emma Lehmer a marvelous opportunity

to work. Thus with patience we put the program into the memory in binary through

the console switches. Of course no one else was using the machine, so it became

essentially our machine. When after months of excellent service some hardware

began to fail, we either programmed around the di_culty or dug into our pockets

for a little money to bring in an IBM engineer to _x the machine.

In the days before its _nal sad demise, JB wrote some factoring and primality

testing programs based on the multiple-precision package of Jerry Johnson. The

primality program tested the primality of a probable prime N, given the complete

factorization of N 􀀀 1. Later, a more elaborate program was written by JB which

automated the passing between levels in primality testing [4]. This program was

a predecessor of the DOWNRUN program of JLS and Marvin Wunderlich, used

extensively at DeKalb and described in 3(b) below.

III B 1 DEVELOPMENTS IN TECHNOLOGY lii

JB wrote not only a simple direct search factoring program, but also a very

productive di_erence of squares program[6]. Results obtained by the latter program

include the factorizations of M103, M163 and

2107 + 254 + 1 = 843589:8174912477117:23528569104401:

A large number of factorizations obtained on the 7090 and the 7094 appear in these

tables for the _rst time, but are lost in the profusion of more recent results.

Some primality testing on Fermat and Mersenne numbers was done by JLS

and Alex Hurwitz at UCLA [96]. They ran a modular check during the testing

on each arithmetic operation and discovered over a long period of time that the

machine did in fact make several arithmetic errors. Of course, such primality testing

made unusually heavy repetitive use of the _xed point instructions. BT developed

a package of Fortran and Assembly language multiple-precision integer arithmetic

and trial-divisor factorization programs for the 7094 at the IBM Research Center,

and used it for work on odd perfect numbers in 1967 [103, 104]. This work

depended on the evaluation and factorization of a number of values of _(n), the

sum-of-divisors function. As is well known, if n =

Q

i pai

i , then _(n) =

Q

i _(pai

i )

and _(pa) = (pa+1 􀀀 1)=(p 􀀀 1). Aside from the denominator p 􀀀 1, this is of the

same form as the numbers bn 􀀀 1 considered in the present work, where b = p,

n = a + 1. However, the interest extended to a greater range of prime values p

of the base, and a lesser range of the exponent, than the present work. Complete

factorizations were made of all cyclotomic numbers _q(p) < 1018 for which p and

q are odd primes, and p > 14, also for scattered larger p as needed, some also

for q = 2. These factorizations may be found in [104]. The ones for p < 12 are

subsumed in the present tables.

Perhaps the most impressive computer center that we used was at the Bell

Telephone center at Holmdel, New Jersey. Several 7094's were hooked into a single

system. They could be switched for di_erent use as easily as one could reassign the

numbers on a tape unit. This center came close to the ideal of having a system

which was not so generalized that simple, standard things couldn't be done simply.

Among the single user machines the 7094 was indeed outstanding for number theory.

(j) The IBM 360 Series. With the introduction of this series of computers,

the single-user became one of the several persons using the machine at the same

time. The word size was shrunk to 32 bits, and the machine was incompatible with

the 7094. It also employed twos-complement arithmetic, but the exact product,

quotient, and remainder in integer arithmetic survived. It was designed to be a

very versatile machine with a complicated job control language, but its generality

made it hard to use for simple tasks.

The _rst model of this machine we used at UCLA was the 360/91, which had

a look-ahead feature as well as a stack (instruction cache). These gave the machine

great speed when a program was written in machine language, since then branching

and register loading could often be accomplished in no extra time.

A drawback in using a stack and look-ahead was that when two instructions

were being executed at the same time and an error occurred, it was di_cult to

determine what had happened. This produced a rather mystical, interpretive feeling

among the programmers who had to try to guess what had happened and how to

_x it, instead of just taking a dump, _nding out what had happened and then

removing the errors.

liii III B 1 DEVELOPMENTS IN TECHNOLOGY

The cycle time on this 360 was 60 nanoseconds. For _xed point, the add

time was 1 cycle, multiply time 7 to 11 cycles and divide time about 37 cycles. For

oating point, the add time was 1 or 2 cycles, multiply time 3 or 4 cycles and divide

time 9 to 12 cycles. In addition, execution of instructions was overlapped, especially

oating point instructions, so that for many purposes, even for computations with

integers, the oating point instructions gave much faster computations.

The _ne collection of software surrounding this machine included excellent

_le-management features, assemblers, compilers, editors and interpreters. Also, it

was possible to use David Cantor's valuable multiple-precision integer subroutine

package.

The main program run on this machine was written by Mike Morrison and

JB. In this program, which is discussed in 2(d) below, a great deal of auxiliary

factoring was done by dividing by a _xed set of small primes. Unfortunately the

designers of the 360 had given the machine rather slow _xed-point multiply and

divide instructions, while making the double-length oating-point operations very

fast. Evidently their rationale was that all really important scienti_c calculations

involve only approximate numbers. Thus, when we wanted to divide by 3, say, we

programmed the division in oating-point rather than in _xed-point because the

former was several times faster. The programming of this required that the binary

point end up in the correct position so the integer part could be properly recovered.

This was greatly assisted by an interpreter which allowed for a single-step-at-a-time

analysis of how the oating-point instructions worked.

This machine's large memory permitted us to use over a million bytes of memory

in the crucial reduction stage of a very large matrix of bits that produced the

factorizations of F7, the _rst and most signi_cant factorization done on this machine

among dozens of others that appear in these tables.

After being used on the 360 at UCLA for several years, the factorization program

was moved in 1973 to the 360/67 at DeKalb. The program was further developed

by Marvin Wunderlich, who used his own multiple-precision integer package

and who also devised an automatic submission feature which made the program

fully automatic. In this improved form, one could merely submit the number to

be factored and, after some time, collect the printout of factors along with some

interesting statistical data.

In addition to this powerful program, another program called DOWNRUN

was written to implement a primality test devised by JLS and Wunderlich [98].

These two programs, used together, have allowed us to bring these tables to their

present advanced state. Free computer time at NIU has of course been invaluable,

as has the enthusiastic sponsorship of JLS and his Foundation for Number Theory

Computing. This Foundation and its supporters deeply inuenced the development

and promotion of _ne computing in number theory during the 1970's.

The 360/75 at the University of Illinois was used by SSW in the table testing

mentioned in section A above. Also, he used the DEC 10/KI in a two months' factoring

rerun that covered the complete set of tables and discovered or rediscovered

the factors up to 235 in the tables. The number representation and set of DEC 10

instructions facilitated multiple-precision arithmetic in base 235. Since this computer

is a dual processor, one processor could work full time for the two months on

the factoring, while the other satis_ed the time-sharing needs of most of the other

users. Much of the information gleaned from these runs was put into _nal form in

_les at DeKalb, where a good editor (WILBUR) from Stanford was in use.

III B 1 DEVELOPMENTS IN TECHNOLOGY liv

The IBM 4341 was used by SSW to factor some large numbers, such as 2,302M

and 1056 + 1, by the continued fraction method. He also used the Illinois Central

Editor (ICE) to perform the _nal testing on the tables. The factoring was done

with \bulk time", an arrangement whereby the interstitial time on the machine

could be used essentially independently of other large projects.

The 360/91 at IBM at Yorktown Heights was used by BT for a search for

Mersenne primes which discovered the prime M19937 [102]. The program that did

this testing was written by BT with very careful thought to timing, in that the

programs took advantage of the author's detailed knowledge of instruction and

hardware operation. To utilize the greater speed of the 360/91 on oating versus

_xed point, the relevant programs were written, or rewritten, in oating point.

(k) Other Computers. A direct search for factors was carried out over many

months on an IBM 1130 at the Mathematics Department at the University of

Arizona. This small 16-bit word computer is quite slow by modern standards, but

slow computers are often more widely available than fast ones. A common computer

center policy is to permit a fast computer to be used only by funded researchers, so

that one is given the option of having little or no time on a really fast computer or

a great deal of time on a slow computer. The 1130 search found all the factors less

than 230 of 2n 􀀀 1 for various n for which a search had not earlier been completed.

At UC Berkeley, after the IBM 7094 was inactivated, a CDC 6400 became

the main machine. This fast machine permitted several jobs to run side-by-side

in the memory, which allowed for useful computing to be done on one program

while another was inputting or outputting. A small zero-priority program, written

by DHL and Peter Weinberger, was tucked away in the memory and was always

available to continue its search for factors up to 1012 on a particular number. This

valuable program produced many factors.

Since this program was to be as unobtrusive as possible, it was designed to

take as little memory as possible, and so did its outputting by the following indirect

procedure: when a factor was found, the program stored it in a particular memory

location and then deliberately divided by zero. This produced an error condition

that caused the system automatically to take a tiny dump of the part of the memory

where the factor was stored. Fetching the factor from the dump in octal and

converting it to decimal was a small matter, provided that the single sheet of

output was not lost and was put in DHL's output box.

One of the more interesting factorizations obtained by this background program

was 698962539799:4096460559560875111, which _nished o_ 2333 􀀀 1.

An amusing by-product of having a program always in memory, ready to run

whenever nothing else was running, was that the running time of the program accurately

measured the idle time of the computer. Occasionally this caused comment

when it was discovered that the program had run almost 100 percent of the time.

The hardware of this machine was poor for number theory in that on multiplying,

it did not produce a double-word product. One had to do each multiplication

twice to get the two product words.

The Swedish computer BESK was used by Hans Riesel for several purposes [86

to 89], among them the factoring of Mersenne numbers and the primality testing

of these numbers.

The Illiac II was used by D. B. Gillies [22] to factor Mersenne numbers and to

study the distribution of Mersenne primes.

lv III B 2 DEVELOPMENTS IN FACTORIZATION

DHL used the Illiac IV at Mo_ett Field, California, for factoring and primality

testing. This interesting computer had a 64-bit word and a cycle time of 64

nanoseconds. An addition took 240 nanoseconds and a multiply took 400 on the

individual processors. A very useful feature of this machine was its capability of

carrying out the same operation on 64 numbers at the same time.

Hugh Williams has used an Amdahl 470/V7 for some of the more di_cult

primality testing and for the factorization of various large composite numbers by

the two-step Pollard method [80].

Finally, Robert Baillie has obtained some impressive factorizations using idle

time on the Plato system's CDC 6500 at the University of Illinois, and Hiromi

Suyama has found factors of several Fermat and Mersenne numbers with his own

8-bit MZ-80C microcomputer.

Some more recent factorizations have also been included in the tables. (See

the status report in section IV B.)

Навигация