Massively distributed computing and factoring large integers

ABSTRACT

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.

REFERENCES

• 1: Bressoud, D.M Factorizatrion and primality Testing. Springer-Verlag. N.Y., Berlin, Lindon, Paris, Tokyo, 1989.
• 2: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 3: Carl Pomerance , J. W. Smith , Randy Tuler, A pipeline architecture for factoring large integers with the quadratic sieve algorithm, SIAM Journal on Computing, v.17 n.2, p.387-403, April 1988 [doi>10.1137/0217023]
• 4: Hans Riesel, Prime numbers and computer methods for factorization, Birkhauser Boston Inc., Cambridge, MA, 1985
• 5: W G Rudd , Duncan A Buell , Donald M Chiarulli, A high performance factoring machine, Proceedings of the 11th annual international symposium on Computer architecture, p.297-300, January 1984
• 6: Smith J.W., and wagstaff Jr,. S.S An extended precision operand computer. In Proceedings of the }Twenty-Firstr southeast Region ACM Conference (1983), 209-216..

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  D. Software
  D.1 PROGRAMMING TECHNIQUES

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Performance, Security, Theory