Several public-key cryptography algorithms, such as RSA and the Diffie–Hellman key exchange, are based on large prime numbers (for example 512 bit primes are frequently used for RSA and 1024 bit primes are typical for Diffie–Hellman.). RSA relies on the assumption that it is much easier (i.e., more efficient) to perform the multiplication of two (large) numbers x and y than to calculate x and y (assumed coprime) if only the product xy is known. The Diffie–Hellman key exchange relies on the fact that there are efficient algorithms for modular exponentiation, while the reverse operation the discrete logarithm is thought to be a hard problem.
Other related articles:
... Indistinguishability under Chosen Plaintext Attack (IND-CPA) is commonly defined by the following game A probabilistic polynomial time-bounded adversary is given a public key, which it may use to generate any number of ciphertexts (within polynomial bounds) ... The adversary generates two equal-length messages and, and transmits them to a challenge oracle along with the public key ...