Programming Techniques

RSA Algorithm Explained with C code

2017-11-06T13:54:00.002+05:45

An RSA algorithm is an important and powerful algorithm in cryptography. It is widely used in Digital Signature and in an SSL. The algorithm works in the following way

Select at random two LARGE prime number $p$ and $q$.
Multiply $p$ and $q$ i.e. $n = p*q$.
Select a small odd integer $e$ which is relatively prime to $\phi(n)$, where $\phi(n) = (p-1) * (q - 1)$.
Calculate the value of $d$ (explained below). $d$ is calculated as a modular multiplicative inverse of $e$ modulo $n$.
Publish the pair $P = (e, n)$ as a public key.
Keep secret the pair $S = (d, n)$ as a private key.

The message is encrypted using $P = (e, n)$ using following formula.

\[P(M) = M^e \text{ mod } n\]

The message can be decrypted using $P = (d, n)$ using following formula.

\[S(C) = C^d \text{ mod } n\]

Secret key pair $(d, n)$ should be kept secret.

Calculation of Modular Exponentiation in C

2017-11-06T08:43:00.002+05:45

Modular Exponentiation takes the following form.
\[A = B^C \text{ mod } D\]
Efficient calculation of modular exponentiation is critical for many cryptographic algorithms like RSA algorithm. The following program calculates the modular exponentiation. The method of repeated squaring solves this problem efficiently using the binary representation of C.

This code is also available on GitHub.

C Code For Solving Modular Linear Equations

2017-11-05T14:41:00.000+05:45

The Extended Euclid's Algorithm solves the equation of the form

\[ GCD(a, n) = d = ax + ny \]

If we multiply the both sides by (mod n), we get

\[ ax + ny \equiv d (\text{ mod } n) \]

This is equivalent to,

\[ ax \equiv d (\text {mod } n)\]

In this article, I present a C Programming Code to solve this type of modular linear equation.

Congruence Modulo

You just saw a weird kind of mathematical expression of the form
\[ A \equiv B (\text { mod } C) \]
This says that A is congruent to B modulo C. What does it mean? Before I tell you the meaning of above operator, please note that this kind of expression is every common in number theory. If you are interested in Cryptography and starting to learn it, you will encounter this operator numerous time. Lets take an example,
\[ 21 \equiv 5 (\text { mod } 4) \]
A symbol $\equiv$ means "Equivalence". In above equation, 21 and 5 are equivalent. This is because 21 modulo 4 = 1 is equal to 5 modulo 4 = 1. Another example is $51 \equiv 16 (\text{ mod } 7)$

The value of x can be more than one depending upon the GCD of a and n. There are always d number of solutions of x where d = GCD(a, n). If a and n are relatively prime i.e. GCD is 1, there is only one unique solution and this is very important for calculating secret key in RSA algorithm.

Extended Euclid's Algorithm C Code

2017-11-05T14:05:00.000+05:45

Before going through this article, please look at my previous article about Euclid's Algorithm. The Extended Euclid's algorithm solves the following equation.
\[GCD(a, b) = d = ax + by\]
In addition to calculating a GCD, it calculates coefficients x and y such that satisfies the above equation. These coefficients x and y are important for calculating modular multiplicative inverses. The Extended Euclid's algorithm is used in a much practical application specifically in cryptography.

The following C code presents the efficient algorithm to solve Extended Euclid's algorithm. The code is also available on GitHub.

Euclid's Algorithm C code

2017-11-05T13:52:00.001+05:45

Euclid's algorithm calculates the GCD (Greatest Common Divisor) for two numbers a and b. The following C program uses recursion to get the GCD.

The code is also available on GitHub.

#include <stdio.h>

int euclid(int a, int b) {
 if (b == 0) {
  return a;
 } else {
  return euclid(b, a % b);
 }
}

int main(int argc, char* argv[]) {
 int a = 30, b = 21;
 printf("GCD is %d\n", euclid(a, b));
 return 0;
}

Fastest Fibonacci Sequence/Number Computation

2017-10-23T23:08:00.000+05:45

The fastest way (in O(n)) of calculating Fibonacci sequence is by using matrix multiplication approach using following relation.
\[\begin{bmatrix}0 & 1 \\ 1 & 1 \end{bmatrix}^n = \begin{bmatrix} F_{n - 1} & F_n \\ F_n & F_{n + 1}\end{bmatrix}\]
Calculating $F_{34}$ is, therefore, multiplying the matrix $\begin{bmatrix}0 & 1 \\ 1 & 1\end{bmatrix}$ 34 times. The $a_{01}$ or $a_{10}$ gives the right fibonacci number. In fact $F_{34}$ can be calculated in less than 34 multiplication in following away.
\[ \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^2 = \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix} X \ \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix} \\
\begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^4 = \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^2 X \ \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^2 \\
\begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^8 = \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^4 X \ \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^4 \\
\begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{16} = \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^8 X \ \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^8 \\
\begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{32} = \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{16} X \ \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{16} \\
\begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{34} = \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{32} X \ \begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}^{2} \\\]
This means, the multiplication can be done in logarithmic time. The C code for this computation is given below (also available on GitHub).

