Hash Collision

문제

For security reasons, TU Delft is going to place locks with numeric keypads on the doors of a large number of rooms. Each room will have its own pass code. The task of setting up the server on which all codes will be stored is given to Harry and Sharon.

Having paid attention in cybersecurity class, they know that the codes should be passed through a hash function, preferably multiple times, before storing.

Sharon came up with the nifty idea of letting the room number be the number of times the code is passed through the hash function. That way, even if two rooms happen to have the same pass code, they will not (necessarily) end up with the same hash value. However, they find that for some combinations of room number and code, the hash value happens to be the same as the original code, presenting a security risk.

Not to be outdone by Sharon, Harry came up with an idea of his own: to switch the roles, that is, let the code be the number of times the hash function is applied to the room number. In other words, if $cc$ is the code and $rr$ is the room number, the hash value will be $f^c(r)=\underset{c\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{s}}{\underbrace{f(\cdots f(}}r)\cdots )f^c(r)\; =\; \backslash underbrace\{f(\backslash cdots\; f(\}\_\{c\; \backslash mathrm\{times\}\}r)\backslash cdots)$.

After some thought, Sharon claimed that, regardless of what the function $ff$ is, it would always still be the case for some room numbers and codes that the hash value is the same as the code; that is, that $f^c(r)=cf^c(r)\; =\; c$. In fact, Sharon thinks it would not be too difficult to find two such numbers, even without knowing the full details of $ff$.

This dismissive statement made Harry angry, who believed that Sharon was just jealous of his idea. After a big argument that led nowhere, Harry decided to make Sharon prove her claim: he has written a program that, upon sending it a query, will return the hash value $f^c(r)f^c(r)$ for the $cc$ and $rr$ given in the query, using a secret hash function $ff$ he has chosen. The hash function accepts any $rr$ in $\{1,\dots ,n\}\backslash \{1,\backslash dots,n\backslash \}$, where $nn$ is given, and returns a value in the same range. The value of $cc$ should also be in the same range. The challenge for Sharon is to find $cc$ and $rr$ such that $f^c(r)=cf^c(r)\; =\; c$, using a limited number of queries.

You know that Sharon is right about her claim and decide to help her.

In the first sample case, the value of $nn$ is 6, and the hidden function is given by $f(1)=4f(1)\; =\; 4$, $f(2)=3f(2)\; =\; 3$, $f(3)=5f(3)\; =\; 5$, $f(4)=2f(4)\; =\; 2$, $f(5)=4f(5)\; =\; 4$, and $f(6)=6f(6)\; =\; 6$. In the second sample, $n=4n\; =\; 4$, and $f(1)=2f(1)\; =\; 2$, $f(2)=4f(2)\; =\; 4$, $f(3)=2f(3)\; =\; 2$, and $f(4)=2f(4)\; =\; 2$.