Tuesday, September 28, 2010

Find a prime number in Java - Algorithm

Simple? Oh yea, it is! But to what extent we can programmatically optimise it? Le'me show you -

Some theory

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

One brute force is to loop through i:0->n : and find out if n is divisible by i. Complexity is O(n) here. But can we optimize it.

Yes. Here are the rules to find a prime number -

  • Number has to be > 1
  • Number cannot be even (Other than 2. 2 is prime). Because even numbers are always divisible by 2. This reduces the number to half.
  • If you list out all of the factors of a number, the square root will always be in the middle. So when checking factors, we need not check 0 to n. Check only upto square root of n, that should cover all possible factors. This further reduces the comparisons to sq. root of n, and that too excluding all evens.

Java Code

package main.java.algo;

public class IsPrime {
 // if you list out all of the factors of a number, the square root will always be in the middle
 public static void main(String[] args) {
 // checks whether an int is prime or not.
 boolean isPrime(int n) {
  //prime is natural number greater than 1
  if(n <= 1)
   return false;
  // but ignore 2, as 2 is a prime number
  if(n == 2)
   return true;
  // check if n is a multiple of 2
  if (n % 2 == 0)
   return false;
  // if not, then just check the odds : note -> i += 2
  // check only upto square root of a number
  for (int i = 3; i * i <= n; i += 2) {
   if (n % i == 0)
    return false;
  return true;


Monday, September 27, 2010

Generate public key ssh-keygen & authorize without password

I was recently working on public key cryptography to regenerate my ssh keys and login into remote machines with password. Recording the bits here -

Generating Public Key

Backup your ~/.ssh

Use ssh-keygen to generate you .ssh keys

ssh-keygen -t rsa
Generating public/private dsa key pair.
Enter file in which to save the key (/Users/username/.ssh/id_dsa): [RETURN]
Enter passphrase (empty for no passphrase): [Enter a secure passphrase then RETURN]
Enter same passphrase again: [Repeat the same secure passphrase then RETURN]
Your identification has been saved in /Users/username/.ssh/id_dsa.
Your public key has been saved in /Users/username/.ssh/id_dsa.pub.
Similarly, generate the dsa key

ssh-keygen -t dsa
Once the SSH key has been generated, you can safely share public key. Just include the contents of the ~/.ssh/id_dsa.pub.

Both DSA and RSA are digital signature algorithms, DSA is faster for signature generation but slower for validation.

SSH to any machine without prompting for password.

Login into that machine with your username

ssh username@remotehost
username@remotehost's password: ********
remotehost:~ username $ mkdir .ssh
remotehost:~ username $ exit
From your local machine where ssh key was generated -

scp -p ~/.ssh/authorized_keys username@remotehost:~/.ssh/
username@remotehost's password: ********

Authorize localhost access without password: [ssh user@localhost] 

cd ~/.ssh
cp id_dsa.pub authorized_keys