Will edit later. =]]]

Today I’m going to demonstrate how to perform a Caesar Shift, solely using a UNIX or Linux command prompt. The Casear Cipher is a basic text transformation that shifts each letter of a given plaintext message up by ‘x’ amount of characters. For example, using a shift of 1, all A’s would becoming B’s and all F’s would become G’s. If you’d like to find out more, you should probably hit up Wikipedia.

Because Julius Caesar preferred to use a Caesar Shift of 3 for all his encoded military communications, I’ll also use a shift of 3 for my demonstration. It’s a simple matter of piping the tr (translate) command onto your basic cat command that displays a file. The left hand side of the tr expression represents the text to be changed and the right hand side represents what it should be changed into. For example, tr ‘a-z’ ‘r’ would change every single lowercase letter in a file to ‘r’. The command tr ‘a-z’ ‘A-Z’ would capitalize every letter in a file. And the command tr ‘a-m’ ‘n-z’ is partially a Caesar Shift in that all letters from a to m are translated into their corresponding letter from the range ‘n-z’ (a becomes n, b becomes o, etc). However, the letters n through z in the original file will remain unchanged because we did not include them on the left hand side of the expression. All letters must be included. Study the following code to see how the cipher is actually implemented.

$ cat > plaintext
Hello World.
$ cat plaintext | tr ‘a-zA-Z’ ‘d-za-cD-ZA-C’
Khoor Zruog.

To decrypt the cipher text, we simply invert the operation by doing it in reverse order. I’ll pipe on a decryption command to the end. We’re really just doing decrypt(encrypt(plaintext)), which should result back into the plaintext. So let’s try that.

$ cat plaintext | tr ‘a-zA-Z’ ‘d-za-cD-ZA-C’ | tr ‘d-za-cD-ZA-C’ ‘a-zA-Z’
Hello World.

The result is just as we expected it – only the plaintext is shown. Again, D(E(M)) = M. Here it is in action:

Note that everything above was done on Linux and would not work properly on our Sun Solaris box. Using the above code, I determined that UNIX recognized ‘a-z’ as three characters (a, -, and z) instead of a range of letters. To specify it as a range of letters, you’ll need to enclose the letters in square brackets. You also won’t be able to crunch all of the ranges together like this: ‘[a-zA-Z]‘. Each range will need to have its own individual brackets around them. So we end up with something like this:

$ cat plaintext | tr ‘[a-z][A-Z]‘ ‘[d-z][a-c][D-Z][A-C]‘

Hope you enjoyed the tutorial. I’ll be posting some crypto using really basic Linear Algebra soon.. just standard matrix multiplication. Still interesting though.

Today we’re going to have some fun with prime numbers!! Because they’re that awesome!! Specifically, we’ll be focusing on figuring out just how fast we can generate prime numbers. So if you’re not a Computer Science major, I’d recommend you stop reading this. If you do decide to continue reading my upcoming prime number articles, I’ll eventually be able to teach you how to crack a 56-bit RSA key in mere minutes using a single home computer. Back in 1997, it took a group of 4,000 teams using tens of thousands of computers linked over the Internet 210 days to crack this code. Wow!

How do you determine if a number is prime?

A prime number is only divisible by 1 and itself. This should be familiar to you.. this is stuff from elementary school. For example, even numbers aren’t prime because they are all divisible by 2. The numbers 6 and 9 aren’t prime because they are both divisible by 3. Again, a number is prime if it’s divisible by just 1 and itself. As an example, 11 is prime because the only two numbers that can be multiplied to get this are 1 and 11. So in order, the first string of prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, and 23. I assume you’re getting the idea by now. So.. let’s find some primes.

Setup

To do this experiment, I’ll be using my laptop, which contains an Intel Core 2 Duo T9300 (2.50 GHz), 4 GB of RAM, and runs on Ubuntu Linux. We’ll be using the Java programming language. I’m going to give you the code that most people would start out with if given the task to find the first 100,000 prime numbers. And then we’re going to continually make improvements on this code. You’ll find that our initial code will take a ridiculously high amount of time to complete; depending on how many numbers you’re trying to find, it can take hours or even days. But we’ll eventually conclude with an optimized code that can find the same amount of numbers almost instantaneously.

The BigInteger Class

