Password Less SSH

SSH is linux utility to logon to a remote machine for executing command on it.
Every time you ssh to any machine you need to provide username/password to securely login on that machine.

Once a username/password is authenticated, you are logged on that machine and can execute the commands on the remote machine. But to successfully execute a password on remote machine without human intervention, you need to setup SSH such that it don't prompt for password.
E.g.: Hadoop applications requires that Master machine should be able to login to all the slaves machine in cluster password less SSH.

 Linux SSH utility provides a easy way to achieve the password less SSH.

Create  SSH Keys
     ssh-keygen -t rsa  -f ~/.ssh/id_rsa -P ''
       The options are
         -t rsa: Specifies the type of key to create
         -f Specifies the filename of the key file.
         -P Passpharse. Note: we are using empty passphrase.

Copy the public key on the remote machine.
    scp ~/.ssh/id_rsa.pub user@remote.machine:/tmp/id_rsa_.pub_test

Log on to the remote.machine.

Append the content of the file to .ssh/authtozed_keys.
     cat /tmp/id_rsa_.pub_test > ~/.ssh/authorized_keys

Ensure following on the remote machine.
   -  ~/.ssh has permission set to 700
   -  ~/.ssh/authorized_keys has permission set to 640

Alternatively you could use ssh-copy-id command to copy the public key on the remote machine. ssh-copy-id ensures that the correct permissions are set on the remote machine.

  > ssh-copy-id user@remote.machine

Try to SSH on the remote machine, SSH should not ask for the passphase and you should be logged on the remote server.

Reference:
    ssh-keygen linux man page.
    ssh-copy-id linux man page.

Bitwise Operations Part I

This is the first artical on Bitwise Operation, and today I will discuss how to multiple numbers using bitwise operation.

Before we dwell in the multiplication lets do some quick overview of bitwise left shift operations. Left shift operator is represented by ‘<<’.

Whenever we left shift a number by 1 we move each bit present at position x to position x+1, and append 0 at the position zero (Also, known as LSB.)
Left shift example:

E.g.:

Left shift 13 by 1.
13 is represented as 1101
13 << 1 = 11010

Similarly we want to left shift something by 5 digits, each bit is moved 5 positions to left and last 5 LSB bits are replaced with zero.

13 << 5= 110100000

For multiplication we only need to know about left shift so lets get started.

Example 1: Multiple 13 and 2 To multiply any number represented in binary we need to left shift the number by 1. So, if we want to multiply 13 by 2 we just need to perform 1 operation.
 i.e. 13 << 1
The above operation produces: 11010, which is equivalent to 26 ( 13*2 = 26 )in decimal.

Example 2:  Calculate 170* 2
Binary of 170 is 10101010
Left shift 10101010 < 1 = 101010100 ( 340 in decimal )

Conclusion: Left shift a number by 1 to multiply a number by 2.

The above method can be extended multiply a number by 4,8,16,32 and so on… So, if you want to multiple a number  ‘x’ by 4, multiply the number x with 2, 2 times.
I.e.:

x<<1      // to get x*2 and again
x<<1      //to get x*2*2
/*  The above expression is equivalent to x<<2. */

In general, if we want to multiple a number ‘x’ with another number which can be represented as 2^n, we can get the result by doing x<<n. ( Left shit x by n ) Multiplying x with y, where x  > 1 and y > 1 In binary each bit can take 2 values 0 or 1 and each bit correspond to value which can be determined as follows: If the bit at position n is set, it means that that set bit add 2^n to the total value of the number.

E.g.:

=  1     0     0     1     0      0     0     1 

= 2^7   2^6   2^5   2^4   2^3   2^2   2^1  2^0

= 128   0     0     16    0     0     0    1

= 128 + 16 + 1

= 145

So if we want to multiple any number ‘x’ with 145, how do we calculate the result using bitwise operation.
To demonstrate the working we will multiply 11 with 145 (Result should be 1595.)
In the binary representation of 145, bits at position 7, 4, 0  (0 based positioning. )

Calculation:

= 11 * 145

= 11 * (2^7 + 2^4 + 2^0)

= 1011 * (2^7 + 2^4 + 2^0)              // 11 in binary is 1011

= 1011 * 2^7  + 1011 * 2^4 + 1011 * 2^0 

= 1011 <<7 + 1011 << 4 + 1011 << 0      

= 10110000000 + 10110000 + 1011   

= 11000111011                           // 1595 in binary

= 1595

So to get the result we need to represent the number in terms of power of two.  And then use the bitwise operation and addition to get the result of a complicated multiplication.

GCD and LCM

We learned about LCM and GCD in our 6/7th Standard. The example on WikiPedia explains the GCD, the way we learn it in school.
First, we represent both the number as product of prime numbers.
Then pick the common number, which appear in both the product representation.
Finally, we multiply all the common factors to get the GCD.


Writing a program to calculate GCD based on above algorithm can be a complex and sometimes very slow. Luckily there are algorithms and trick to calculate GCD.

LCM also follows somewhat similar calculation, but if we know the GCD of the 2 numbers we can easilt calculate LCM using 3 simple steps.
1) Calculate product of 2 given numbers.
2) Calculate GCD of those 2 numbers.
3) Divide the product by GCD and we get LCM given 2 numbers.

Here is a simple code in C++ to calculate LCM and GCD using Euclidean algorithm
 

#include <iostream>
#include <assert.h>

using namespace std;

namespace Math {

    int gcd ( int high, int low ) {
        assert ( high != 0 );
        assert ( low != 0 );
        assert ( high > low );

        if ( low == 1 || low == high )
            return low;

        int remainder = high % low;

        if ( remainder == 0 ) {
            return low;
        }
        high = low;
        low = remainder;
        return gcd( high, low );
    }

     int lcm ( int high, int low ) {
        assert ( high != 0 );
        assert ( low != 0 );
        assert ( high > low );

        long product = low * high;
        int gcd = Math::gcd ( high, low );

        return product/gcd;
     }
}

using namespace Math;

int main ( int argc, char* argv[] ) {

  int int_gcd, int_lcm;

  int_gcd = gcd( 20, 10 );
  assert( int_gcd == 10 );
  printf( "GCD( %d, %d) = %d \n", 20, 10, int_gcd );
  int_gcd = gcd( 95, 5 );
  assert ( int_gcd == 5 );
  printf( "GCD( %d, %d) = %d \n", 95, 5, int_gcd );

  int_gcd = gcd ( 49, 14 );
  assert ( int_gcd == 7 );
  printf( "GCD( %d, %d) = %d \n", 49, 14, int_gcd );

 int_lcm = lcm ( 100, 10 );
  printf( "LCM( %d, %d) = %d \n", 100, 10, int_lcm );

  int_lcm = lcm ( 218912312, 67223434 );
  printf( "LCM( %d, %d) = %d \n", 218912312, 67223434, int_lcm );

}

Above program produces following output:

GCD( 20, 10) = 10 
GCD( 95, 5) = 5 
GCD( 49, 14) = 7 
LCM( 100, 10) = 100 
LCM( 218912312, 67223434 ) = 966336792

Refreneces: GCD LCM Euclidean algorithm