防衛省サイバーコンテスト2023 Programming LFSR Period

はじめに

Write Up で Wikipedia へのリンクが示されているけれど、これを読んでわかるほどのレベルにないので理論の理解は置いておいてプログラムを読みとく。

参考URL :: https://ja.wikipedia.org/wiki/%E7%B7%9A%E5%BD%A2%E5%B8%B0%E9%82%84%E3%82%B7%E3%83%95%E3%83%88%E3%83%AC%E3%82%B8%E3%82%B9%E3%82%BF

今回の問題は 20 bit で、一般的にプログラミング言語で扱える符号なし整数は 8 bit, 16 bit, 32 bit, 64 bit
なので、その点も考慮する必要があると思うが、いったん棚上げ

また理論上の多項式 $$ x^{16} + x^{14} + x^{13} + x^{11} + 1 $$ の意味するところはわかっていない。

出てくる論理演算子

演算子	意味
&	AND
^	XOR
>>	右シフト
<<	左シフト

図を読む

• ビット位置を差す添字が左から1ではじまるので、符号なし整数は右から0ビット目と考えるので変換する必要がある

C/C++ のプログラムを読む

bit = (reg & 0x0001) ^
      ((reg & 0x0004) >> 2) ^
      ((reg & 0x0008) >> 3) ^
      ((reg & 0x0020) >> 5);
reg = (reg >> 1) | (bit << 15);

0x は16進数(Hex)表記なので 0x0001 は 16bit で2進数表記ば以下のように
なる。

0x0001 = 0000 0000 0000 0001

同様に

0x0004 = 0000 0000 0000 0100
0x0008 = 0000 0000 0000 1000
0x0020 = 0000 0000 0010 0000

となるので 0x0001 は図の 16bit目、0x004 は 14bit目、0x0008 は13bit目、0x0020 は11bit目を表している。

そして >> は右シフト演算子なので、それぞれを符号なし整数の1bit目に移動させる処理を行なっている。つまり

0x0004 >> 2 = 0000 0000 0000 0100 >> 2 = 0000 0000 0000 0001
0x0008 >> 3 = 0000 0000 0000 1000 >> 3 = 0000 0000 0000 0001
0x0020 >> 5 = 0000 0000 0010 0000 >> 5 = 0000 0000 0000 0001

別の見方をすれば 16bit 長のレジスタで図の位置のフィルターを作るには
0x0001 << (ビット長 - ビット位置)とすれば良いことがわかる

0x0001 << (16 - 16) = 0x0001 << 0 = 0000 0000 0000 0001 << 0 = 0000 0000 0000 0001
0x0001 << (16 - 14) = 0x0001 << 2 = 0000 0000 0000 0001 << 2 = 0000 0000 0000 0100
0x0001 << (16 - 13) = 0x0001 << 3 = 0000 0000 0000 0001 << 3 = 0000 0000 0000 1000
0x0001 << (16 - 11) = 0x0001 << 5 = 0000 0000 0000 0001 << 5 = 0000 0000 0010 0000

したがって ((reg & 0xXXXX) >> n は現在のレジスタのNビット目を抽出している。そして抽出したNビット目の XOR(^) を取り bit に代入している。(図中左端の0)

次に下記代入式は現在のレジスタの値を 1 bit 右シフト、算出した bit を 16 bit 目にセットしている。
具体的には bit の値(0 or 1)を 15 bit 左にシフト、つまり 16 bit 目に移して論理ANDを取っている。

reg = (reg >> 1) | (bit << 15);

したがって初期値 0xACE1 = 1010110011100001 を 1bit 右シフト結果 '0'101011001110000 の 16 bit目に bit の値、ここでは 0 をセットしている。

防衛省サイバーコンテストの問題の Write Up を読む

これで https://blog.hamayanhamayan.com/entry/2023/08/06/220606 のコードが理解できる。

問題は下記多項式について、レジスタ長が 20 bit である場合について周期を求める問題

x^{20} + x^{15} + x^{11} + 1

まず各ビット位置のフィルターを準備

0x1 << (20 - 20) = 0x1 << 0
0x1 << (20 - 15) = 0x1 << 5
0x1 << (20 - 11) = 0x1 << 9

フィルターで各ビット位置の値を抽出して XOR を取る

bit = ((reg & x11) >> 9) ^ ((reg & x15) >> 5) ^ ((reg & x20) >> 0);

現在のレジスタの値を 1 bit 右にシフトして 20 bit 目に算出結果をセット

reg = (reg >> 1) | (bit << 19);

これを初期値がもう一度あらわれるまで繰り返してその繰り返し回数を求める。

Rust でリライト

fn main() {
    let start_state: u32 = 0x70109;
    let x20: u32 = 0x1 << 0;
    let x15: u32 = 0x1 << 5;
    let x11: u32 = 0x1 << 9;

    let mut reg: u32 = start_state;
    let mut bit: u32 = 0;
    let mut period = 0;
    let mut found = false;

    while !found {
        bit = ((reg & x11) >> 9) ^ ((reg & x15) >> 5) ^ ((reg & x20) >> 0);
        reg = (reg >> 1) | (bit << 19);
        period = period + 1;
        println!("start = {:020b}, reg = {:020b}", start_state, reg);
        found = reg == start_state;
    }
    println!("Period = {}", period);
}

参考