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: