University of Virginia, Department of Computer Science
CS588: Cryptography, Spring 2005

Notes: Tuesday 1 February 2005
Assignments Due


How many women should we expect the Iraqi national assembly to have?

(define number-of-parties 111)
(define number-of-assembly-members 275)

(define (max a b) (if (> a b) a b))
(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))
(define (choose n k)  
   (/ (factorial n) (* (factorial k) (factorial (- n k)))))
(define (binomial-probability n k p)  
   (* (choose n k) (expt p k) (expt (- 1 p) (- n k))))

(define (expected-parties seats)
  (exact->inexact (* number-of-parties 
                     (binomial-probability number-of-assembly-members
  seats (/ 1 number-of-parties)))))

(define (expected-party-count n)
  (if (< n 0) 0
      (+ (expected-parties n) (expected-party-count (- n 1)))))

(define (expected-women n)
  (if (< n 0) 0
      (+ (* (floor (/ n 3)) (expected-parties n))
         (expected-women (- n 1)))))

Enigma Schematic

How big is the keyspace for the Enigma machine?

What is an involution?

Why must the reflector be an involution?

Rejewski's Theorem: The composition of two permutations that are involutions consists of pairs of cycles of the same length.


Propose to an Englishman any principle, or any instrument, however admirable, and you will observe that the whole effort of the English mind is directed to find a difficulty, a defect, or an impossiblity in it. If you speak to him of a machine for peeling a potato, he will pronounce it impossible: if you peel a potato with it before his eyes, he will declare it useless, because it will not slice a pineapple.

Charles Babbage, breaker of Vigenere cipher, after losing funding for his Difference Engine project, 1823.

CS 655 University of Virginia
Department of Computer Science
CS 588: Cryptology - Principles and Applications