xorshift521

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 next function to state=521 for (521**521)**521 times.
• 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 next function 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 next function 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 next function?

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 next function directly from SageMath by importing chal.py.
• If you copy the code from chal.py, keep in mind that the XOR operator in SageMath is ^^, not ^.