Parallelized factoring operation for the RSA public key - Estrella, Florida Valerio (1997)
A sequential algorithm is a one-step-at-a-time solution to a given problem. This algorithm uses a general purpose, deterministic random access computer which can execute one operation at a time. Parallel algorithm is a solution in which several operations may be executed at the same time in parallel. A parallel algorithm uses a multiprocessor machine having more than one processor working on the problem at the same time. Assume that a sequential algorithm will execute X operations. Using a machine with P processors, the best that can happen from a parallel implementation of the algorithm is that it will run in X/P time. Thus, parallelism can speed up computation. Also, microprocessors have become cheaper and technology for interconnecting them has improved in recent years. It is possible and practical to build general purpose parallel computers containing a large number of processors. A possible application of parallel algorithm is in Cryptology. In the MIT algorithm for Public Key Cryptology, a descryption (secret) key can be obtained from the encryption (public) key by factoring a very large number. Factoring a 200 digit number requires 4 billion years of computer time and factoring a 500 digit number requires 10 to the 25th power years of computer time using the best known algorithm and sequential computers with 1 microsecond instruction time.