Problem Sets

1. Collatz Conjecture

void collatz(unsigned int n){         while (n > 1)         {                  printf("%u -> ", n);                  if (n % 2)                          n = 3*n + 1;                  else n /= 2;
  }         printf("%d", n);}

2. Binomial theorem

(a+b)^n = ∑(n,k)a^k b^(n-k)

A function that is easy to compute but hard to invert is often called a one-way function. In the context of encryption, we desire that ek be an injective and one-way function so that decryption can be performed. Unfortunately, although there are many injective functions that are believed to be one-way, there currently do not exist such functions that can be proved to be one-way.
For a public-key crypto-system, it is not sufficient to fine an injective one-way function. We do not want ek to be one-way from Bob's point of view, because he needs to be able to decrypt messages that he receives in an efficient way. Thus it is necessary that Bob possesses a trapdoor, which consists of secret information that permits easy inversion of ek. So, we say that a function is a trapdoor one-way function if it is a one-way function, but it becomes easy to invert with the knowledge of a certain trapdoor.