A computer is generally considered to be a universal computational device; i.e., it is believed able to simulate any physical computational device with a cost in computation time of at most a polynomial factor. It is not clear whether this is still true when quantum mechanics is taken into consideration. Several researchers, starting with David Deutsch, have developed models for quantum mechanical computers and have investigated their computational properties. We give a randomized algorithm for factoring integers on a quantum computer that takes a number of steps which is polynomial in the input size, e.g., the number of digits of the integer to be factored. This problem has generally been considered hard on a classical computer and has been used as the basis of several proposed cryptosystems, including the widely used RSA cryptosystem. So far, quantum computers are purely thought experiments; it is not clear whether it is possible to build one. However, this does show that simulating arbitrary quantum mechanical systems is at least as hard as factoring.