A basic principle behind RSA is the observation that it is practical to find three very large positive integers , , and , such that for all integers , both and have the same remainder when divided by (they are congruent modulo ):However, when given only and , it is infeasible to compute ^th roots modulo ; that is, for uniform random , it is extremely difficult to find such that .

The integers and form the public key and is the