[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.)

1.1. Solution

Basically, we are solving two equations in two unknowns, and the only twist is that we are doing it in ℤ31 instead of ℚ.

Let's start by using the first equation to get an expression for d in terms of m and x:

Plugging this into the second equation gives:

This would be easier to solve if we knew what 25-1 was in ℤ31.

Using the extended Euclidean algorithm, we want to find n1 and m1 such that 31n1 + 25m1 = 1.

Write 31 = 1⋅25 + 6 to reduce to the problem of finding n2 and m2 such that 25n2 + 6m2 = 1. Here since 25 = 4⋅6 + 1, we easily get 25⋅1 + 6⋅(-4) = 1, giving n2 = 1 and m2 = -4.

Working backwards, we have 6 = (31-25) so 1 = 25 - 4⋅6 = 25 - 4⋅(31-25) = 5⋅25 - 4⋅31. So 25-1 = 5 (mod 31).

Note: If we don't want to go through the extended Euclidean algorithm, there are other alternatives: one is to just guess the correct answer (possibly by trying out cases until we find one that works, or by Googling "inverse of 25 mod 31"), and verify that it is correct by multiplying 5⋅25 = 125 = 31⋅4 + 1. This is perfectly acceptable in a proof, although it may not work if the modulus is much larger. Another is to use Euler's theorem and calculate 25-1 = 2530-1 = 2529 = 34694469519536141888238489627838134765625 = 5 (mod 31). This requires either having a calculator that can handle really big numbers, or using something like the Russian Peasant's Algorithm to calculate the exponent mod 31 a piece at a time. Either approach is likely to be more computationally expensive than the extended Euclidean algorithm, and in general we won't expect the Euler's theorem approach to work when m is a large composite number, since we can't compute the totient of m (and thus figure out what exponent we need) unless we can factor m.

However we found 25-1, we can now put it back in our y formula:

Rearrange to put m by itself:

Knock down the 371 by taking it mod 31:

Now we need to know what 30-1 is in ℤ31. The easy way to do this is to notice that 30 = -1, so 30-1 = (-1)-1 = -1. Multiplying both sides by -1 then gives

Since 11 = -20 (mod 31), we can make this a little cleaner by rewriting it as

Our formula for d (with 25-1 replaced by 5) says

Summarizing, we have

m = 11x + y

d = 14x - 2y

(with everything taken mod 31). As a quick check, if we use our example of x = 3, y = 5, we get m = 33+5 = 38 = 7 (mod 31) and d = 42-10 = 32 = 1 (mod 31), which is what we started with.

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'.

2.1. Solution

  1. Reflexive: let 2k = 2l = 20 = 1; then 2kx = x = 2lx. Symmetric: If 2kx = 2ly, then 2ly = 2kx. Transitive: Let 2kx = 2ly and 2my = 2nz. Suppose that m ≥ l. Then 2k+m-lx = 2my = 2nz. Alternatively, if m < l, then 2n+l-mz = 2m+l-my = 2ly = 2kx. (Extra sneaky transitivity proof: 2k+mx = 2m2kx = 2m2ly = 2l2my = 2l2nz = 2l+nz. This avoids the case analysis.)

  2. Proof: Let 2kx = 2k'x' and 2ly = 2l'y'. Then 2k+k'x = 2l+l'y'.

  3. Disproof: 1 ≡ 2, and 1 ≡ 4, but it is not the case that 2 ≡ 6.

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.

3.1. Solution

  1. If k ≤ n, then k is a factor of n! (since it's included in the big product). So we have k|n! and k|k, implying k|(n!+k). Now observe that (a) k ≠ 1; (b) since n ≥ k > 1, n! ≥ 2! = 2, implying n! + k ≥ k+2 and in particular n! + k ≠ k. Thus n! + k has a factor that is neither equal to itself or 1, so it's composite.

  2. The smallest possibly counterexample works: 2! + 1 = 3 is prime. The next counterexample is 3! + 1 = 7. After that the counterexamples start getting pretty thin. The next smallest one is 11! + 1 = 39916801, which happens to be prime, but not obviously so.

2014-06-17 11:57