Walk Through of RSA Public-key Encryption for Beginners - Part III:Bijection Functions


Today we wil be going over bijection functions. We will proceed to understand:

  1. What is a function?
  2. What is onto function?
  3. What is one-to-one function?
  4. What is bijection function?
  5. What make a function bijection?

  6. What is a function?

A function can be viewed a mapping from elements in set A to elements in set B. For input x in A (domain), output f(x) must be in B (range). We can also denote such function f as f: A—>B

2.What is onto function

An onto function is a function that for everyone output f(x) in B, there is an pre-image of it in A. In other words, all elements in B is linked to some element in A.

See the image below;

F is not onto where as G is. 

 3. What is one-to-one function

A one-to-one function is a function that  for all a, a' in A, if f(a)= f(a') , then a=a'. 

In other words, elements in A cannot share the an element in B. 

See the image below;

F is one-to-one while G is not.

  1. What is a bijection function.

A bijection fuction is both onto and one-to-one.

5.What make a function bijection?

Lemma: If a function f maps set A–>A, and it has an inverse function g(x) such that g(f(x))=x, then f is a bijection function. 

We will leave the proof of the above Lemma as an exercise. 

« Walk through of RSA public-key encryption for beginners - Part II: Some Background On Modular Arithmetics Walk through of RSA public-key encryption for beginners - Part I : An introduction »