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 = { xe 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.

1. Prove or disprove: If A and B are square matrices of the same size, and AB = 0, then either A = 0 or B = 0.
2. 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 ℤ2. Some operations that can be performed on signed chars include:

Left shift

Given a signed char x, return a new signed char y, where y0 = 0, y1 = x0, y2 = x1, ..., y7 = x6. (This is written as y = x<<1.)

Right shift with sign extension

Given a signed char x, return a new signed char y, where y7 = x7, y6 = x7, y5 = x6, ..., y0 = x1. (This is written as y = x >> 1.)

XOR

Given two signed chars x and y, return a new signed char z, where zi = xi + yi (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 = x7x6x5x4x3x2x1x0. 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.

1. Suppose we represent x as a column vector. Show that there exist matrices L and R with entries in ℤ2 such that Lx = x << 1 and Rx = x >> 1.

2. 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 ℤ2, 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.)

2014-06-17 11:57