Selection Algorithm (median of medians ) implementation in C

2017-10-19T12:20:00.000+05:45

How do you find out a median of an array? If someone asks you this question, you will immediately say "First sort it and then find the $\left ( \frac{n}{2}\right)^{th}$ element". Of course, this is correct. But what's the runtime? hmmm... the lower bound of any comparison based sorting algorithm is a ceiling of $\log_2(n!)$ which is in order of $\Theta(n\log_2n)$. No matter what sorting algorithm do you use, the running time is $\Omega(n\log_2n)$. Can we do better? That is, can we find a median of an array in linear time?. The answer is yes. The following code calculates the median of an array in $O(n)$ time. The algorithm is called 'Selection algorithm'. This algorithm calculates the '$k_{th}$' smallest value. Median is, therefore, $\left ( \frac{n}{2}\right)^{th}$' smallest element. The algorithm works as follows: (The code is also available on GitHub)

Largest and Smallest Element of an Array in C

2017-10-19T03:33:00.000+05:45

Calculating largest and smallest element in C is straightforward. All you have to do is scan through the array one element at a time and compare it with current largest or smallest value. Since you scan every element of array, there will be n (number of elements in the array) comparisons. Therefore the running time of this algorithm is $\Theta(n)$.

Calculation of Largest Element

int get_largest(int a[], int n) {
 int i, largest = 0;
 for (i = 0; i < n; i++) {
  if (a[i] > largest) {
   largest = a[i];
  }
 }
 return largest;
}

Calculation of Smallest Element

int get_smallest(int a[], int n) {
 int i, smallest = 2147483647;
 for (i = 0; i < n; i++) {
  if (a[i] < smallest) {
   smallest = a[i];
  }
 }
 return smallest;
}

This code is also available in GitHub.

Pyramid and Star pattern generation in C

2017-10-19T02:06:00.002+05:45

Generating pyramid and other star patterns in C extend your knowledge of using a loop in a program. In the program below I have generated various patterns. You can combine the multiple patterns to generate a new pattern. All patterns use for loop. The patterns that the code generates are:

The sample code is also available on Github

#include 
#include 

void pattern_1(int n) {
 int i, j;

 for(i = 0; i < n; i++) {
  for (j = 0; j <= i; j++) {
   printf("*");
  }
  printf("\n");
 }
}

void pattern_2(int n) {
 int i, j;

 for(i = 0; i < n; i++) {
  for(j = 0; j < n - i - 1; j++) {
   printf(" ");
  }
  for (j = 0; j <= i; j++) {
   printf("*");
  }
  printf("\n");
 }
}

void pattern_3(int n) {
 int i, j;

 for(i = 0; i < n; i++) {
  for(j = 0; j < n - i - 1; j++) {
   printf(" ");
  }
  for (j = 0; j <= 2 * i; j++) {
   printf("*");
  }
  printf("\n");
 }
}

void pattern_4(int n) {
 int i, j;
 for(i = n - 1; i >= 0; i--) {
  for (j = 0; j <= i; j++) {
   printf("*");
  }
  printf("\n");
 }
}

void pattern_5(int n) {
 int i, j;
 for(i = n - 1; i >= 0; i--) {
  for(j = 0; j < n - i - 1; j++) {
   printf(" ");
  }
  for (j = 0; j <= i; j++) {
   printf("*");
  }
  printf("\n");
 }
}

void pattern_6(int n) {
 int i, j;

 for(i = n - 1; i >= 0; i--) {
  for(j = 0; j < n - i - 1; j++) {
   printf(" ");
  }
  for (j = 0; j <= 2 * i; j++) {
   printf("*");
  }
  printf("\n");
 }
}

void pattern_7(int n) {
 int i, j;

 for(i = 0; i < n; i++) {
  for(j = 0; j < n - i; j++) {
   printf(" ");
  }
  for (j = 0; j <= 2 * i; j++) {
   printf("*");
  }
  printf("\n");
 }
 for(i = (n - 1) ; i >= 0; i--) {
  for(j = 0; j < n - i; j++) {
   printf(" ");
  }
  for (j = 0; j <= 2 * i; j++) {
   printf("*");
  }
  printf("\n");
 }
}