Please note that when you start dealing with modern cryptography, there will eventually come a time when you will be unable to use primitive data types. Recall that an int can only hold 32 bits (numbers up to 2^32, which is 2,147,483,647) and a long can only hold 64 bits (numbers up to 2^64, which is 9,223,372,036,854,775,807). For anything larger than that, we’ll need to use the java.math.BigInteger class. A quick Google search reveals that the 10 millionth prime number is 179,424,673. And 32 bits is easily enough to hold this. So for today’s purposes, we won’t be using the BigInteger class.

The Standard Amateur Code

So here’s the first thing that enters every amateur programmer’s mind, including my own. By definition, a prime number is only divisible by one and itself. So all we have to do in order to tell if a number is prime is try dividing it by every single number that is smaller than it. And if we find something divisible besides 1 and itself, we know the number isn’t prime. Seems like pretty good logic. How do we tell if a number is divisible? Divide it and see if there is a remainder or not. To check for a remainder in Java you use the modulus operating, which is represented by a % symbol. It will divide one number by another number and return the remainder to you. For example, 9 % 3 returns the value 0. How is this useful to us? By not having a remainder, we now know that 9 was divisible by 3. Thus, 9 is not prime. So to code this, let’s go ahead and make a loop that checks every single number to see if it’s prime.

package net.justinburr.math;

public class PrimeNumberFinderV01 {

   public static void findPrimes(int numPrimesNeeded) {
      int numPrimesFound = 0;
      int currNum = 2; // Start checking at the first prime number.
      int divisor;
      boolean isPrime;

      while(numPrimesFound < numPrimesNeeded) {
         divisor = 2;
         isPrime = true;
         while(divisor < currNum) {
            if(currNum % divisor == 0) {
               isPrime = false;
            }
            divisor++;
         }

         if(isPrime) {
            System.out.println(currNum);
            numPrimesFound++;
         }

         currNum++;
      }
   }

   public static void main(String[] args) {
	  int numPrimes = 100000;
      long timeStart = System.currentTimeMillis();
      findPrimes(numPrimes);
      long timeEnd = System.currentTimeMillis();
      System.out.println("It took " + ((timeEnd - timeStart)/1000) +
            " seconds to find " + numPrimes + " prime numbers.");
   }
}

The 100,000th Prime Number Found: 1,299,709
It took 8223 seconds to find 100000 prime numbers. (2 Hours, 17 Minutes, 3 Seconds)

Gooooooood lord – the time it took was atrocious!! As you can see, the code isn’t very efficient. In fact, it’s probably about the worst piece of code you could possible write. However, you do get the correct results and the logic behind it is easy to understand. I recommend you analyze this code and understand it before moving on. Then we’ll have a look at what can be improved.

Various Tweaks, Including The ‘Odd Candidates Only’ Method

First of all, remember how I said that even numbers cannot be prime? With that in mind, why in the hell are we bothering to check EVERY single number? Let’s cut the program’s runtime down by only checking the odd numbers – that’s half as many numbers and it’s an easy fix. To do this, we simply increment the current number by 2 instead of 1 each time it does a prime check. However, this creates a small problem because the first number we are checking is even, thus we end up skipping all the odds. So all we have to do to fix this is change the starting number from 2 to 3. And we’ll just hard code in that we want to print out the number 2. So we make the following changes:

Original Code:
currNum++;

Replace With:
currNum = currNum+2;

Original Code:
int currNum = 2;

Replace With:
int currNum = 3;

Add Before Our Loop:
System.out.println("2");

Original Code:
int numPrimesFound = 0;

Replace With:
int numPrimesFound = 1;

And since we’re only looking at odd numbers now, why are we bothering to check if 2 is a divisor? An odd number divided by two will always produce a remainder.

Original Code:
int divisor = 2;

Replace With:
int divisor = 3;

So what other changes can we make? Let’s use the similar concept of not wanting to check more numbers than we have to. Because our smallest divisor is 3, the highest possible number that can be multiplied by to hit our currentNumber (n), is of course, n/3. Simple math. 3 * (n/3) = n; So go ahead and change that as well (adding an = sign I should note).

