銀河級のフラグチェッカーが入力した文字列が正しいフラグかどうかを有限時間で判定します！
初心者向けヒント①
- この問題を解くためには
state=521にnext関数を(521**521)**521回適用した結果を計算する必要がありそうです。 - しかし、単純に計算していてはあまりにも時間がかかるため、何らかの工夫が必要になります。
- 関数が計算している内容を他の方法で計算することはできないでしょうか？
初心者向けヒント②
- n ビットの整数を n 次元ベクトル GF(2)^n として考えます。(GF(2) = Z/2Z は {0, 1} からなる体です。)
next関数はビットシフトと XOR の組み合わせで構成されていて、GF(2)^n → GF(2)^n の線型変換になっています。- GF(2) 上の線型代数を考えることになりますが、実数上の線型代数で成り立っていた性質の多くは GF(2) 上の線型代数でも成り立ちます。
初心者向けヒント③
next関数は LFSR と呼ばれる種類の疑似乱数生成器の状態遷移関数になっています。- 例えば Xorshift32 は内部状態が 32 ビットの LFSR です。
- 代表的なパラメータの Xorshift32 の周期は 2^32 - 1 で、0 以外の状態からスタートして状態遷移関数を適用していくと 2^32 - 1 通りの状態を巡回して最初の状態に戻ります。
next関数の周期はどうなっているでしょうか？
初心者向けヒント: SageMath について
- この問題は SageMath を使って解くことをおすすめします。
- SageMath については 簡単な紹介文 があります。必要に応じて参照してください。
chal.pyを import することでそのまま SageMath からnext関数を呼び出すことができます。- コードをコピーして使用する場合は SageMath では XOR 演算子は
^ではなく^^であることに注意してください。