Something Unimaginable !

Though I'm late but still I won't stop myself.Wishing everyone a very happy and prosperous diwali .

This is the first time I was participating in ACM ICPC regionals and we got selected for one but the sad part is that we got selected just because of the rules of the competition .

According to the rules of the competition - Firstly, those teams will be selected which have solved at least 1 question and are first from their college,if slots are left then teams will be selected from the rank list according to the merit.

As you can see that it may happen that from a college where many good programmers are participating a highly potential team may not get entry to the regional while a not so good team may get it easily.

Let me show you an example - Suppose there are two colleges X,Y

X is a very big and renowned college and has around 50 good programmers .

Y is not so big college and doesn't have programmers at par with X .Lets say somehow, Y comes up with 1 team.

In the contest around 7 teams from X solve 2/5 problems , 8 teams solve 3/5 problems and 2 teams solve 4/5 problems .

On the other hand team from Y manage to solve 1/5 'the easiest of all problem' and gets rank 1 in their college.

So, according to the rules it may happen that the teams which solved 3/5 problems don't get selected as they are not the best in their college but as Y's team was the best in their college it will get entry to the regional. Sounds unfair right ?!

That's what happens every year in the Olympics of programming ACM ICPC .

 Nevertheless , we got selected and we should try our best to prove our selection right. 

We missed Kharagpur online contest.It was scheduled at 2 to 5 PM and due to our negligence we thought that it is at 6 to 9 PM because for Amritapuri regional it was from 6 to 9 PM .

I came to know about this at around 5:45 and we were dumbstruck. This was one of the biggest mistake we would have ever done but I told my teammates not to worry about anything we still have Amritapuri and we will give our best there.

Surprisingly on Diwali day I got a surprise that due to some reasons they are re conducting the contest on Oct 30 and luckily, very luckily we got another chance for the contest. This time we won't make any mistake .

This week I solved problems from SPOJ and participated in codeforces round also . After a very long time I again participated in the online contest on codeforces and stood 1285 from around 2000 contestants . 

Question: Is it time to change the selection procedure ICPC regionals ? Leave your comments below .

ACM !

So, its official now . My team got selected for ICPC onsite regional of Amritapuri !

Though, our performance was very bad but we got selected as we were the best team in our college.
We would like to make a mark in our first ever regional . Lets see what happens in the coding arena .

These days I'm learning and coding as much as I can . Expanding my armory with new techniques ranging from geometry to DP ,from bits to graphs.

After a long time I participated in a timed contest on codechef and stood 852 out of around 2500 contestants . Not one of my best but still good enough for a start after a very long time .

Yesterday I solved a question based on breadth first search and it felt so great after solving that as it was my first bfs problem . I was waiting for this for a long time .

Thanks for reading and keep coding !

Decrypting RSA cryptosystem

This week I was busy in making my Computer Science presentation . I chose prime numbers as the topic of my presentation .

Here are some of the highlights from my presentation .

We all know what are prime numbers right ? ok let me remind you again . Prime numbers are those natural numbers which are greater than 1 and doesn't have any positive divisors other than 1 and the number itself ,

Then I presented a very simple way to generate prime numbers Sieve of Eratosthenes if you don't know what is it you can check Sieve of Eratosthenes for more details .

You must be thinking that ok prime numbers are difficult to find but what are their real world applications ? How are they useful to a layman ?

Interestingly, a layman and you too might be using prime numbers that too almost daily! How ?

We all have accounts on google,facebook,twitter,etc,. and we do online shopping also from websites like amazon,ebay,flipkart,etc,.

To keep our personal data secure these sites use some form of cryptosystem to secure our invaluable data such as messages,passwords,credit card numbers,etc,.

They use some form of RSA cryptosystem for this .

RSA algorithm is one of the most widely used algorithm in today's world . Our cyber safety relies on this method . Let's have a look how this algorithm protects us from the hackers.

Working of RSA cryptosystem -

STEP 1 - Key generation

    Public key -
    Host sites randomly generate two very large prime numbers P,Q and multiply them to get N

    For ex lets say P=53 & Q=59
    N = P*Q = 3127
    N is the first part of the public key.
    second part of the key e is selected according to the constraints that e should be 1<e<phi(N) and         gcd(e,phi(N))=1 , where phi() is Euler Totient Function.
    Click here for algorithm for gcd()
   for simplicity lets say e = 3 in our example.
   Public key is made public .That means everyone has access to numbers e and N.

  Private key -    

  This is the secret key which is not made public and is only available to host .
 
  Representing it by d it is calculating by solving d*e mod phi(N) =1 (euler's theorem is used for    calculation).

Now, you must be thinking that anyone can calculate d as everyone know N and e .This is where beauty of prime numbers lie :) .