void pattern_8(int n) {
 int i, j, k;
 for (i = 0; i < n; i++) {
  printf("\n");
  for(k = 0; k < n - i; k++) {
   printf("*");
  }

  for(k = 2*i; k > 0; k--) {
   printf(" ");
  }

  for(k = 0; k < n - i; k++) {
   printf("*");
  }
  

 }
 for (i = 0; i <= n; i++) {
  for(k = 0; k < i; k++) {
   printf("*");
  }

  for(k = 0; k < 2* (n - i); k++) {
   printf(" ");
  }

  for(k = 0; k < i; k++) {
   printf("*");
  }
  printf("\n");
 }
}

int main(int argc, char *argv[]) {
 int n;
 if (argc != 2) {
  printf("Usage: outputfile n\n");
  exit(1);
 }

 n = atoi(argv[1]);

 pattern_1(n);
 printf("\n");
 pattern_2(n);
 printf("\n");
 pattern_3(n);
 printf("\n");
 pattern_4(n);
 printf("\n");
 pattern_5(n);
 printf("\n");
 pattern_6(n);
 printf("\n");
 pattern_7(n);
 printf("\n");
 pattern_8(n);
}

Difference between exports and module.exports in Node.js

2016-03-06T13:09:00.002+05:45

When you have large javascript file, you want to break that file into independent modules so that you can reuse each module in different files. Node.js follows CommonJS module system in which modules are imported using require method available in global scope. For example, lets say you have two files, person.js and main.js. To import person.js functionality into main.js, you would do this

var Person = require('person');

Now you can use methods defined in person.js in main.js using Person variable. To be able to get the Person variable from person.js file, we should have return statement inside the person.js file so that require method assigns return value to the Person variable. person.js would look like this

Sorting Java objects based on property

2016-03-05T10:00:00.001+05:45

In Java, sorting of group of primitive type is simple. That is, sorting of group of integers, floats, doubles or strings is one step process (if you don't use your own algorithm for sorting). java.util provides various methods for sorting these kind of group. Two of them are :

Arrays.sort()
Collections.sort()

Why sorting of group of primitive type is simple?

The answer is Java knows what exactly are those types and how to compare those types to each other. For example, comparing two integers is simply using the logical <, = and > operator. Similar for float, double and strings.

But, if you have your custom type (i.e. class) of data, then Java doesn't know what to do with them. Lets say you have group of people with different properties like height, weight, age, name, religion and so on, and you want Java to sort these people in increasing order. When Java tries to compare two people, it gets confused. It doesn't know which parameter to consider for sorting. Sorting can be done based on height, weight, age etc but which one to take as a parameter to decide?

To solve this problem, you need to explicitly specify the property. Based on the property, comparison should be carried out i.e. if you want to sort people based on their height, you need to tell Java explicitly that I want to sort people based on their height.

Programatically, this can be accomplished using Comparator interface as follows.

Collections.sort(persons, new Comparator () {
        @Override
 public int compare(Person p1, Person p2) {
  return Integer.compare(p1.height, p2.height);
 }
});

Passing implementation of Comparator interface as a second argument to Collection.sort method helps Java to make decision while comparing between two objects.

In above code snippet, you see that you need to implement one method i.e. compare , to carry out this operation. If you closely observe the code you can see we have explicitly specified that sorting needs to be carried out based on height. The compare method returns 3 possible values

A negative integer -> means first argument is less than second argument
Zero -> means both arguments are equal
A positive integer -> means first argument is greater than second argument

A runnable example for sorting is given bellow.

import java.util.*;
class Person {
 // height in cm
 public int height; 
 public String name;
 public Person(int height, String name) {
  this.height = height;
  this.name = name;
 }
}
class CustomSort {
 static void sort(List persons) {
  Collections.sort(persons, new Comparator () {
   @Override
   public int compare(Person p1, Person p2) {
    return Integer.compare(p1.height, p2.height);
   }
  });
 }
 public static void main(String [] args) {
  List persons = new ArrayList<>();
  // add some persons to arraylist
  persons.add(new Person(154, "John"));
  persons.add(new Person(150, "Henry"));
  persons.add(new Person(160, "Smith"));
  persons.add(new Person(162, "Bob"));
  persons.add(new Person(155, "Rubina"));
  persons.add(new Person(170, "Stiva"));
  persons.add(new Person(178, "Bijay"));
  CustomSort.sort(persons);
  System.out.println("Sorted persons based on height");
  System.out.println();
  for (Person person: persons) {
   System.out.println(person.name);
  }
 }
}

Retrofit 2.0 tutorial with sample application

2015-09-30T20:23:00.001+05:45

Retrofit is a HTTP client library in Android and Java. It has great performance compares to AsyncTask and other android networking libraries. Retrofit 2.0 has been released few months back with major update. In this tutorial I am going to talk about how to create a simple REST client in Android that communicates with REST endpoint to perform the READ and WRITE operations. This tutorial is intended for retrofit 2.0 beginner who are using retrofit for first time and getting their hand dirty with retrofit 2.0.

The overview of application that we are creating is as follows. The application has two main components 1) REST client in Android 2) REST server in Node.js. We will focus on REST client as this writing is for retrofit which is client library. We will create REST endpoints that creates and list User. User has two properties., username and name. The program (Client) has two methods; one for creating user and other for listing all the users. Final android application has two fragments in pager view, one has interface for creating new user and another for listing the user. In backend, the program uses Mongodb as database.

