Panoramas from Ljubljana and Dubrovnik

Dubrovnik Coast (4 images stitched in Hugin):

Ljubljana, on the river (6 images stitched in Hugin):

Public/Private Key Math

Heavily sourced from: Cryptography and Network Security, Fourth Edition by William Stallings.

Key Generation

Pick two prime numbers: p and q

p = 7
q = 13

Compute n=p.q

n=p.q
n=7 x 13
n=91

Compute the Euler Totient of n: Φ(n) = (p-1)(q-1)

Φ(n) = (7-1)(13-1)
Φ(n) = 6 x 12
Φ(n) = 72

Pick an integer e, such that the greatest common denominator between Φ(n) and e is 1, and e is greater than 1 but less than Φ(n)

gcd(Φ(n),e)=1 and e>1 and e<Φ(n) gcd(72,e)=1  Choosing e: 5 

Determine the value of d using the formula:

de mod Φ(n) = 1
dx5 mod 72 = 1

Possible values for dx5 need to be 72*(some integer) + 1:
73 (won't work)
145 (that will work)
145/5 = 29

Plugging into:
dx5 mod 72 = 1
29x5 mod 72 = 1

d = 29

With d, e, and n computed, we have our keys:

Public Key:  KU = {e, n} = {5, 91}
Private Key: KR = {d, n} = {29, 91}

Encryption and Decryption

Now, we're ready to encrypt. Assuming plaintext M, we compute ciphertext using the formula: C=(M^e)mod(n)

Assuming plaintext M=10
C = (M^e) mod(n)
C = (10^5) mod(91)
C = 82

Compute 10^5 mod 91 via wolframalpha.

Decryption uses the formula: M=(C^d)mod(n)

C = 82 (from above)
M = (C^29)mod(91)
M = (82^29)mod(91)
M = 10 (that worked!)

Compute 82^29 mod 91 via wolframalpha

What's remarkable is how monstrous the math gets using relatively tiny prime numbers to start with. We started with 7, and 13 to create our keys, and our final computation (the decryption) required us to compute 82^29, which is:

31666620625027474232451213268613396669946986162166956032

Our keys, were of a really trivial bit-length {5,91}, and {29,91}. Consider that most asymmetric algorithms talk about keys that are of lengths greater than 1000 bits. Now consider what the size of the exponents may look like, and the corresponding products which need to be modulo divided.

Dilbert meets Hobbes

Today (sadly), I was forced to use a laptop running Windows.

• I connected a mouse to it (using a USB port)


• The hardware drivers kicked in and the mouse started to work


• I used the mouse to move, and click on a window


• Windows informed me that a mouse had been detected and installed (after I used the aforementioned mouse to move and click on something)


• This informative dialog stole the focus from the application I was using, after I used the mouse it so eagerly wanted to let me know it had found


• I have dogs that are better behaved, and far, far more intelligent

Sigh. Pull my teeth out with rusted pliers and pour some salt on whatever is left. If you love eating shit, then..

Constant Time Add Operations

I had to write a paper recently, and I opted to analyze the seemingly trivial constant time add operations on two different Java list implementations. Guaranteed to bore you to death: List Add Operations.

Updated (18 June 2009) link above should work.

insert performance variance

Disclaimer: I've done some research here based purely on measurement and assumed use cases. The performance discrepancies shown are on very large data volumes (1 million elements), so the findings may or may not be applicable.

Here's the premise under which I started searching for measurement:

• I see Sorted collections, specifically TreeSet objects being used rampantly to maintain an ordered set of data


• Typically, the ordering is comparison based (driven by the object implementing Comparable)
  
• Often, the contents of the collection, once populated, are not tampered with


• A frequent use of the contents of the collection is to iterate over it in sequence

Considering the above, it seems like we (I know I've done this) generally feel comfortable incurring some cost upon adding elements to a collection in order to be able to recover them in sorted fashion quickly. The specific cost of insert time is log(n) where n is the number of elements already in the Set. For a clean explanation about why the cost is log(n), read about Binary Search Trees.

Here's what my dilemma is though: add operations on lists cost very little (a constant for all practical purposes). And sorting on a list that can manage a swap operation quickly is likely to be very fast too. A simple QuickSort should theoretically be able to accomplish n(log(n)) performance if the data is reasonably well distributed.

So the question that I wanted to tackle was: For large enough data sets, would it be quicker to get a sorted collection by adding data to a simple list and then sorting it, or would it be quicker to work with a data structure that sorts with each insert? I decided to play with the ArrayList and TreeSet to dig into this.

Here's the ArrayList code:

        ArrayList<Long> arrayList = new ArrayList<Long>();
        Random r = new Random(1l);
        long start = System.currentTimeMillis();
        for (int x = 0; x < 1000000; x++) {
            long l = r.nextLong();
            arrayList.add(l);
            if (arrayList.size() % 10000 == 0) {
                long now = System.currentTimeMillis();
                System.out.println(now - start);
            }
        }

Here's the TreeSet:

        TreeSet<Long> treeSet = new TreeSet<Long>();
        Random r = new Random(1l);
        long start = System.currentTimeMillis();
        for (int x=0; x<1000000; x++) {
            long l = r.nextLong();
            treeSet.add(l);
            if (treeSet.size() %10000 == 0) {
                long now = System.currentTimeMillis();
                System.out.println(now - start);
            }
        }

Here's a graph of the performance:

Not surprisingly, the ArrayList is way quicker. Looking at the cumulative cost though, you get a better picture of the total time it takes to add a lot of data to a sorted vs unsorted collection:

Again, not terribly suprising. But, now let's try and equalize the game a bit. Let's transcribe the QuickSort Algorithm to code, and then run it on the ArrayList after we've added everything to it. Here's the QuickSort:

    private void sort(List<Long> arr, int start, int end, int d) {
        if (start < end) {
            int pivot = start;
            int newPivot = partition(arr, pivot, start, end);
            sort(arr, start, newPivot - 1, ++d);
            sort(arr, newPivot + 1, end, ++d);
        }
    }


    private int partition(List<Long> arr, int pivot, int start, int end) {
        long pivotValue = arr.get(pivot);
        swap(arr, pivot, end);
        int newPivot = start;
        for (int x = start; x < end; x++) {
            if (arr.get(x) <= pivotValue) {
                swap(arr, x, newPivot);
                newPivot++;
            }
        }
        swap(arr, newPivot, end);
        return newPivot;
    }

    /**

     * Helper to manage a 3-op swap
     */

    private void swap(List<Long> arr, int from, int to) {
        long tmp = arr.get(from);
        arr.set(from, arr.get(to));
        arr.set(to, tmp);
    }

    public void sort(List<Long> arr) {
        sort(arr, 0, arr.size() -1, 0);
    }

And, tweaking the ArrayList insert code to leverage the sort:

        ArrayList<Long> arrayList = new ArrayList<Long>();
        Random r = new Random(1l);
        QuickSort qs = new QuickSort();
        long start = System.currentTimeMillis();
        for (int x = 0; x < 1000000; x++) {
            long l = r.nextLong();
            arrayList.add(l);
            if (arrayList.size() % 10000 == 0) {
                long now = System.currentTimeMillis();
                System.out.println(now - start);
            }
        }
        qs.sort(arrayList);
        long now = System.currentTimeMillis();
        System.out.println(now - start);

Our performance numbers are:

Even with the separate sort, costing n(log(n)), the ArrayList won handsomely (a factor of approx 20%). Granted, the quicksort wasn't very general, but this does seem to raise a few questions. Perhaps for large volumes, this is a viable strategy?

Mailboxes and Dogs

From a few weeks back:

It appears that someone decided to drive over our mailbox. I'm not sure what the state of their vehicle is currently, but it can't be great. Bruce (our neighbor) has set about building a brand new mailbox (post included), and from what I can tell, there's no wood involved- just loads of metal.

Party on..

A few weeks back, when the weather was better, we had our neighbors over for brunch. Dogs are always welcome.

Mowgli

Read this news article first: Omaha Woman Rescues Dogs from Streets of Mumbai

Mowgli is one of the four puppies from the trash bag, and he now lives with us:

Radiohead rules

Like many other people, I saw that Radiohead had created an interesting music video for House of Cards with all sorts of visualizations. From what I read, they had sampled visual data using Lidar. Substantial portions of the data used in constructing the video are available (as is the music) to the general public. The House of Cards group on YouTube showcases how a number of people have re-run the data through various visual engines.

As you may notice, most of the videos on YouTube use some form of 3D engine to visualize the data. The data is structured fairly simply in the CSV files with x, y, and z coordinates, as well as an intensity level for each point.

Problem: I'm not adept (at all) with anything 3D based. So, I decided to see if I could kludge my way into trying to create a visualization of my own using what I know. Er.. All I know is Java and Graphics2D.

For rendering data, I just used a simple linear scale to position the x and y points. Each point was merely a filled circle. I plotted all points in white. The intensity value on each point drove the alpha values on each point. Lastly, I used the z value to control the size of the point- closer z values got larger points. Here's what I got for starters:

Some tuning in point size, and changes in colors to prevent it from looking too scary:

Anyone know an easy way to sequence some 1000 images into a decent video? I can't seem to get iMovie to have a delay between images of less than .3s, and the actual frames need to be rendered out at 30 frames per second.

*Follow up:* Meant the attach a larger copy that shows the patterns generated by the circle size and alpha variations:

Broader thinking

Steph decided to take a horizontal sequence of pictures on her camera when we were up in the Rocky Mountain National Park. The goal was to stitch the images into a panorama. The last time I did this, was back in 2001, gluing together the Manhattan skyline (World Trade Center buildings included). That was done mostly with gimp, if I recall right.

Meet Hugin- a gem of a tool that does all the hard work needed to assemble a panoramic blend of pictures. The image below, cobbled from some 7 shots took around 3 minutes. Just be sure to preserve your Exif information as you get your pictures together since Hugin can use them to drive a massive amount of automation.

Hugin is an open source application, and it leverages the libpano suite. The value it provides is really outstanding. Moreover, the community behind Hugin seems to be adding value in raw photographic know-how on their blog: panospace. Kudos to a great app, and the community that powers it.

Need bicycle porn?

Or a house? Look no further.

Lightning and a Moth

Some of the storms in early June had such a high density of lightning strikes that it turned out to be easy enough to catch a couple of strikes. My location left a lot to be desired, and I kind lacked the courage (or funds) to subject myself and the camera to the worst of the storm. Here's what I got:

Towards the latter part of June, Steph saw this moth and took some photos of it. Note the fur all over it, and the fern like antennae. Does anyone know kind of moth it is?

Java 6 on OS X

This almost sneaked past me.. The most recent update humbly drops in Java SE 6:

It doesn't seem to replace Java 1.5 right away. You've got to fire up the Java Preferences app and fiddle with a few switches.

And then, presto:

And in case you need to add the new VM to some app (like Eclipse), the goldmine is at: /System/Library/Frameworks/JavaVM.framework/Versions.

graphviz > MS Project

Guerrilla Project Management in action (from Mr Blaine). See Guerrilla Marketing for context.

Pulling data out of the air

About a month ago, I bought a real small weather station from AAG Electronica. The unit I got has three sensors: temperature, wind speed and wind direction. Data is transmitted from the station using the 1-Wire protocol. The transport that this runs on is merely a phone line, within which only two of the wires are put to use.

The first major challenge was finding a good place to install the station. I wasn't keen on running reams of phone line around the countryside, so I compromised on location. It turned out that the tripod on which the (absolutely detestable farce of a connectivity solution) DirecWay dish was installed would work nicely. (Also, considering that we'd long since stopped using the hideous service, it seemed like the dish installation might be able to redeem itself in some mechanical way). Perhaps most nifty: the dish accidentally manages to serve as a direct sun shield, preventing the unit from getting cooked.

With the station installed, I had to start collecting data. The One-Wire Weather project proved quite easy. In addition to a gtk UI that's useful to detect and configure a setup file, there's a no-gui program that can be configured to scrape readings from the station. Wrap that in a bit of perl, add a database, write code code with JFreeChart and presto:

For for now, I get up to the 5-minute interval readings of temperature posted on recursed.org.

sizzle

Back when I was thinner, and had a sense of humor. Perhaps more peculiar than normal.

Slow SSH Login

The SSH daemon appears to execute a reverse lookup on inbound IPs to map them to a DNS address. My symptoms were authentication attempts that took a long time to return a password prompt, but thereafter performed as normal.

It seems like the key is to get the server to "know" the host attempting to authenticate, and so tweaking with /etc/hosts is pretty much a quick way to fix the issue.

ssh user@server
... takes forever to get password challenge

Within the /etc/hosts on server, add:

#IP.Of.Connecting.Client hostNameOfConnectingComputer
192.168.1.100 kitchenLaptop

That seems to have fixed things. The password challenges flash up immediately. Of course, it might be prudent to set up an internal DNS so each machine doesn't have to have a cobbled host file.

Online

We got broadband to our house today.

Our local technician, Kerry, is the hero of the neighborhood. Without his involvement in the process, I doubt we would have got this connectivity. He's my hero.

That said, I've got my Dynamic DNS back on line. If you do need one, try zonedit. It is free, and the site instills confidence with its lack of sexy, and focus on the job. Another plus, it works with ddclient. My real simple /etc/ddclient.conf:

syslog=yes
pid=/var/run/ddclient.pid
ssl=yes # use ssl

use=web, web=checkip.dyndns.org/, web-skip='IP Address: ' 

server=www.zoneedit.com, \
protocol=zoneedit1, \
login=username, \
password=password \
comma-separated-list-of-domains

If you're running a Debian flavor, the sleep time and such is at /etc/default/ddclient, which seems to override any sleep times set in the ddclient.conf file.

Waiting

A few days ago, we got a note from our power company indicating that they were going to upgrade the metering equipment that they use to estimate and bill us on consumption for. The new equipment will be wireless- a passing by truck will be able to scan readings without having the driver exit, or even stop the vehicle. This probably saves the power company a lot of money- the time expended in measuring how much power I'm consuming drops down dramatically, leading to a higher productivity level for this job through automation. There's probably a savings in energy expended since the vehicles moving people to these metering locations will be using a lot less gas- no more start/rev up/stop/start/rev up/stop, but probably a leisurely drive through the neighborhood. Multiply that by thousands of starts and stops and vehicles, and you've got a lot coin in the bank.

If my house, and everyone else's house had an assumed internet connection, the power company might approach this problem differently. Say that everyone's house had some sort of assumed internet connectivity (like a 110 Volt three-prong outlet, or some wireless capacity). In that case, the power company would probably have left me a note indicating that the new metering equipment would serve their data on demand, or maybe periodically, or maybe even constantly, via a secure connection to the internet.

This letter, and others like it cry out for moving us into an age where reasonable connectivity is deemed an infrastructural necessity. This might seem like a reach, but in a world where data points tend to be of immense value, surely an assumed infrastructure for moving data is of value too?

Urban areas seem to be benefiting from the prevalence of broadband infrastructure. Still, there aren't too many manufacturers that can assume that a data connection exists as simply as say a socket to a bulb. Most of the products that make this assumption are purely internet related. Still, some newer ones are setting precedent (Blu-Ray devices, Digital Photo Frames, and the like). Not too many that resemble a power consumption meter though. Do you know of any that break the mold?

Perhaps the advent of these sorts of devices will spur the adoption of an assumed connected infrastructure. Perhaps the assumed infrastructure will spur the growth of those devices? Maybe seeing them crop up in urban areas will show people what sort of innovation lies in store for us if we can let manufacturers assume an internet connection as easily as they assume a power plug.

Meanwhile, I wait for my ISP to figure out when it would like to provide me with broadband access. The strange reality is that I'm only 20 miles away from my ISPs headquarters.

Ford GT

At the McMullen Ford Dealership in Council Bluffs, I happened to see this machine. No one near it, no one drooling over it, just the car, right there.

The Ford GT

The good shepherd

That's Leela (again). This is the sight that anyone opening the garage door would be greeted with. It also happens to be the first thing the cats see in the morning.