[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.


1. A secret code

The IT manager at the First Bank of Insecurity wants to use customer birthdays to verify people calling its customer service desk, where we take a customer birthday as consisting of a month m in the range (1..12) and a day d in the range (1..31). But upper management insists that the bank can't violate its customers' privacy by storing the actual dates. So the IT manager suggests storing instead a pair (x,y) where


For example, if a customer's birthday is (7,1), the encoded value would be (3,5). When a customer calls up, a highly trained customer service representative can compute this encoding based on the customer's actual birthday and compare it with the bank's records. But in the other direction (the IT manager reasons), it would take an expensive brute-force search of all 366 possible birthdays to figure out what the actual birthday was given just x and y.

Show that this system does not in fact provide much security, by giving a simple formula for computing m and d given x and y. (Since you are working mod 31, it's OK if your formula returns 0 for d when the actual value is 31.)

2. A strange equivalence

Given x and y in ℕ, let x ≡ y if there exist k and l in ℕ such that 2kx = 2ly.

  1. Show that ≡ is an equivalence relation.
  2. Prove or disprove: If x ≡ x' and y ≡ y', then xy ≡ x'y'.
  3. Prove or disprove: If x ≡ x' and y ≡ y', then x+y ≡ x'+y'.

3. Factorials

The factorial of n, written n!, is equal to the product of the natural numbers from 1 to n. Formally, n! = $\prod_{i=1}^{n} i$.

  1. Prove that n! + k is composite for any 1 < k ≤ n.

  2. Give a counterexample that shows that n! + k might not be composite if k = 1, even if k < n.

2014-06-17 11:57