Discrete Cosine Transform and JPEG compression : Image Processing

2014-02-07T15:35:00.000+05:45

JPEG is well known standard for image compression and Discrete Cosine Transform (DCT) is the mathematical tool used by JPEG for achieving the compression. JPEG is lossy compression meaning some information is lost during the compression. Lets dig deeper into the JPEG standard starting from the block diagram.

Above diagram shows the encoder part of JPEG. The decoder is the reverse of encoder except it doesn't contains the reverse part of Quantizer block and this is the main reason why JPEG is lossy compression. We cannot recover data lost during the quantization step. The operations performed by each block is presented below

Google Cloud Messaging (GCM) in Android using PHP Server

2014-01-09T15:28:00.000+05:45

GCM for Android is a service which is basically used to send the data from the server to the android devices. One use of this GCM is a push notification service. In this tutorial, I am going through all the steps needed to setup the GCM and build a simple but complete android application in Eclipse.

Logistic Regression in Machine Learning

2013-12-26T12:56:00.000+05:45

Before studying logistic regression, I would recommend you to go through these tutorials.

The first and most important thing about logistic regression is that it is not a "Regression" but a "Classification" algorithm. The name itself is somewhat misleading. Regression gives a continuous numeric output but most of the time we need the output in classes (i.e. categorical, discrete). For example, we want to classify emails into "spam" or "not spam", classify treatment into "success" or "failure", classify statement into "right" or "wrong" , classify transactions into "fraudulent" or "non-fraudulent" and so on. These are the examples of logistic regression having binary output (also called dichotomous). Note that the output may not always be binary but in this article I merely talk about binary output.

Nepal over last Four Decades with R

2013-12-21T23:34:00.001+05:45

The World Bank DataBank provides the data of all countries for more than 1000 indicators since 1960. It can be used for various statistical analysis purpose. This weekend, I downloaded the Data for Nepal, and tried few simple things in R, mainly for the purpose of learning R. R is very powerful statistical analysis tool.

The data was downloaded as csv file, which can be read with read.csv() function in R. We can run the R commands from R command line, and its really interactive.

Gradient descent versus normal equation

2013-12-21T14:23:00.001+05:45

Gradient descent and normal equation (also called batch processing) both are methods for finding out the local minimum of a function. I have given some intuition about gradient descent in previous article. Gradient descent is actually an iterative method to find out the parameters. We start with the initial guess of the parameters (usually zeros but not necessarily), and gradually adjust those parameters so that we get the function that best fit the given data points. Here is the mathematical formulation of gradient descent in the case of linear regression.

Numerical Methods Tutorials

2013-12-10T11:01:00.000+05:45

This section consists of various numerical methods problems and their solution in C language. You can click each link to view the source code of corresponding problem in C.

Note: All the codes are compiled in GCC Mingw compiler in windows. Attempting to compile in other compiler and platform may result errors. These tutorials are targeted for student and for learning purpose, so the code may not be optimized for the actual implementation. Some operations like matrix inversion and determinant are done without pivoting, divide by zero error may result in some cases. Partial and full pivoting are recommended.

Business Intelligence (BI) implementation in Nepalese Telecommunications

2013-11-01T10:41:00.002+05:45

This article aims at discovering the business intelligence technologies that can be applied to the telecommunication industries to facilitate the business process. I have used the data warehouse approach to build the warehouse of telecom data from which various reporting tolls can be used to visualize these data and perform various types of analysis to support the decision making process. Furthermore, I have pointed out some data mining methods that can be added to make it more intelligent as its name "Business Intelligence'. This article shows all the steps from data collection to report generation through warehouse ETC process with related technological background and tools and technologies wherever necessary.

