Massively distributed computing and factoring large integers

Over the last 15 years the increased availability of computers and the introduction of the RSA cryptosystem has led to a number of new and remarkable algorithms for finding the prime factors of large integers. Factoring numbers is an arithmetic problem so simple to understand that school children are asked to do it. While multiplying or adding two very large numbers is simple and can be done quite quickly, the age-old problem of trying to find a number that divides another number still has no simple solution. Computer science has reached a point where it is starting to custom tailor the design of computers toward solving specific problems. This pracnique will discuss some of the more recent algorithms for factoring large numbers and how networks of computers can be used to run these algorithms quickly. Since this is a general exposition, we do not give detailed mathematical descriptions of the algorithms. We also allow ourselves to be somewhat casual with mathematical notation in places and hope that the mathematically sophisticated will forgive the looseness.

View this article in the ACM Digital Library.