RSA works on the principle that  Prime factorization of a number is a fundamentally hard problem . It take a lot of time to factorise a big number .It can take 1000s of years to break a very big number even with network of supercomputers with the current level of technology!

remember phi() function ? to calculate phi(N) we need to have factorisation of N known to us .

If calculation of phi is so much hard how host does it ? :) Its because host knows the factorisation of N which is P*Q and phi(Prime no.) = Prime no. - 1 and phi also obeys multiplicative property so phi(P*Q)=phi(P)*phi(Q)

STEP 2 - Encryption

Suppose user is sending a message "HI"
This message is converted to a number m by a generalised padding scheme . For simplicity lets convert alphabets to numbers according to their order i.e, A-1,B-2,C-3 and so forth.
so in our example HI gets converted to 89 H->8 I->9

Then by applying N and e on m our web browser encrypts m to c like this m^e mod N = c
Then it sends c to the host.

STEP 3 - Decryption

Host receives c and applies its secret private key d on it to get m like this c^d mod N = m
Then by reverse applying padding scheme on obtained m host gets "HI" .

This is how our data is secured. Thanks to prime numbers.

Some interesting facts -

Till now the biggest key broken is a 768 bit key . It took a team of 11 cryptographers to break it and that too in 2 years!

With present level of prime factorization technique and computational ability it is estimated that a 1024 bit key can be broken within some years.

As 1024 keys are vulnerable now, google upgraded its SSL key from 1024 bit to 2048 just 1 year back. Twitter also uses 2048 bit keys.

It is estimated that by 2030 even 2048 bit keys will be vulnerable to attacks.    

If you can break a 1024 bit key you can become famous ! and till now nobody has done that.

So,now whenever you are making an online transaction stay relaxed for security reasons as prime numbers are there to keep your data secure .

I hope you enjoyed this write up on application of prime numbers .If you want to ask or correct my mistakes do comment in the comment box .

If you liked my post subscribe to my blog for more such exciting posts . Thank You 

Triangle Triangle everywhere not a point to think

Suppose we have 3 points which are making a triangle and we need to find whether a given point P is in the triangle or not .

There are many ways to do this problem but a very simple method is -

Lets say the triangle is made by three vertices A,B,C and the coordinates of the points are (x1,y1) , (x2,y2) , (x3,y3) and lets say point P is (a,b) so we just need to check whether the sum of the area of the triangle formed by the points A,B,C taken 2 at a time and P is equal to the area of the triangle ABC or not . Not getting it right ? No need to worry at all :)

Let ar(ABC) denotes the area of the triangle ABC. So, we just need to check whether

ar(ABC) = ar(ABP) + ar(BCP) + ar(CAP)

we can calculate the area of the triangle by the formula -
area = abs((x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2))/2.0)

If it is equal then the given point P is in the triangle ABC .

To understand it better lets look at the figures below -

When P lies inside the triangle ABC

In this figure P is inside the triangle ABC and this can be easily seen that ar(ABP) + ar(BCP) + ar(CAP) = ar(ABC)

so we conclude that P lies inside ABC .

When P lies outside the triangle ABC

 In this figure P is outside the triangle ABC so the ar(ABP) + ar(BCP) + ar(CAP) is not equal to ar(ABC) as they include additional area of triangles BDP and DCP . 

TIP :  This observation can be applied to find whether a given point lies inside a given n-polygon or not by taking the area of triangles and equating it to the total area of the polygon . 

I hope you would've found this post informative and useful . For any suggestions just post a comment below. 

Have a good day . 

Gaining the momentum

This week I was revising my previously learned algorithms/theorems . This includes sieve of Eratosthenes,Game theory,modular exponentiation,etc,.

Its time to increase my knowledge base . These days instead of participating in online contests(other than ACM related) I'll be only learning new things and posting about them in detail in my coming posts . So, stay tuned for some amazing stuff coming shortly ;)

I was also trying my hands on application development . I am learning to make a simple calculator using C++ .

Thanks for reading .