Original Code:
while(divisor < currNum) {

Replace With:
while(divisor < (currNum/3)) {

There is also no reason to continue checking divisors for a number after we’ve already determined that it isn’t prime. When that happens, let’s stop and move onto the next number. So there are two ways to do this… you can either add an additional condition to our while loop OR you can insert a break statement. Many consider break statements bad form. You can do a google search if you’d like more information on this, but I’m just going to go ahead and add a break statement into our code. I feel it’s significantly easier to understand in this situation.

Add this after setting isPrime to false:
break;

Alternatively, you could have done this instead:

Original Code:
while(divisor <= (currNum/3)) {

Replace With:
while((divisor <= (currNum/3)) && isPrime) {

So let’s take a look at what we have so far and see how long the program takes to finish.

package net.justinburr.math;

public class PrimeNumberFinderV02 {

   public static void findPrimes(int numPrimesNeeded) {
      int numPrimesFound = 1;
      int currNum = 3;
      int divisor;
      boolean isPrime;

      System.out.println("2");

      while(numPrimesFound < numPrimesNeeded) {
         divisor = 3;
         isPrime = true;
         while(divisor <= (currNum/3)) {
            if(currNum % divisor == 0) {
               isPrime = false;
               break;
            }
            divisor = divisor + 2;
         }

         if(isPrime) {
            System.out.println(currNum);
            numPrimesFound++;
         }

         currNum = currNum+2;
      }
   }

   public static void main(String[] args) {
	  int numPrimes = 100000;
      long timeStart = System.currentTimeMillis();
      findPrimes(numPrimes);
      long timeEnd = System.currentTimeMillis();
      System.out.println("It took " + ((timeEnd - timeStart)/1000) +
            " seconds to find " + numPrimes + " prime numbers.");
   }
}

The 100,000th Prime Number Found: 1,299,709
It took 201 seconds to find 100,000 prime numbers.

Wowzers! We went from an algorithm that took over two hours to an algorithm that takes a mere 3 minutes. It’s amazing what our subtle little changes to the code were able to do. I’m sure there are further improvements that can be made to this algorithm, but at this point we need to start to looking to make significant improvements or perhaps use a different algorithm altogether.

The Square Root Method

Recall in our previous algorithm that we were only going to have the divisor increment until (n/3). Because we start checking divisors at 3, multiplying divisors by more than (n/3) would produce a number that overshoots our number n. So with this in mind, maybe there are other restrictions on just how high the divisor can be before we cease to find anything. Let’s just pretend our current number is 81. Using our previous logic that the divisor must be less than (n/3), we found that it’s only useful to check numbers up to 27. But do we really want to be checking that high? The number 27 does divide into 81.. but we have actually already checked this number (when we did calculations using the divisor 3). So because using (n/3) as a max ends up re-checking numbers, it would seem logical that we can make due with an even lower number than (n/3). But what? At what point does the re-checking of numbers begin? One factor that we know isn’t being re-checked is 9*9, as it is only checked when the divisor is 9. Is that the highest divisor we need to check? Well, let’s think about it. With the divisor 10, we would have to multiply that by a number a little bit over 8 in order to get 81. As we increase the divisor by 10, the number we would have to multiply by gets smaller and smaller. And these smaller numbers, as we know, have already been checked. So it looks like 9 is the highest number we’d have to check in order to find factors for 81. Try it – there can be NO factors in which both numbers are greater than 9. It’s simply not possible. I explained this a little more than I needed to, but hopefully you understand now that we only need to increment the divisor up to the square root of n. We could use “divisor <= Math.sqrt(currNum))”, but square roots are nasty. Why don’t we just square both sides instead? Let’s use “divisor * divisor <= currNum”. This simplifies things. It will also eliminate the need for us to import the java.Math class. So let’s go ahead and make this single change in our code and then see where we’re at.

Original Code:
while(divisor <= (currNum/3)) {

Replace With:
while(divisor * divisor <= currNum) {

package net.justinburr.math;

public class PrimeNumberFinderV03 {

   public static void findPrimes(int numPrimesNeeded) {
      int numPrimesFound = 1;
      int currNum = 3;
      int divisor;
      boolean isPrime;

      System.out.println("2");

      while(numPrimesFound < numPrimesNeeded) {
         divisor = 3;
         isPrime = true;
         while(divisor * divisor <= currNum) {
            if(currNum % divisor == 0) {
               isPrime = false;
               break;
            }
            divisor = divisor + 2;
         }

         if(isPrime) {
            System.out.println(currNum);
            numPrimesFound++;
         }

         currNum = currNum+2;
      }
   }

   public static void main(String[] args) {
	  int numPrimes = 100000;
      long timeStart = System.currentTimeMillis();
      findPrimes(numPrimes);
      long timeEnd = System.currentTimeMillis();
      System.out.println("It took " + ((timeEnd - timeStart)/1000) +
            " seconds to find " + numPrimes + " prime numbers.");
   }
}

The 100,000th Prime Number Found: 1,299,709
It took 1 second to find 100,000 prime numbers.

Yeeeeaaaaa… that’s what I’m talking about. We went from 2 hours… to 1 seconds. Can we do better? At this point, why would we even care? Well, in cryptography, finding 100,000 is not a very impressive feat at all. We’re going to have to up our scale a little bit. So let’s start conducting tests to find 10,000,000 prime numbers (yes, ten MILLION), starting with the code we just tested:

The 10,000,000th Prime Number Found: 179,424,673
It took 665 seconds to find 10,000,000 prime numbers. (11 Minutes, 5 Seconds)

Although we’re only finding 100 times as many numbers, the time it took to find these numbers increased 665 times as much. Why? Because the run time is exponential. As the numbers get bigger, it gets tougher and tougher to figure out which ones are prime. In the next article of my series, I’ll explain some advanced techniques for finding prime numbers many times faster than we already are!! Hope you enjoyed part 1.

Welcome to my site.  Creating a website can be a rather tedious task, as the time investment required to do so is far too great during the school year.  But since I’m home for Christmas break and my job has no hours available when all the students are away from campus, I’m stuck here at home.. bored off my ass.  Thus, I’ve finally gone through the long process of creating a template, coding it, and then integrating it into WordPress.  I’m at least somewhat satisfied with it, although I’m sure I can do better.  So.. what exactly will be on this site?  Hopefully a pretty good balance between geeky technology related stuff and the fun things we find to do in college.. starting with my new favorite activity to do when you’re bored on winter break… Snowboarding!!

So this was my first time doing this, and I’ll admit that I would have been fully satisfied with just being able to keep my balance and slowly glide down a bunny hill for a good 15 feet.  I guess I got a little more than a bargained for in that respect.  I ended up cruising down the bunny hill like it was nothing.  I could build up tons and tons of speed.  I absolutely loved it.  Unfortunately, I couldn’t manage to figure out how to slow the damn thing down.. or stop for that matter.  So I ended up wiping out at the bottom each and every time.  I really took a bruising and quite frankly, I’m surprised I didn’t break anything.  So being the bright college kids that we are, we decide to leave the bunny hill without learning those skills and go down one of the normal “easy rated” hills.  Wow, what a mistake that was.  I couldn’t believe what I’d got myself into when I looked down from the ski lift.. hundreds of feet to the ice below.  The being able to slow down part ended up being a little more important than I ever could have anticipated, and not just for stopping either.  You know it’s not good when you’re cruising past experienced snowboarders and twice their speed,  only to go flying head over heels down the hill.  But what the hell – it was a ton of fun and no one got hurt.  I’d consider that a tremendous success.  On second thought, it probably didn’t have anything to do with being ‘bright college kids’ as much as it did being ‘guys’.  I guess we’ll find out after school starts because I already know of at least one girl who said she wants to go with us.  She said that she’ll even try to teach me how to stop.  We’ll see.. odds are I’ll still just end up crashing in order to stop.

So there’s about one week until I’ll be going back to campus.  Expect some geekier posts in the upcoming days here.. possibly some stuff dealing with programming in Java.  Fun stuff, right?  Oh.. and I’ll have NFL Championship preditions up before the game tomorrow.  I was just shy of 70% in NFL predictions this regular season, which is more than I can say for most of the ESPN, FOX, and CBS analysts.. and I won’t even start with how bad the NFL Network commentators are.  Aside from just predictions, I also won the consolation bracket in the 16 person fantasy football league we had going on campus.  I had a rough start to the season – I was in dead last for a while.  But after some big free agency moves, I nearly won out the rest of my games.  That’s not to mention that my first draft pick, Peyton Manning, did absolutely nothing the first half of the season.  Believe it or not, there was actually a point where I had to bench him for Kyle Orton.  It paid off too – he was a big surprise early in the season.  Unfortunately, my pitfalls in the beginning of the season cost me a place in the Winner’s Bracket – much to the relief of others, as I was really hot at the end of the season, averaging about 100 points a game.  But I’ll settle for being the loser’s bracket champ though.  So before I ramble any more, I’ll leave it at that.  Expect football predictions tonight!!