OASIS: an open architecture sieve system for problems in number theory
Allan Jeffrey Stephens · Mspace (University of Manitoba) · 1990
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 ArchitectureSieve-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 runusing 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.