The security of many public-key cryptosystems relies on the apparent intractability of the computational problems studied in this chapter. In a cryptographic setting, it is prudent to make the assumption that the adversary is very powerful. Thus, informally speaking, a computational problem is said to be easy or tractable if it can be solved in (expected)1 polynomial time, at least for a non-negligible fraction of all possible inputs. In otherwords, if there is an algorithm which can solve a non