Problem D
Feistel Fun

A Feistel network, named after IBM researcher Horst Feistel (1915–1990), is an important structure often used in the design of symmetric-key ciphers known as block ciphers. A block cipher encrypts binary data in (relatively large) fixed-length chunks called blocks. For a block cipher based on the Feistel network structure, the block size must be even, i.e., equal to $2n$, where $n$ is a positive integer.

As is the case for many block ciphers, a Feistel network block cipher encrypts its input block (the plaintext) to produce an output block (the ciphertext) by repeatedly applying a simpler encryption step called a round. (The number of round iterations is chosen by the cipher designer(s) to balance various criteria such as security and speed.) A single round takes in a block and outputs a block, i.e., it maps $\{ 0,1\} ^{2n}$ to $\{ 0,1\} ^{2n}$, where $\{ 0,1\} ^ b$ denotes the set of all $b$-bit vectors. Internally, a round makes use of a round function, $f$, that maps $\{ 0,1\} ^{n}$ to $\{ 0,1\} ^{n}$, i.e., $f$ operates on half blocks. Here is what happens in a single round:

1. $f$ is applied to the right half of the input block

2. the resulting output of $f$ is combined with the left half of the input block via bitwise XOR ($\oplus $)

3. the right half of the output block is the the $n$-bit vector produced by this XOR operation

4. the left half of the output block is a copy of the right half of the input block

Symbolically, if the $2n$-bit round input is denoted $(x,y)$, where $x$ is the left half and $y$ is the right half, then the round output is $(y, x \oplus f(y))$.

The properties of a Feistel network block cipher depend critically on the choice of the round function, $f$, for which there are many options, but we will make a simplifying assumption: the round function is just multiplication of its $n$-bit input with a fixed $n \times n$ binary matrix, $M$.¹ Note that all values are restricted to $\{ 0,1\} $, so any intermediate integer produced during vector-matrix multiplication (or matrix-matrix multiplication) must be reduced $(\mathrm{mod}~ 2)$. For example,

The order of an $n \times n$ matrix $M$ is the smallest positive integer $m$ such that $M^ m = I_ n$, where $I_ n$ is the $n \times n$ identity matrix, and $M^ m$ denotes $M$ multiplied by itself $m$ times.

All of this leads to a very interesting question. Given the order $m \geq 1$ of the matrix $M$ used in the round function, will the cipher become the identity mapping after a finite number of rounds, and, if so, what is the minimum number of rounds required to make this happen? A cipher is the identity mapping if every plaintext encrypts to itself. For example, if $m=2$, Figure $1$ shows that the Feistel network cipher we have described becomes the identity mapping after $6$ rounds (since the plaintext, $(x,y)$, is always equal to the ciphertext).

Figure 1: When $m=2$, the cipher becomes the identity mapping after $6$ rounds

Input

The input consists of a single positive integer, $m$ $(m \leq 40)$, the order of the matrix $M$ used in the round function of the Feistel network block cipher described above.²

Output

Output a single positive integer, the minimum number of rounds required for the cipher to become the identity mapping. For the values of $m$ under consideration, this is guaranteed to happen after a finite number of rounds.

1

3

2

6