LFSR

線型回帰フィードバックレジスタ。乱数列を生成する

構造

n bit シフトレジスタのいくつかのbitをXORで線型結合したやつ。雑なイメージだと↓な感じ。（本当は初期状態やtapをランダムに決めてはだめ） tapのことを特性多項式や帰還多項式と言ったりする

class LFSR():
    def __init__(self, n):
        self.state = [getRandBit(1) for _ in range(n)]
        self.taps = [getRandBit(1) for _ in range(n)]
    def next(self):
        output = reduce(xor, [bit&tap for bit,tap in zip(self.state, self.taps)])
        self.state = self.state[1:] + [output]
        return output

入力

出力した0または1が入力としてフィードバックされる。いやフィードバックはどこでも良いが……

出力

0または1が出力される。

周期

0 / 1に周期はあるのか→ある

内部状態が n bit、すなわち通りなので、最大で回の出力で必ず同じ内部状態が現れることになる。周期は tap によって決まる

GF(2ⁿ)上の多項式との対応

tapは 上の多項式とみなせる（多項式の係数をベクトルで表したものに見えるので）

帰還多項式と周期の関係

帰還多項式の位数がLFSRの最短周期になる。原始多項式の時最長

実装

まともな実装は多項式の係数をbit列で表して整数になる。fibonacci型とgalois型があるっぽい？

これはzer0lfsrという問題から拝借してきた実装

class lfsr():
    def __init__(self, init, mask, length):
        self.init = init
        self.mask = mask
        self.lengthmask = 2**(length+1)-1

    def next(self):
        nextdata = (self.init << 1) & self.lengthmask 
        i = self.init & self.mask & self.lengthmask 
        output = 0
        while i != 0:
            output ^= (i & 1)
            i = i >> 1
        nextdata ^= output
        self.init = nextdata
        return output

これもわかりやすい実装ですね

def generate_bit_sequence(initial_state):
    state = initial_state
    while True:
        last_bit = state & 1
        yield last_bit
        middle_bit = state >> 3 & 1
        state = (state >> 1) | ((last_bit ^ middle_bit) << 4)

状態の復元

LFSRを「逆に回す」ということもできる（線形性があるので）

参考： 0CTF 2019 Quals | zer0lfsr, 2018 CISCN oldstreamgame | oldstreamgame

ただし、状態を左シフトしていく場合は最上位bitが、右シフトしていく場合は最下位bitが立っていないと状態が一意に定まらないので、これは出来ない。たいていの原始根では最上位bitも最下位bitも立っているはずなので心配しなくてよいが……