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 symmetrickey ciphers known as block ciphers. A block cipher encrypts binary data in (relatively large) fixedlength 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:

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

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

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

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$.^{1} Note that all values are restricted to $\{ 0,1\} $, so any intermediate integer produced during vectormatrix multiplication (or matrixmatrix multiplication) must be reduced $(\mathrm{mod}~ 2)$. For example,
\[ (1 \, \ 0 \, \ 1 \, \ 1) \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix} \ = \ (1 \, \ 1\, \ 0\, \ 1) \]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).
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.^{2}
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.
Sample Input 1  Sample Output 1 

1 
3 
Sample Input 2  Sample Output 2 

2 
6 
Footnotes
 Anyone familiar with symmetrickey cryptography knows that using matrix multiplication for $f$ is a really bad idea, but our goal here is the creation of an interesting programming competition problem, not a cryptographically strong cipher. Such a person will also notice that we are completely ignoring keys.
 As an assurance that we are not dealing with nonexistent mathematical objects, note that it is not hard to prove that whenever $n \geq m$, there exist $n \times n$ binary matrices of order $m$.