You can download the full article from here.

Linear Regression in Machine Learning

2013-11-01T09:15:00.000+05:45

Linear regression is used in machine learning to predict the output for a new data based on the previous data set. Suppose you have data set of shoes containing 100 different sized shoes along with prices. Now if you want to predict a price of a shoe of size (say) 9.5 then one way of doing prediction is by using linear regression. We train the model based on those 100 data. After training we will have a hypothesis and based on this hypothesis we can predict the price of the new shoe.

Fetch Data from MYSQL using Jquery Ajax

2013-07-22T15:04:00.002+05:45

This is really an interesting article where I will show you how to fetch data from MySQL table using Jquery Ajax. If you are familiar with PHP, then you may already know about how to fetch data using PHP. But in this tutorial, I will show a completely different way of doing this. Ajax is a technology which extracts and displays the web content without loading the full page. I can update a single HTML <div> without loading the full website. Now, lets move to a step by step procedures for pulling all the data out of MySQL table and displaying in HTML table.

The first thing you need to do is create a simple MySQL database with some tables with some data. You can do this using simple SQL query but I have already a data of population of districts of Nepal in my database. I will use it in this tutorial. If you want to display different data then its ok just create a mysql table and insert some data in it.

Solving Knapsack problem using Dynamic Programming

2013-07-18T09:03:00.001+05:45

This is post is basically for solving the Knapsack problem, very famous problem in optimization community, using dynamic programming. But remember this problem can be solved using various approaches with different complexities, but here I shall talk about only dynamic programming, specifically bottom-up approach. So lets first talk about what is Knapsack problem for the people who are unfamiliar with it. The Knapsack problem states that “Given a set of items, each with a weight and a value, determine the number of each item include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible”. Let's consider a concrete example, suppose you have a Knapsack and you have lots of books and articles. You are planning to go somewhere in your vacation and you want to keep some important books and articles with you. The Knapsack has fix capacity so you cannot keep all the books and articles that you got inside the knapsack.

C Mini Project Ideas with a Sample Calculator Project

2013-06-22T17:56:00.001+05:45

Do you want to build a simple application in C but you don’t know how and where to start? Or you know how to build a C application but don’t know any project ideas? then do not worry you are at the right place. If you finished learning C and became familiar with its programming paradigm then I encourage you to build some applications (whether it is application software or system software) to actually sharpen your skills in C. If you do projects, then you will know how to apply those programming constructs accurately in building projects. So here I will explain how to start a new C project for complete beginner and give some projects ideas about what type of application you can build using C language
I have some suggestions for people who are about to write their first C application.

Basic Euclidean vector operations in C++

2013-05-17T15:47:00.001+05:45

Euclidean vectors are very important quantity in mathematics, applied mathematics, physics, engineering etc. Formally vectors are those quantity which have both magnitude and direction. For example velocity. Velocity has both magnitude (Speed, like 2 Km/Hr) and direction (e.g. east). In programmer’s perspective, there are many situation where you need to compute different vector operations. For example consider a moving ball. To simulate the motion of ball, you must calculate the velocity of the ball. The ball has both magnitude (i.e rate of translation of position of center of the ball) and direction (e.g. axis x or y or z). This is just one example but there are various examples where vector operations are essential.
Now in this article, I will show you how to compute different vector operations like, sum of two vectors, multiplication by scalar, dot product, cross product, normalization etc in C++. I choose C++ instead of C because it is object oriented. The vector can be represented by an object. The components of vector along x, y and z axis will be the data member of the object. The data members are attributes of the object. Similarly different operations will be the member functions of the object. Now the vector object can completely represent the vector quantity.

Calculation of Discrete Fourier Transform(DFT) in C/C++ using Naive and Fast Fourier Transform (FFT) method

2013-05-14T02:08:00.001+05:45

Discrete Fourier Transform has great importance on Digital Signal Processing (DSP). There are many situations where analyzing the signal in frequency domain is better than that in the time domain. The Fourier Transform actually converts the function in the time domain to frequency domain, some processing is done in the frequency domain, and finally, inverse Fourier transforms converts the signal back into the time domain. The term discrete means the signal is not continuous rather it is sampled by some sampling frequency i.e. only some samples are taken in a certain interval (also called period). The sampling frequency depends upon the frequency of the original signal and this must satisfy Nyquist criteria. A simple example of Fourier transform is applying filters in the frequency domain of digital image processing. Before looking into the implementation of DFT, I recommend you to first read in detail about the Discrete Fourier Transform in Wikipedia. If you are already familiar with it, then you can see the implementation directly. The 1 dimensional DFT can be calculated by using the following formula