Reference / Paper · 1989
OASiS: An Open Architecture Sieve System for Problems in Number Theory (PhD thesis, University of Manitoba)
Thesis on OASiS, the Manitoba open-architecture sieve built in the late 1980s.
Reference / Paper · 1989
Thesis on OASiS, the Manitoba open-architecture sieve built in the late 1980s.
OASiS: An Open Architecture Sieve System for Problems in Number Theory by Allan J. Stephens A thesis presented to the University of Manitoba in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the Department of Computer Science Winnipeg, Manitoba @ Allan J. Stephens, 1989 E*E National Library Biblíothèque nationale of Canada du Canada Canadian Theses Service Service des thèses canadiennes Ottawa. Canada KI A ON4 The author has granted an irrevocable nonexclusive licence allowing the National Ubrary of Canada to reproduce. loan. distribute or selt copies of his/her thesis by any means and in any form or format, making this thesis availabte to interested persons. The author retains ownership of the copyright in his/her thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without his/her permission. Lhuteur a accordé une licence irévocable et non exclusive permettant à la Bibliothèque na- tionale du Canada de reproduire, prêter. distribuer ou vendre des copies de sa thèse de quelque manière et sous quelque forme que ce soit pour mettre des exemplaires de cette thèse à la disposition despersonnes intéressées. L auteur conserve la propriété du droit d'auteur quiprotège sa thèse. Ni la thèse nides extraits substantiels de celle-ci ne doivent être imprimés ou autrement reproduits sans son autorisation. ISBN ø-315-6321ê-6 Canadä OASiS: AN OPEN ARCHITECTURE SIEVE SYSTEM FOR PROBLEMS IN NI]MBER THEORY BY ALLAN J. STEPHENS A thesis subnr¡ned to thc Faculty of Graduate Studies of the university of Ma¡ritoba in partial fulfìllment of the requirenrents of the degree of DOCTOR OF PEILOSOPHY o 1990 Permission has been granred to rhe LIBRARY oF THE uNlvER- S¡TY OF MANITOBA to lend or selt copies of this rhesis. to the NATIONAL LIBRARY OF CANADA ro rnicrotitm this thesis a¡rd to lend or æll copies oí the fìlm, and uNIVERslry MICROFILMS to publish an absrracr of rhis rhesis. The author rescrves other publication righfs, and neither thc thesis nor extensive extracts from it may be pnntec or otherwise reproduced without the author's written permission. (This page contains form approving the thesis.) -11 - I hereby declare that I am the sole author of this thesis. I authorize the University of Manitoba to lend this thesis to other institutions or individuals for the purpose of scholarly research. I further authorize the University of Manitoba to reproduce this thesis by photocopying or by other means, in total or in part" at the request of other institutions or individuals for the purpose of scholarly research. Allan J. Stephens -tll- Abstract The technique of sievinghas been known since the time of Eratosthenes, and has been used to solve problems involving systems of linear congruences since the end of the eighteenth century. As a wide range of number theoretic problems can be converted into sieving problems, considerable effort has been expended in constructing machines which are fast enough to solve problems that a¡e otherwise intractable. Most notable is the work of D. H. Lehmer, who pioneered the development of automatic sieving hardware in the 1920's. His sieving systems have made use of such diverse technologies as bicycle chains, photoelectric gears, and general-purpose computers. Lately, attention has shifted to machines using integrated circuits such as high-speed shift registers. The latest deveþment in automated sieving is the "Open Architecture Sieve System" (OASiS). The system features a specially-designed computer-the Open Architecture Sieve-that is capable of testing possible solutions to a system of linear congruences at a rate of over 200 million numbers per second. Unlike crürent sieves, the OAS can assume a variety of configurations, allowing the user to alter the number of congruences being tested in ha¡dware and thei¡ size. The sieve can be easily upgraded to accommodate more and larger congruences; additional sieve processors can also be installed to permit sieving to be performed in parallel. The OAS runs as a peripheral to a conventional minicomputer which runs special software that oversees the execution of sieving problems. This software increases the speed at which many sieving problems are solved by automatically optimizing sieving whenever one or more congruences with a single acceptable residue class a¡e present. This thesis discusses the generalized sieving problem and the history of automated sieving systems. It then introduces the basic concepts behind the design of the Open Architecture Sieve System. This is followed by chapters describing the operation of the system software and the OAS hardware, and subsequent chapters detailing their design and construction. The thesis then presents some results of problems that have been run using OASiS. This includes extending the tables of known pseudo-squares and pseudo. cubes, finding periodic continued fractions with long periods, and finding polynomials which have a high density of prime values. Acknowledgements The author was assisted by many individuals during the development of this thesis. Although there is room to mention only a few by name, the efforts of all those who were involved are greatly appreciated. Foremost ¿rmong those who worked on OASiS itself was our hardware technician, Dale Brodland. Dale designed the parts of the Open Architecture Sieve that I did not have the experience to do myself, and was instrumental in debugging the hardwa¡e once it was built. Without his help, the OAS might never have become fast enough or reliable enough to be a successful research tool. Thanks also go out to Dr. F. J. Burkowski of the University of Waterloo, who helped to establish the foundations of the OAS design. The primary financing for OASiS came from my advisor, Dr. Hugh C. Williams, who faithfully supported the system throughout the long interval from initial concept to finished product. A University of Manitoba Grant in Aid of Research provided funding for a prototype version of the sieve, and its support is also gratefully acknowledged. The Natural Sciences and Engineering Research Council of Canada contributed to OASiS in the form of a postgraduate scholarship to the author. Special thanks are directed to Dr. Derrick Henry Lehmer who provided many of the interesting and informative details about the early sieving machines described in Chapter 1. Dr. Iæhmer kindly invited me into his home and patiently answered an almost endless series of questions about his work, allowing me relate information that has never been formally recorded anywhere. I am also grateful to Dr. John Brillhart, his former pupil, who pointed out several errors in this chapter and suggested additional references. My thanks are also extended to the members of my thesis examination committee, who provided a similar valuable service in their critique of the entire document. Finally, I must thank the people whose contributions to OASiS, although indirect, were nonetheless essential to its success. Foremost among these is my loving wife, Billie, who stuck by me throughout the years of work on my doctorate, and frequently helped shoulder the burden when things got tough. Her patience, understanding, and support were greater than I had any right to expect. My thanks also go out to those many friends who provided a sympathetic ear or an encouraging word when I needed it most. -vl- Table of Contents ................. v Abstract... Acknowledgements.... .............. vi Chapter 1 : An Inroduction to Sievin9............... ...........1 1.1 The Sieving Problem. ................... I 1.1.1 Solving a Sieving Problem... ...............2 1.1.2 The Complexity of Sieving. ................. 3 1.1.3 Applications of Sievin9............. .......... 4 t.2 The Development of Sieve 4utomation................ ............7 1.2.I Sieving By Hand... ............. I ............ l0 1.2.2 Principles of Sieve 4utomation............... ........... 14 1.2.3 Automatic Sieving Systems.... ...... 24 1.2.4 Summary.. ...................26 Chapter 2:The Open Architecture Sieve System..... ................26 2.I Motivation ................. n 2.2 Goals....... 2.3 Chrono1ogy................ .................28 ....29 2.4 Design and Justification......... ...........29 2.4.1 Design Philosophy .... 30 2.4.2 Overall System Design ...................... 31 2.4.3 The Open Architecture Sieve......... .....33 2.4.4 The OASiS Environment.............. ......... 36 2.5 Preview of System Details ........37 Chapter 3 : Using OASiS ....37 3.L Creating a Sieving Problem... ......37 3.1.1 The Problem FiIe........ ....... 38 3.1.2 The Filter Program.... ...........40 3.1.3 The Configuration Fi1e............ ........ 40 3.1.4 Checking a Problem for Errors.. ....42 3.2 Running a Sieving Problem... ......42 3.2.1 Submitting a Problem for Execution............. ........43 3.2.2 What Happens During Problem Execution.. .....44 3.2.3 Monitoring a Problem. ...........45 3.2.4 Halting a Problem. .........46 3.2.5 Processing Problem Results...... ...............47 3.2.6 Running a Short Problern... .:...................................47 3.3 Handling Errors During Sieving .....49 Chapter 4 : OAS Principles of Operation................ 4.1 Design Fundamentals............ ......49 4.2 Modes of Operation................ .... 50 ........... 51 4.3 Basic Sieving Capabilities................. 4.4 Additional Capabilitie$............... .................53 ..................54 4.5 The Command Interpreter........... 4.6 Solving a Sieving Problem.... ..... 55 -vii- ........58 Implementation.......... ............... 58 5.1 The OASIS Accounr... ...............59 5.2 The SIEVE Command ...... 60 5.2.1 Implementation Overview........... .......61 5.2.2 The Monitor.............. ......62 5.2.3 The Problem Schedu1er................ ............. 63 5.2.4 The Problem File Controller. ...... & 5.2.5 The Virtual Sieve....... ...... 68 5.2.6 The Timer. ........... 68 5.3 Batch Sieving Problems.. ............. 69 5.3.1 The SYS$OASIS Job Queue ......69 5.3.2 The QJOB Command .......70 5.3.3 The Batch Job Command File..... .....................70 5.4 Additional OASiS Commands .......70 5.4.1 The KILL Command ..........70 5.4.2 The FIT Command ......................71 5.4.3 The LOOK Command. ......72 5.4.4 The PLILL Command ...................73 5.5 Installing the OASiS Software... ......................73 5.6 Porting OASiS to Other Hosts .....76 Chapter 6 : OAS Implementation.......... ...................76 6.1 Hardware Overview .......76 6.1.1 OAS Construction..... ............... 78 6.1.2 Sieve Unit Design............... ................ 81 6.2 The Control Board..... ...... 81 6.2.1 The Sieve Microcomputer............ .....82 6.2.2 Host Interface.............. ............. 82 6.2.3 Controlling Sieve Components............... .............. 85 6.2.4 Sieve Clocking... ........... 88 Detection Solution 6.2.5 ........ 90 The Trial Counter..... 6.2.6 .................. 90 6.3 The Ring Boa¡d........ .......... 90 6.3.1 Address Decoding.. ......91 6.3.2 Ring Design............... ....... 93 6.3.3 Ring Implementation ........ 96 6.3.4 Clocking the Rings... .................96 6.4 The Backplane........... ..................97 6.4.1 Control Board Interface... .... 98 6.4.2 Ring Board Interface.... ..................99 6.5 Firmware Overview.. ....... 100 6.5.1 Program Structure... .... 101 6.5.2 Command Processing ..... 103 6.5.3 SIVMON Services.... .. 104 6.5.4 Host Communication... ...... 106 Chapter 7 : Some OASiS Results...... ................... 106 7.1 Problems Involving Quadratic Character.. ... 107 7.1.1 Pseudo-squ4res............ ...... 109 7.7.2 Negative Pseudo-squares........... 7.L.3 Periodic Continued Fractions with Iong Periods..... ........... I l1 7.L.4 Quadratic Polynomials Generating Many Primes...... ......... 112 ............ 116 .2 Pseudo-cubes................ Chapter 5 : Host Software 7 -vlu- OASiS ................118 ............... 118 8.1 An OASiS Retrospective............. ... 119 8.2 Future Development of OASiS............... .....120 8.2.1 Improving the Existing System.. .....123 8.2.2 Multi-processor Sieving.............. ......... 125 8.2.3 A "Second Generation" Sieve Unir.......... ....... 126 8.3 The University of Calgary Sieve......... ........... 128 References Appendix A : OAS Schematics ............... A-1 ............... B-1 Appendix B : OAS PAL Descriptions....... .........B-1 8.1 PAL Usage in the Open Architecture Sieve......... .. B-1 8.2 Reading PALASM Equations ................... B-2 8.3 Reading PALASM Fuse Maps .............C-1 Appendix C : SIVMON Guide.... ............... C-l C.l Command Basics....... ............... C-2 C.2 InpulOutput Control. ............... C-3 C.3 Command Summary.. .............. C-4 C.4 Command Descriptions................ .... C-4 Count....... C.4.I .... C-4 Down........ C.4.2 .... C-4 Find.......... C.4.3 .... C-5 Go............. C.4.4 .... C-5 Ha1t.......... C.4.5 .... C-5 Initialize... C.4.6 .... C-5 Memory.... C.4.7 .... C-6 C.4.8 Query........ .... C-6 Read......... C.4.9 .... C-8 C.4.10 Step.......... .... C-8 C.4.11 Up............. ............ C-8 C.4.12 Write .............D-1 Appendix D : SEND Guide........ ................... D-l D.l The OASiS SEND Facility...... .... D-3 D.2 Using the SEND Command. ................. D-3 D.2.1 Before Using SEND........ ...... D-3 D.2.2 Invoking SEND........ ................... D-4 D.2.3 Basic Script Techniques ........... D-5 D.2.4 Advanced Script Techniques ...............D-8 D.3 Modifying the SEND Facility..... ..........E-1 Appendix E : The OASiS Problem Fi1e........... ............:..... ...................E-1 E.l Problem File l-ayou1................ ....................E-1 8.2 Problem File Contents............. ............8-2 8.2.1 Name Pa¡r.......... ....8-2 8.2.2 Congruences Part....... ....8-4 8.2.3 Parameters Part........... ......... E-6 8.2.4 Results Part........... .................E-6 8.3 Problem File Grammar............... Chapter 8 : Beyond the -lx- File....... F.l Configuration File Layout....... F.2 Configuration File Contents.... F.2.1 Channel Specification................ F.2.2 Clock Speed Specihcation............... F.2.3 Number of Taps Specification............... F.2.4 Ring Description Part. F.3 Configuration File Grammar... Appendix G : A Sample Problem.... G.l hoblem Fi1e........... G.2 Filter Routine.... G.3 Running the Problern G.4 Problem Results..... Appendix F : The OASiS Configuration -x- ......F-l ....................F-1 ....................F-1 .......F-1 ...................F-2 .............F-2 ....F-2 ....................F-3 ....... G-l .................. G- 1 .....G-2 ............... G-4 .................. G-4 Chapter 1 : An Introduction to Sieving Attempt tlrc end, and never stand to doubt; Nothing's so hnrd, but searchwillfind it out. Robert Herrick, Seek and Fínd The technique of sieving has been used to solve mathematical problems since the time of Eratosthenes (fl. 230 B.C.). Although it is a general method that can be applied to a variety of problems in number theory, sieving is also computationally intensive; as a result, its applications are bounded by ttre rate at which the required operations can be perfomred. Since the late eighteenth century, a variety of devices have been constn¡cted to increase the speed of sieving, ranging from simple mechanical aids that improve the efficiency of sieving by hand to high speed computer systems that do sieving automatically. This chapter describes the generalized sieving problem and some of its applications, and traces the development of mechanized sieving over the last 200 years. t .1 THn SrnvrNc Pnonln*r Any mathematical problem that requires finding solutions to an a¡bitrary system of linear congruences involves an instance of the generalized sieving problem (GSP). fn general, a sieving problem P defines ft linear congruences, x=tit,r¡2t...tr¡r- (mod *r) Ii ? t;,'Z';'rO, where the moduli fti1,t7t2, ...,flkare positive integers. It may be assumed that the m¡ãta relatively prime in pairs and that each set of admissible residues R¡ = { fiL, riz, .,., finil contains distinct, non-negative integers less than m¡. The soluúon set S(P) for P is defined to be all¡e Z that lie within an interval specified by P, sayA (¡ç8, satisfy all È congruences, and satisfy any additional restrictions placed on.r'by P. Depending on the precise requirements of the problen¡ solving P may entail generating S(P), finding a subset of S(P), or simply determining the number of elements in S(P). As an illustration of a sieving problem, consider a P that utilizes the following set of five congruences: -1- An Introduction to Sieving x=l x=l x=1,4 " ' 2,4 1l (mod 8) (mod 3) (mod 5) (mod 7) i'J,q,s,g (mod n) , the restriction x * n2, and the range 0 < x < 3000. This problem arises naturally from the sfudy of quadratic residues (see Chapter 7). In this instance, there are two solutions in S(P\: 2641 and2689. 1.1.1 Solving a Sieving Problem The entries of S(P) a¡e the result of an exceedingly complex function of m¡, t¡¡, A, B, and the additional restrictions. The simplest algorithm for finding them is to treat each congruence as a "screen" or "sieve" which lets through only those integers which lie in the acceptable residue classes. Finding all of the x values that solve the t congruences then involves taking each integer in [,4"8), applying it to each of the È sieves in turn, and puning it in S(P) if it makes it through all of the sieves. Any additional restrictions specified by P can be imposed by using a further sieve that rejects any value lacking the required properties. This method of solving the problem is what gives it its name. The sieving method can be implemented in a variety of ways, ranging from a strictly sequential approach to a massively parallel one. Oppornrnities for parallel processing arise because the final acceptance or rejection of a given ¡ does not depend on the order in which the sieves are applied or on the results of sieving any other value in the search interval. It is theoretically possible to test a given integer against all of the sieves simultaneously, to test all of the integers in [AJ) against a given sieve simultaneously, or both. In practice, the amount of parallelism that can be employed is limited by implementation factors, which means that some form of serial processing must be performed when these limits are exceeded. A typical sieving implementation tests elements of the specified interval in sets of r, smfüng with A, A+1, ..., A+t-I. Each set of r values is applied simultaneously to as many sieves as possible, and then to the remaining sieves in a sequential manner. If a point is reached where all r entries have been rejected, the remaining sieves need not be applied. This approach limits the number of values tested in parallel to a feasible number, and also allows the system to handle "search" problems, in which the upper bound of the interval [A"B) is unknown. Such problems arise frequently in number theory, and usually involve finding the ¿ smallest elements of S(P). Sieving terminates either when the sea¡ch inærval has been completely processed or when ¿ solutions have been found. An lntroduction to Sieving 1.1,.2 The Complexity of Sieving The simple, deterministic nature of the sieving process makes it an atractive method for solving the GSP. Unfortunately, a comparison of the running time of the algorithm against the size of the problem shows that sieving is not a polynomial time algorithm. The specification of an arbitrary sieving problem that has no additional restrictions on its solutions defines & congruences and a search interval [Aß), and can be represenæd using k L^,*log2A +log2B i= I bits. If testing a given -r value to see if it satisfies a single congn¡ence is considered to be a basic operation, then finding all entries of S(P) may require up to k(B-A) operations to test all of the values in [Af) against all of the problem's congruences. This is an exponential function of the problem's size. The same is true for search problems, which use an open-ended interval (B = oo¡. Here, determining S(P) can require up to k k lþni i= I operations. After this point the pattern of solutions repeats with a period equal to the product of the moduli of the congruences. The exponential nature of the sieving algorithm means that it is easy to construct problem instances that are too large to be solved within a reasonable amount of time, so it would be nice to find a better way to solve an arbitrary system of congruences. Unfortunately, not only have mathematicians been unable to find a polynomial-time, deterministic algorithm that does this, but not even a polynomial-t:.me non-deterministic algorithm is known! For example, if the claim is made that a particular sieving problem has S(P) = { x1, 12, ..., rs } , it is easy to verify that the r¡ âre solutions. However, the only method known for showing that there are no others is to test the remaining values in [.a"8) to show that they are not solutions. Thus, the task of verifying a proposed S(P) is just as dif,ficult as generating it by sieving. Similarly, a claim that y is the smallest solution in S(P) can only be verified by testing all of the values less than y. The failure to find a computationally efficient method for solving the GSP is a result of its intrinsic difficulty. Pattenon [Pat89] has recently shown that the NP-complete problem of "quadratic congruences" [M478] can be transformed into a sieving problem, An Introduction to Sieving demonstrating that the GSP is NP-hard-that is, at least as hard as the problems in NP. Thus, it \yill probably be some time before the "brute force" technique of sieving will be replaced by a better algorithm for solving arbitrary sieving problems. Since there is currently no good method for verifying the solutions to a sieving problem, there is no proof that the GSP even lies in NP at all. It may lie in a class of problems that are even more difficult than NP, making the task of finding an improved algorithm even harder. Even though the sieving method is an exponential algorithm, it does not mean that sieving cannot be used to solve non-trivial sieving problems. From a human standpoint, a sieving problem with the interval [0,28) can be considered twice as difficult as the same problem covering [0"8) because there are twice as many possible solutions; the same is true if 2È congruences a¡e involved instead of k congruences, since there are twice the number of restrictions on its solutions. If this "human" notion of problem size is used, rather than the normal "bit counting" approach, then the time required to solve a problem by sieving is directly proportional to its size. This, along with the fact that the simple, deterministic nature of sieving allows it to be implemenæd efficiently, means that sieving can be utilized to solve many signif,rcant problems in number theory. L.1.3 Applications of Sieving The sorts of sieving problems that arise in number theory are quite varied in nature, and several date back many centuries. One is related to the well-known Sieve of Eratosthenes (see [Dic19]) and uses the frst tprimes (pypz, ...,pù as moduli and whose residue sets, R¡, exclude only zero. Such a system of congruences removes only multiples of the primes used, so sieving the intervalþ¿+I,p**]) generates all primes lying in thatrange. For example, the system of congruences obtained using å = 4 is x=l (mod 2) (mod 3) (mod 5) x = L,2,3,4 x = 1,2,3,4,5,6 (mod 7) , x:- 1,2 and produces the primes from 1 I to 113 when the interval [8,121] is sieved. At the opposite end of the spectrum is the Chínese Remainder Problem, in which only one residue class is acceptable for each congruence. Such problems have exactly one solution modulo nttmz...m¡, For example, the system r=l (mod2) x =2 (mod 3) x=3 (mod5) An Introduction to Sieving has the single solution x:23 (mod 30). The CRP is notable because it is one of the few classes of sieving problem which can be solved by a means other than sieving. One simple approach repeatedly merges pairs of congruences by means of the Euclidean Algorithm until only one congruence remains (see 54.3.2 of KnuSll). A much larger class of sieving problems, and one which is of considerable interest to mathematicians, involves finding integers ¡ and y which solve f@,y) = 0, where/is a polynomial of arbitrary degree with integer coefficients of arbitrary size. The "method of exclusion" of Gauss allows us to convert this Diophantine equation to a set of necessary (but not sufficient) sieve conditions which can be solved for-r by sieving. The solutions to the original equation are then found among the few-r values that remain instead of the entire solution space of possible x and y values. The lack of restrictions on / allows this technique to be applied to a wide range of problems in number theory. A brief list of such problems has been given by læhmer tleh66l and includes: . finding the representations of a large number by a given binary quadratic form, for example N = x2 -Y2, . finding the binomial units of a given algebraic number field, . finding the numbers (or the number of numbers) for a given polynomial that lie between given limits. As an illustration of this technique, a method of factoring an arbitrary large integer is given below. Although based on Fermat's idea of writing the integer as the difference of t'wo squ¿ìres [Dic19], the actual algorithm was developed by Gauss ([GC66], articles 319-325). A more complete discussion of both approaches is given by Brillhan tBriSll. Suppose that we wish to factor an odd integer, n > 0. If n is composite, then it must be the product of two odd factors, rut rl where U >V. If we define :.r.r, y=¡ü+V),y=yu-n and solve for U andV, we find U=(x+y),V=(x-y) and thus, n=(x +yxr-1l)= x2-y2 or Y2=x2-n' Therefore, if we can fînd an x value for which x2- n is a perfect square, \ile can calculate the factors of n, U and V. The number of such ¡ values that exist is equal to the number of ways that n can be represented as a product of nvo non-rivial factors. An Introduction to Sieving Suppose we have an¡ such thatyz=x2-n. Then !2=f -n (modp) for anype Z, meaning * - n must be a quadratic residue modulop. Ifp is an odd prime which does not divide n, only þ * @lp)) of the p residue classes to which x may belong result in x2 - n being a quadratic residue.i We therefore construct x = rr, 12, ...,t¡¿ (modp), k=fu + @/p)) which specifies these residue classes and start sieving. The sieving does not guafiìntee that each x found results in x2 - n being a perfect square, but it does exclude many ¡ values for which the expression is not a square. The chances of finding a suitable x is improved greatly by applying this approach to a number of different p values. This produces a set of linear congruences, each of which excludes roughly half of its residue classes. If & congruences are used, only about one in 2e numbers will make it through the sieving process to require the test to see if x2 -n is a perfect square. Since finding an x whose correspondingfl - n is a quadratic residue of all ft primes but is not a perfect square is relatively unlikely, most r values that solve the congruences allow us to factor n once,t becomes large. The effectiveness of the sieving can be improved significantly by forming con$uences modulo p2 rather than modulo p since this results in a lower proportion of acceptable residue classes. The interval to be sea¡ched can be bounded easily . We can arbitrarily restrict r > 0, since if ¡2 - j2 = n, then (-x)2 -!2 = n as well. Thus, x>l''lr l. et n is odd, we know that the second term in the factorization (-r + yxr -)) = r must be at least 3, meaning the ffust term (and therefore x) must Ue < L f J. If this range is exhausted without finding a factorization of n, then ¿ is prime. As an example of this procedure, let us factor n = 5917 using the primes 3, 5, and'l. We first construct a table to determine the residue classes to be examined. ¡ (mod p) x¿ (mod p\ 3 0,r,2 0,1,1 I 5 0,1,2,3,4 0,1,2,3,4,5,6 0,1,4,4,r 0,1,4,2,2,4,1 2 2 p 7 n (mod p) i¿-n (mod¿) 2,0,0 3,4,2,2,4 5',.6.2.0.0.2.6 The underlined values in the final column of the table signify the residue classes which cÍìnnot contain perfect squares. The set of congruences to be used is therefore , {øU'¡denotes ttre Iægendre symbol. An Introduction to Sieving (mod 3) x = 1,2 (mod 5) x = 1,4 x = 2,3,4,5 (mod 7) . The interval to be searched goes fromA = [.Æm 1=77 to B = LryJ + I = 1973. There are 289 solutions for x in this range, only one of which leads to a factorization. At x = 79 we find that792 - 5917 = 324 = lS2,giving us the result U=79 + 18=97 ,V=79- 18=61 =) 5917 =6I.97. All of the other solutions for x produce expressions which are not perfect squares; for example, the solution at x = 86 results in 862 - 5gl7 = 1479 = (38.45777)2. flne unusual- ly high proportion of "non-factoring" solutions to "factoring" solutions in this example is prirnlarily due to the very small number of congruences used during sieving, and could be easily decreased by using more moduli. The factoring algorithm is typical of applications of sieving-its usefulness is entirely dependent on the ability of the user to find solutions to a set of congruences quickly. When an efficient method exists, 15 digit numbers can be factored in less than a day even though the algorithm's running time is O(n). To factor values of up to 25 digits, a modified version of the factoring algorithm can be used whose running time is O(^tù U-L741. Although much better factoring algorithms now exist that under suitable heuristics are of complexiry O(eüõfiìõelõs " + o(t)) [Pom89], until 1970 the most efficient means known of factoring an arbitrary large integer was to use a sieving approach [M875]. I.2 THn DSvBI,OPMENT OF SIEVE AUTOMATION Mathematicians have used the technique of sieving as a tool for solving problems in number theory for over 200 years. During that time, a variety of mechanisms have been developed to increase the speed and accuracy of the sieving process. Unfornrnately, those who utilized sieving often published the results of their work with little or no description of the methods they used to obtain them. Some may have felt that little could (or should) be said about a technique that amounted to little more than a brute force search; others may have found the effort of publishing their methods too great to bother with given the limited interest in sieving among mathematicians and computing specialiss. Whatever the reason, the result is that much is unknown about many of the sieving systems used, and what is known has been pieced togettrer from a variety of sources, some of which give conflicting accounts. This section amalgamates this material into a single account that highlights the rnost significant developments in automated sieving. An Introduction to Sieving L.2.1 Sieving By Hand The earliest attempt to apply a mechanical technique to solving the GSP was made by Legendre in 1794 [Rub83]. V/hile his srrþ metllad increased the speed and accuracy of sieving, it was still a rather slow and inconvenient manual technique. Even so, it remained the best method for solving a GSP until well into the 20th cenrury. It is possible that the inspiration for Legendre's invention came from an earlier application of mechanical devices to sieving: the constn¡ cnon of factor nbles. Such tables list the prime factors, or in some cases just the smallest prime factor, for every integer in a specified range, and were widely used by mathematicians in the pre-computer age. Not only did such a table provide a rapid test for properties directly related to a number's factorization, such as primality or the presence of square factors, but it was often helpful in ordinary mathematical calculations, say, allowing the user to obtain a more accurate logarithm for a number by summing the logarithms of its factors. Numerous factor tables were constructed between the 17û and 20ù centuries, starting in 1659 with a uble by Rahn (or Rhonius) extending up to 24,ffi0; a list of early factor tables and their formation is described by J. W. L. Glaisher [Gla78]. The creation of a factor table is a relatively simple process that is based on the sieve of Eratosthenes [.eh18]. All of the integers in the desired interval are written down in a line, then a "2" is written underneath every even number, î"3" under every value divisible by 3, and so on; the table is complete when all primes less than the square root of the upper bound of the table have been processed in this manner. The table can be reduced in size by about 7 5Vo by arranging the numbers in rows of 30 and deleting the 22 columns containing the values divisible by 2, 3, or 5; no significant information is lost since any number divisible by these factors can be spotted easily without using the table. Although a number of early factor tables rtrere created entirely by hand, the fact that multiples of a prime p are separated by exactly p units means that the process of sieving out multiples is very regular. The first to take advantage of this was Ç. F. Hindenburg, who in the mid-1770's utilized a strip of thick paper with a regular pattern of holes (parone) to aid in identifying the multiples ofp. A machine containing a series of rods was also used, and is described by Bernoulli [Ber85]. Hindenburg's table was never published. At roughly the same time, Anton Felkel independently utilized the same approach in beginning the construction of a table that was to extend up to ten million. The Austrian govemment financed the publication of the portion up to 408,000 n 1776, but when it sold poorly An Inroduction to Sieving 9 (probably due to its unorthodox layout) the entire ediúon ,was scrapped to make cartridges for use in the war against the Turks. Only a few copies were saved. l¿ær mathematicians used mechanical aids to produce tables that were more successful. In 1817, Burckhardt used paper stencils to generate and published a table of factors for the integers up to three million; by 1883, similar tables by Glaisher2 and Dase had continued the work up to nine million [Leh18]. Finally, in 1909, D. N. læhmer produced a factor table (and a smaller table of primes) that extended up to ten million, reaching Felkel's goal over 130 years after it was first proposed. Beginning n t924,1æhmer used a different form of sieving to factor large integers: the factor stencil tLE39l. The technique is based on the principle that if a given integer R is a quadratic residue of N, then it is also a quadratic residue of all of the factors of N. Each stencil rcpresented a different R, and had 5000 cells corresponding to the fint 5000 primes. A hole was punched in a given cell only if R is a quadratic residue for the associated prime. Factoring was accomplished by finding a small set of quadratic residues for N and superimposing the stencils for those R; only if all cells in a given position contained a hole could the corresponding prime possibly divide N. Trial division could then be used to show whether any of these primes were factors. For a 10 digit number, less than a dozen quadratic residues were usually sufficient to cut the number of possible factors down to 2 or 3. Although more complicated than refening to a factor table, the factor stencil method had an important advantage: it still gave useful information even if the number to be factored was larger than the stencils were designed to handle. Lehmer's first stencils were constructed largely by hand and only a few copies of ttre entirc set were made, but in 1939 Elder constructed a revised and extended version of the stencils using Hollerith cards; these were easily reproduced and numerous sets were distributed by the Carnegie Institution. Despite the increases in speed and accuracy that these approaches gave, sieving remained a cumbersome technique. One problem was that the work was still done by hand and remained a relatively slow and error-prone process. As well, it was necessary to decide on the limits of the interval to be processed before sieving began. This was no drawback for problems such as the creation of factor tables since the entire interval was always processed regardless of the results obtained, but it presented a major handicap when applied to the GSP. If, for example, the smallest value satisfying a system of congruences lay near the start of the sea¡ch interval, the entire interval was sieved using all but the last 2 tp father of J. W. L. Glaisher. An Introduction to Sieving 10 congruence before the solution was discovered; all of the effort involved in sieving the high end of the interval was wasted. It was not until the advent of the fust automatic sieving machine that these difficulties were eliminated and sieving became practical on a large scale. 1.2.2 Principles of Sieve Automation The periodic behaviour of the sieving process naturally lends itself to the constn¡ction of a machine that can solve the GSP. Consider the task of finding the non-negative solutions to an arbitrary set of È linear congruences r,= rij(modrn) {j == l;'r,'...', I,. *, . The solutions can be found by constructing a table of rnlm7..mkcolumns numbered from 0 to m1m2...mrl. For each congruence, add a row to the table which indicates which values lie in the set of acceptable residue classes, R¡. Any column of the table which satisfÏes all of the congruences represents a solution to the congruences. x-012345678... x=0 (mod2) (a) x=1,2 (mod3) x,=0,2,3 (modS) mod2- {o xr {o xr {o xr {o xr./0... mod3 - xo {r {z *o {t {, xo {r 12 ... mod5 - {o xr {, {, *¿ {o *r {z {3 ... x -0 2) (b) x = 1,2 (mod 3) x = 0,2,3 (mod 5) ¡ =0 (mod - {o xr mod 3 - xe {1 {2 mod 5 - {o xr {2 {3 xa mod,2 x -3 .r=0 (mod2) mod2-xr{o (c) x = 1,2 (mod 3) mod 3 - xe {1 {2 x = 0,2,3 (mod 5) mod 5 - {¡ t¿ {s x1 {2 Figure 1-1. Principles of Sieve Automation Figure l-1 (a) shows a portion of a table for an sxampl€ involving three congruences; the solutions at 2 and 8 are readily apparent. In practice, this sort of table is too large to construct, but since each row of the table exhibits a cyclic pattern corresponding to the list An Introduction to Sieving 11 of acceptable and forbidden residue classes for its associated congruence, the information in the table can be compressed to a small fraction of its original size by recording the pattern of residues only once (Figure 1-1 (b)). Any column of the original table can be generated by shifting each of the rows to the left to advance the appropriate set of residues to the first column; the leftmost residue wraps around to the righnnost end. For example, th¡ee shifts generates column 3 of the original table (Figure l-1 (c)). In general, column r can be obtained by performing r shift operations. From here, it is easy to see how a machine that performs sieving can be constructed. Each congruence used in the problem is represented by a loop, or ring, whose size corresponds to its modulus. The ring for congruence i is built with rn¡ positions, and tags are placed in those slots representing acceptable residue classes. The machine examines one position from each ring at a fixed location called the tap, or window, and simply advances the rings in unison until all of the rings present an acceptable residue simultaneously. A trial counter records the number of shifts performed by the machine, and is used to determine the value of each solution found. The machine can be set up to start searching from any point A by setting r