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 destructive RSA key

Let p and q be distinct primes, and let e = 2(p-1)(q-1). Show that the set A = { x^e mod pq | x ∈ ℕ } has exactly four elements.

2. Zero matrices

Recall that a zero matrix, usually just written as 0, is a matrix all of whose entries are zero.

Prove or disprove: If A and B are square matrices of the same size, and AB = 0, then either A = 0 or B = 0.
Prove or disprove: If A and B are square invertible matrices of the same size, then AB ≠ 0.

3. Xorshift formulas

On a typical machine, a signed char value in C consists of 8 bits, which we can imagine as the entries of an 8-dimensional vector x over ℤ₂. Some operations that can be performed on signed chars include:

Left shift: Given a signed char x, return a new signed char y, where y₀ = 0, y₁ = x₀, y₂ = x₁, ..., y₇ = x₆. (This is written as y = x<<1.)
Right shift with sign extension: Given a signed char x, return a new signed char y, where y₇ = x₇, y₆ = x₇, y₅ = x₆, ..., y₀ = x₁. (This is written as y = x >> 1.)
XOR: Given two signed chars x and y, return a new signed char z, where z_i = x_i + y_i (mod 2). (This is written as z = x^y.)

Note: By convention, the bits in a character are numbered from 7 (most significant) to 0 (least significant), e.g. x = x₇x₆x₅x₄x₃x₂x₁x₀. This is backwards from the way we usually write vectors, and also ends at 0. For the purposes of this problem, let us meet this convention half-way: imagine that vectors and matrices are written in the usual order (indices go left-to-right and top-to-bottom), but that we start counting at 0.

Suppose we represent x as a column vector. Show that there exist matrices L and R with entries in ℤ₂ such that Lx = x << 1 and Rx = x >> 1.
Consider the following rules for building xorshift formulas in some variable x:
- x is a formula.
- If f is a formula, so is (f<<1) and (f>>1).
- If f and g are formulas, so is (f^g).
Show that for any formula f in this class, there exists a matrix A over ℤ₂, such that the result of evaluating f for a given x is the same as the result of computing Ax. (Hint: Use induction on the length of f.)