MATH 195: CRYPTOGRAPHY HOMEWORK #4

Problem 3.4’. Let N ≥ 3. Prove that the probability

\frac{#\{σ ∈ Sym N : ∃k ∈ \{1, 2, …, N\} : σ(k) = k\}}{N!}

is ≥ 5/8 and is ≤ 2/3.

Problem 2.13. Find constants c_{1} and c_{2} such that the usual algorithm (shown in class) for finding the inverse of any A ∈ GL(k, F) over any field F takes no more than c_{1}k^{c_{2}} arithmetic operations (+, −, ·,^{−1}) in F; how many of these are inversions?

Problem 3.14 (Feistel ciphers). Let k ≥ 2, A = (ℤ/2ℤ)^{k}, and define the maps

s, g : A × A → A × A
s(x, y) = (y, x)

g(x, y) = \begin{cases}(x, y), & y ≠ (0, 0, …, 0); \\ (x + \underbrace{(1, 1, ..., 1)}_{k}, (0, 0, …, 0)), & y = (0, 0, …, 0). \end{cases}

Prove: s^{2} and g^{2} are the identity on A × A, (sg)^{4} = sgsgsgsg moves only 3 elements of A × A (i.e. (sg)^{4}((x, y)) ≠ (x, y) for only 3 elements (x, y) ∈ A × A), and (sg)^{12} is the identity.

Date: February 19, 2002.

3.4’, 2.13, 3.14.