of the private key: and the primes from the key generation, These values allow the recipient to compute the exponentiation more efficiently as follows: , , , . This is more efficient than computing exponentiation by squaring, even though two modular exponentiations have to be computed. The reason is that these two modular exponentiations both use a smaller exponent and a smaller modulus. Integer factorization and RSA problem The security of the RSA cryptosystem is based on two mathematical problems: the problem of factoring large numbers and the RSA problem. Full decryption of an RSA ciphertext is thought to be infeasible on the assumption that both of these problems are hard, i.e., no efficient algorithm exists for solving them. Providing security against partial decryption may require the addition of a secure padding scheme. The RSA problem is defined as the task of taking th roots modulo a composite : recovering a value such that , where is an RSA public key, and is an RSA ciphertext. Currently the most promising approach to solving the RSA problem is to factor the modulus . With the ability to recover prime factors, an attacker can compute the secret exponent from a public key , then decrypt using the standard procedure. To accomplish this, an attacker factors into and , and computes that allows the determination of from . No polynomial-time method for factoring large integers on a classical computer has yet been found, but it has not been proven that none exists; see integer factorization for a discussion of this problem. Multiple polynomial quadratic sieve (MPQS) can be used to factor the public modulus . The first RSA-512 factorization in 1999 used hundreds of computers and required the equivalent of 8,400 MIPS years, over an elapsed time of about seven months. By 2009, Benjamin Moody could factor an 512-bit RSA key in 73 days using only public software (GGNFS) and his desktop computer (a dual-core Athlon64 with a 1,900 MHz CPU). Just less than 5 gigabytes of disk storage was required and about 2.5 gigabytes of RAM for the sieving process. Rivest, Shamir, and Adleman noted that Miller has shown that – assuming the truth of the extended Riemann hypothesis – finding from and is as hard as factoring into and (up to a polynomial time difference). However, Rivest, Shamir, and Adleman noted, in section IX/D of their paper, that they had not