# 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 ℤ_{2}. Some operations that can be performed on `signed char`s include:

- Left shift
Given a

`signed char`x, return a new`signed char`y, where y_{0}= 0, y_{1}= x_{0}, y_{2}= x_{1}, ..., y_{7}= x_{6}. (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_{7}= x_{7}, y_{6}= x_{7}, y_{5}= x_{6}, ..., y_{0}= x_{1}. (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_{7}x_{6}x_{5}x_{4}x_{3}x_{2}x_{1}x_{0}. 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 ℤ

_{2}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 ℤ

_{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.)