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.

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 ℤ₂. 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.

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

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