The galactic flag checker determines whether an input string is the correct flag in finite time!
Beginner Hint 1
- To solve this problem, it seems necessary to calculate the result of applying the
nextfunction tostate=521for(521**521)**521times. - However, performing this calculation simply would take far too long, so some ingenuity is required.
- Is there another way to calculate what the function is computing?
Beginner Hint 2
- Think of an n-bit integer as an n-dimensional vector over GF(2). (GF(2) = Z/2Z is the field consisting of {0, 1}.)
- The
nextfunction consists of a combination of bit shifts and XOR, forming a linear transformation from GF(2)^n to GF(2)^n. - This leads us to consider linear algebra over GF(2), and many properties that hold in linear algebra over the real numbers also hold over GF(2).
Beginner Hint 3
- The
nextfunction is a state transition function of a type of pseudorandom number generator called an LFSR. - For example, Xorshift32 is an LFSR with a 32-bit internal state.
- The period of a typical Xorshift32 is 2^32 - 1, and if you start from a state other than 0 and apply the state transition function, it will cycle through 2^32 - 1 states before returning to the initial state.
- What is the period of the
nextfunction?
Beginner Hint: About SageMath
- I recommend using SageMath to solve this problem.
- For a short introduction to SageMath, see this short guide.
- You can call the
nextfunction directly from SageMath by importingchal.py. - If you copy the code from
chal.py, keep in mind that the XOR operator in SageMath is^^, not^.