My Tryst with CS

In this post I would like to talk about the Chinese Remainder Theorem. You might have heard this problem as a kid: There are x number of things. When taken in groups of 5, they leave a remainder 1. When taken in groups of 7, they leave a remainder 2. When taken in groups of 9, they leave a remainder 3. And when taken in groups of 11, they leave a remainder 4. Find the value of x. We will see how such problems can be solved using the Chinese Remainder Theorem(CRT). LINEAR CONGRUENCES Lets talk about linear congruences. You might have already encountered them informally in my previous post on the RSA encryption system. Here I would like to introduce it a bit more formally. ax ≡ b (mod n) Abusing the use of notation, we can express this equation into a form which might look more familiar, i.e ax%n = b. In other words, the integer ax when divided by n leaves a remainder equal to b. Lets say that we find a solution to the above equation, say x = x 0 . => ax 0 ≡ b (

THE NEED OF ENCRYPTION In today's world where a lot of secured information like our credit card number, passwords etc., travel around the web, the presence of a secure encryption system is almost inevitable. We want a method to encrypt a message, send it over the insecure internet connection and allow only the receiver to be able to decrypt and read the original message. This exact problem was solved by R ivest, S hamir and A dleman(RSA) in the year 1978, in their paper A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. In this post, I will try to explain the method they adopted to create a secure encryption system. PUBLIC KEY CRYPTOSYSTEM A public key cryptosystem has the following properties: 1) D(E(M)) = M, if we decrypt an encrypted message, we should get back the message. 2) Both E and D should be easy to compute, if it takes days to encrypt or decrypt the message, then the cryptosystem is not very useful. 3) By publicly revea

MIN CUT We have already talked about the maximum flow problem. Now is a good time to talk about a seemingly different but actually quite similar to the maximum flow problem, i.e the min-cut problem. A cut is defined on two vertices A and B such that we can partition all the vertices of the graph into two sets such that A and B do not belong to the same set. Going by this definition an s-t cut can be defined as a partition of the vertices of a graph such that the source and the sink are not in the same partition. Now we associate with a cut, what is called the capacity of the cut . It is defined as the sum of the flow of edges that go out of the cut. We do not consider the edges coming back into the cut as we want an upper bound on the amount of flow that can go out of the cut. Formally the capacity of a s-t cut is defined as:  where δ + (A) is used to denote the set of edges sticking out of A. (Similarly we will use δ - (A) to denote the set of edges sticking into A)

PROBLEM DESCRIPTION The problem of finding the maximum flow in a network, has a history which dates back to the second world war. Practically the maximum flow problem can be stated as:  “A list of pipes is given, with different flow-capacities. These pipes are connected at their endpoints. What is the maximum amount of water that you can route from a given starting point to a given ending point?” or equivalently “A company owns a factory located in city X where products are manufactured that need to be transported to the distribution center in city Y. You are given the one-way roads that connect pairs of cities in the country, and the maximum number of trucks that can drive along each road. What is the maximum number of trucks that the company can send to the distribution center?” Formally stated the problem is: We are given a network - a directed graph, in which every edge has a certain capacity c associated with it, a starting vertex (called the source), and an ending ver