The latest and possibly fastest of the general factoring methods for large composite numbers is the quadratic sieve of Carl Pomerance. A variation of the algorithm is described and an implementation is suggested which combines the forces of a fast pipeline computer such as the Cray I, and a high speed highly parallel array processor such as the Goodyear MPP. A running time analysis, which is based on empirical data rather than asymptotic estimates, suggests that this method could be capable of factoring a 60 digit number in as little as 10 minutes and a 100 digit number is as little as 60 days of continuous computer time.

Many sequences are most efficiently generated on a digital computer with a sieving procedure in which one represents in the main memory of the machine a set of elements known to contain the desired sequence and then systematically sieves out elements not in the desired sequence. In this expository paper, the technical aspects of programming such sieves are discussed. Special attention is given to the most efficient methods of representing sets in the main memory of the machine as well as the programming difficulties encountered when sieving on these sets. The paper concludes with a discussion of four examples in which sieving procedures were employed.