Editorial for Balkan OI '11 P2 - Decrypt
Submitting an official solution before solving the problem yourself is a bannable offence.
There are 2 phases:
- Determine
- Determine
Phase 1
Solving this problem starts by observing that has a period of (or iff ).
Also (xor) is a bitwise operation so the bits of each are independent. We are only interested in finding out a bit for now (let's assume least significant bit). The other bits are computed in a similar fashion.
Let , where are bits.
We start to play with the encryption device. What we ask is not that important, but we have to make sure that we don't ask the same number after uses, because we would just waste a query.
What we care about are collisions, i.e. queries that give the same answer.
Let be the queries we asked at times and , respectively.
Since and is a permutation we deduce that . This is the same as .
This pretty much gives an equation for finding out .
What we need is independent equations (independent collisions). We can continue to play with the device until we get them. Some attention is needed to make sure the equations are really independent.
Once we have independent collisions we can find out .
We can do the same for the rest of the bits: through . We just have to use a different bit from .
Phase 2
Now that we know , we can compute . It's important to remember the queries from step (1), otherwise the number of queries can easily exceed .
We know the step we are at () and the element of that we want to compute. Let be the index of the element. We query for . This gives us .
The total number of queries should be at least (for ) and (for collisions). However, many collisions are not independent. Since the tests are random, it's easy to find independent collisions in at most collisions.
Comments