lfsr.py

''' Implementation and table of LFSRs

    Currently only Fibonacci LFSR is implemented.

    Galois LFSRs wouldn't be too hard though.
'''

import random

# note: we use uint8 and manually mask & 1 because bool is saturating
import numpy as np


def product(seq):
    import functools
    import operator
    return functools.reduce(operator.mul, seq, 1)


def parity(val):
    bits = val.bit_length()
    shift = 1
    while shift <= bits:
        val ^= val >> shift
        shift <<= 1
    return val & 1


class BitVec:
    def __init__(self, val, *, bits=None):
        if bits is None:
            bits = val.bit_length()
        vec = self.vector = np.zeros(bits + 1, dtype=np.uint8)
        vec[0] = 1
        for i in range(bits):
            vec[i+1] = bool(val & (1 << i))

    @classmethod
    def from_vector(cls, vec):
        assert len(vec.shape) == 1
        rv = cls.__new__(cls)
        rv.vector = vec & 1
        return rv

    @classmethod
    def from_column_matrix(cls, vec):
        assert len(vec.shape) == 2 and vec.shape[1] == 1
        return cls.from_vector(np.array(vec)[:, 0])

    def as_column_matrix(self):
        return np.matrix([self.vector]).T

    def to_int(self):
        rv = 0
        vec = self.vector
        for i in range(1, len(vec)):
            if vec[i]:
                rv |= 1 << (i-1)
        return rv


def matrix_moved_left(matrix, shift, *, fix):
    rows, cols = matrix.shape
    left = matrix[0:rows, shift:cols]
    right = np.zeros(shape=(rows, shift), dtype=matrix.dtype)
    rv = np.concatenate((left, right), axis=1)
    if fix:
        rv = matrix_fix_invariant(rv)
    return rv
def matrix_moved_right(matrix, shift, *, fix):
    rows, cols = matrix.shape
    left = np.zeros(shape=(rows, shift), dtype=matrix.dtype)
    right = matrix[0:rows, 0:cols-shift]
    rv = np.concatenate((left, right), axis=1)
    if fix:
        rv = matrix_fix_invariant(rv)
    return rv
def matrix_moved_up(matrix, shift, *, fix):
    rows, cols = matrix.shape
    top = matrix[shift:rows, 0:cols]
    bottom = np.zeros(shape=(shift, cols), dtype=matrix.dtype)
    rv = np.concatenate((top, bottom), axis=0)
    if fix:
        rv = matrix_fix_invariant(rv)
    return rv
def matrix_moved_down(matrix, shift, *, fix):
    rows, cols = matrix.shape
    top = np.zeros(shape=(shift, cols), dtype=matrix.dtype)
    bottom = matrix[0:rows-shift, 0:cols]
    rv = np.concatenate((top, bottom), axis=0)
    if fix:
        rv = matrix_fix_invariant(rv)
    return rv

def matrix_rotated_left(matrix, shift, *, fix):
    if fix:
        rows, cols = matrix.shape
        invariant = matrix[0:rows, 0:1]
        left = matrix[0:rows, shift+1:cols]
        right = matrix[0:rows, 1:shift+1]
        rv = np.concatenate((invariant, left, right), axis=1)
        return rv
    rows, cols = matrix.shape
    left = matrix[0:rows, shift:cols]
    right = matrix[0:rows, 0:shift]
    rv = np.concatenate((left, right), axis=1)
    return rv
def matrix_rotated_right(matrix, shift, *, fix):
    if fix:
        rows, cols = matrix.shape
        invariant = matrix[0:rows, 0:1]
        left = matrix[0:rows, cols-shift:cols]
        right = matrix[0:rows, 1:cols-shift]
        rv = np.concatenate((invariant, left, right), axis=1)
        return rv
    rows, cols = matrix.shape
    left = matrix[0:rows, cols-shift:cols]
    right = matrix[0:rows, 0:cols-shift]
    rv = np.concatenate((left, right), axis=1)
    return rv
def matrix_rotated_up(matrix, shift, *, fix):
    if fix:
        rows, cols = matrix.shape
        invariant = matrix[0:1, 0:cols]
        top = matrix[shift+1:rows, 0:cols]
        bottom = matrix[1:shift+1, 0:cols]
        rv = np.concatenate((invariant, top, bottom), axis=0)
        return rv
    rows, cols = matrix.shape
    top = matrix[shift:rows, 0:cols]
    bottom = matrix[0:shift, 0:cols]
    rv = np.concatenate((top, bottom), axis=0)
    return rv
def matrix_rotated_down(matrix, shift, *, fix):
    if fix:
        rows, cols = matrix.shape
        invariant = matrix[0:1, 0:cols]
        top = matrix[rows-shift:rows, 0:cols]
        bottom = matrix[1:rows-shift, 0:cols]
        rv = np.concatenate((invariant, top, bottom), axis=0)
        return rv
    rows, cols = matrix.shape
    top = matrix[rows-shift:rows, 0:cols]
    bottom = matrix[0:rows-shift, 0:cols]
    rv = np.concatenate((top, bottom), axis=0)
    return rv

def matrix_fix_invariant(matrix):
    matrix[0, :] = 0
    matrix[:, 0] = 0
    matrix[0, 0] = 1
    return matrix


class FunctionMatrix:
    def __init__(self, bits):
        self.matrix = np.matrix(np.identity(bits + 1, dtype=np.uint8))

    @classmethod
    def from_matrix(cls, mat):
        rv = cls.__new__(cls)
        rv.matrix = np.matrix(mat & 1)
        return rv

    def __call__(self, val):
        assert isinstance(val, int)
        return (self * BitVec(val, bits=len(self.matrix)-1)).to_int()

    def __xor__(self, other):
        if not isinstance(other, FunctionMatrix):
            return NotImplemented
        return self.from_matrix(self.matrix ^ other.matrix)

    def __mul__(self, other):
        if isinstance(other, BitVec):
            return BitVec.from_column_matrix(self.matrix * other.as_column_matrix())
        if isinstance(other, FunctionMatrix):
            return self.from_matrix(self.matrix * other.matrix)
        return NotImplemented

    def __pow__(self, exponent):
        if not isinstance(exponent, int):
            return NotImplemented
        return self.from_matrix(self.matrix ** exponent)

    def __lshift__(self, shift):
        if not isinstance(shift, int):
            return NotImplemented

        # if shift=2 and bits=6, then
        #
        #           ⎡1 0 0 0 0 0 0⎤
        #           ⎢0 0 0 0 0 0 0⎥
        #           ⎢0 0 0 0 0 0 0⎥
        # new_op =  ⎢0 1 0 0 0 0 0⎥
        #           ⎢0 0 1 0 0 0 0⎥
        #           ⎢0 0 0 1 0 0 0⎥
        #           ⎣0 0 0 0 1 0 0⎦
        #
        # which, if applied directly to a BitVec, changes
        #
        # [1]       [1]
        # [f]       [0]
        # [e]       [0]
        # [d] into  [f]
        # [c]       [e]
        # [b]       [d]
        # [a]       [c]
        #
        # and obvious abcdef << 2 == cdef00
        #
        # when applied to a matrix, it applies a new unary function on the left
        # think f(g(h(x))) - f is logically the last function/matrix to be applied

        new_op = matrix_moved_left(np.identity(len(self.matrix), dtype=np.uint8), shift, fix=True)
        return self.from_matrix(new_op * self.matrix)

    def __rshift__(self, shift):
        if not isinstance(shift, int):
            return NotImplemented
        new_op = matrix_moved_right(np.identity(len(self.matrix), dtype=np.uint8), shift, fix=True)
        return self.from_matrix(new_op * self.matrix)

    def rotl(self, shift):
        if not isinstance(shift, int):
            return NotImplemented
        new_op = matrix_rotated_left(np.identity(len(self.matrix), dtype=np.uint8), shift, fix=True)
        return self.from_matrix(new_op * self.matrix)

    def rotr(self, shift):
        if not isinstance(shift, int):
            return NotImplemented
        new_op = matrix_rotated_right(np.identity(len(self.matrix), dtype=np.uint8), shift, fix=True)
        return self.from_matrix(new_op * self.matrix)


class LFSR:
    def __init__(self, *taps):
        ''' Note: taps are 1-based; the highest is the width.
        '''
        assert (len(taps) & 1) == 0
        assert all([isinstance(t, int) and t > 0 for t in taps])
        assert taps == tuple(sorted(taps, reverse=True))
        assert len(taps) == len(set(taps))
        mask = 0
        for t in taps:
            mask |= 1 << (t-1)
        self.tap_mask = mask
        self.bits = taps[0]
        self.full_mask = (1 << self.bits) - 1
        assert self.tap_mask.bit_length() == self.full_mask.bit_length()
        self.matrix = None

    def __call__(self, state, count=1, *, xnor=False):
        for i in range(count):
            low = parity(state & self.tap_mask)
            state = ((state << 1) & self.full_mask) ^ low ^ xnor
        return state

    def jump(self, state, count, xnor=False):
        matrix = FunctionMatrix(bits=self.bits)
        matrix <<= 1
        matrix.matrix[1, :] = BitVec(self.tap_mask).vector
        matrix.matrix[1, 0] = xnor
        return pow(matrix, count)(state)

    def verify(self):
        for x in (False, True):
            width = self.bits
            period = self.full_mask
            locked_state = -x & period
            assert self(locked_state, xnor=x) == locked_state
            assert self.jump(locked_state, 1, xnor=x) == locked_state
            if width <= 16:
                assert self(1, period, xnor=x) == 1
                for i in range(1 - x, 2**width - x):
                    assert 0 <= self(i, xnor=x) < 2**width
            assert self.jump(1, period, xnor=x) == 1
            for factor in bad_periods[width]:
                assert self.jump(1, factor, xnor=x) != 1

# for these bit widths, we can check whether the LFSR is full-period or not
# simply jump by full_period / each factor, and verify that none of those
# hit your start point
# (note: haven't implemented jump yet though, needs matrices)
#
# we only need to list each factor once (and could better store the inverses
# directly), but this helps check that the factors weren't miscopied

mask_factors = {
        #0: None, # 2⁰-1 = 0
        1: [], # 2¹-1 = 1
        2: [3], # 2²-1 = 3
        3: [7], # 2³-1 = 7
        4: [3, 5], # 2⁴-1 = 15
        5: [31], # 2⁵-1 = 31
        6: [3, 3, 7], # 2⁶-1 = 63
        7: [127], # 2⁷-1 = 127
        8: [3, 5, 17], # 2⁸-1 = 255
        9: [7, 73], # 2⁹-1 = 511
        10: [3, 11, 31], # 2¹⁰-1 = 1023
        11: [23, 89], # 2¹¹-1 = 2047
        12: [3, 3, 5, 7, 13], # 2¹²-1 = 4095
        13: [8191], # 2¹³-1 = 8191
        14: [3, 43, 127], # 2¹⁴-1 = 16383
        15: [7, 31, 151], # 2¹⁵-1 = 32767
        16: [3, 5, 17, 257], # 2¹⁶-1 = 65535
        17: [131071], # 2¹⁷-1 = 131071
        18: [3, 3, 3, 7, 19, 73], # 2¹⁸-1 = 262143
        19: [524287], # 2¹⁹-1 = 524287
        20: [3, 5, 5, 11, 31, 41], # 2²⁰-1 = 1048575
        21: [7, 7, 127, 337], # 2²¹-1 = 2097151
        22: [3, 23, 89, 683], # 2²²-1 = 4194303
        23: [47, 178481], # 2²³-1 = 8388607
        24: [3, 3, 5, 7, 13, 17, 241], # 2²⁴-1 = 16777215
        25: [31, 601, 1801], # 2²⁵-1 = 33554431
        26: [3, 2731, 8191], # 2²⁶-1 = 67108863
        27: [7, 73, 262657], # 2²⁷-1 = 134217727
        28: [3, 5, 29, 43, 113, 127], # 2²⁸-1 = 268435455
        29: [233, 1103, 2089], # 2²⁹-1 = 536870911
        30: [3, 3, 7, 11, 31, 151, 331], # 2³⁰-1 = 1073741823
        31: [2147483647], # 2³¹-1 = 2147483647
        32: [3, 5, 17, 257, 65537], # 2³²-1 = 4294967295
        33: [7, 23, 89, 599479], # 2³³-1 = 8589934591
        34: [3, 43691, 131071], # 2³⁴-1 = 17179869183
        35: [31, 71, 127, 122921], # 2³⁵-1 = 34359738367
        36: [3, 3, 3, 5, 7, 13, 19, 37, 73, 109], # 2³⁶-1 = 68719476735
        37: [223, 616318177], # 2³⁷-1 = 137438953471
        38: [3, 174763, 524287], # 2³⁸-1 = 274877906943
        39: [7, 79, 8191, 121369], # 2³⁹-1 = 549755813887
        40: [3, 5, 5, 11, 17, 31, 41, 61681], # 2⁴⁰-1 = 1099511627775
        41: [13367, 164511353], # 2⁴¹-1 = 2199023255551
        42: [3, 3, 7, 7, 43, 127, 337, 5419], # 2⁴²-1 = 4398046511103
        43: [431, 9719, 2099863], # 2⁴³-1 = 8796093022207
        44: [3, 5, 23, 89, 397, 683, 2113], # 2⁴⁴-1 = 17592186044415
        45: [7, 31, 73, 151, 631, 23311], # 2⁴⁵-1 = 35184372088831
        46: [3, 47, 178481, 2796203], # 2⁴⁶-1 = 70368744177663
        47: [2351, 4513, 13264529], # 2⁴⁷-1 = 140737488355327
        48: [3, 3, 5, 7, 13, 17, 97, 241, 257, 673], # 2⁴⁸-1 = 281474976710655
        49: [127, 4432676798593], # 2⁴⁹-1 = 562949953421311
        50: [3, 11, 31, 251, 601, 1801, 4051], # 2⁵⁰-1 = 1125899906842623
        51: [7, 103, 2143, 11119, 131071], # 2⁵¹-1 = 2251799813685247
        52: [3, 5, 53, 157, 1613, 2731, 8191], # 2⁵²-1 = 4503599627370495
        53: [6361, 69431, 20394401], # 2⁵³-1 = 9007199254740991
        54: [3, 3, 3, 3, 7, 19, 73, 87211, 262657], # 2⁵⁴-1 = 18014398509481983
        55: [23, 31, 89, 881, 3191, 201961], # 2⁵⁵-1 = 36028797018963967
        56: [3, 5, 17, 29, 43, 113, 127, 15790321], # 2⁵⁶-1 = 72057594037927935
        57: [7, 32377, 524287, 1212847], # 2⁵⁷-1 = 144115188075855871
        58: [3, 59, 233, 1103, 2089, 3033169], # 2⁵⁸-1 = 288230376151711743
        59: [179951, 3203431780337], # 2⁵⁹-1 = 576460752303423487
        60: [3, 3, 5, 5, 7, 11, 13, 31, 41, 61, 151, 331, 1321], # 2⁶⁰-1 = 1152921504606846975
        61: [2305843009213693951], # 2⁶¹-1 = 2305843009213693951
        62: [3, 715827883, 2147483647], # 2⁶²-1 = 4611686018427387903
        63: [7, 7, 73, 127, 337, 92737, 649657], # 2⁶³-1 = 9223372036854775807
        64: [3, 5, 17, 257, 641, 65537, 6700417], # 2⁶⁴-1 = 18446744073709551615
        65: [31, 8191, 145295143558111], # 2⁶⁵-1 = 36893488147419103231
        66: [3, 3, 7, 23, 67, 89, 683, 20857, 599479], # 2⁶⁶-1 = 73786976294838206463
        67: [193707721, 761838257287], # 2⁶⁷-1 = 147573952589676412927
        68: [3, 5, 137, 953, 26317, 43691, 131071], # 2⁶⁸-1 = 295147905179352825855
        69: [7, 47, 178481, 10052678938039], # 2⁶⁹-1 = 590295810358705651711
        70: [3, 11, 31, 43, 71, 127, 281, 86171, 122921], # 2⁷⁰-1 = 1180591620717411303423
        71: [228479, 48544121, 212885833], # 2⁷¹-1 = 2361183241434822606847
        72: [3, 3, 3, 5, 7, 13, 17, 19, 37, 73, 109, 241, 433, 38737], # 2⁷²-1 = 4722366482869645213695
        73: [439, 2298041, 9361973132609], # 2⁷³-1 = 9444732965739290427391
        74: [3, 223, 1777, 25781083, 616318177], # 2⁷⁴-1 = 18889465931478580854783
        75: [7, 31, 151, 601, 1801, 100801, 10567201], # 2⁷⁵-1 = 37778931862957161709567
        76: [3, 5, 229, 457, 174763, 524287, 525313], # 2⁷⁶-1 = 75557863725914323419135
        77: [23, 89, 127, 581283643249112959], # 2⁷⁷-1 = 151115727451828646838271
        78: [3, 3, 7, 79, 2731, 8191, 121369, 22366891], # 2⁷⁸-1 = 302231454903657293676543
        79: [2687, 202029703, 1113491139767], # 2⁷⁹-1 = 604462909807314587353087
        80: [3, 5, 5, 11, 17, 31, 41, 257, 61681, 4278255361], # 2⁸⁰-1 = 1208925819614629174706175
        81: [7, 73, 2593, 71119, 262657, 97685839], # 2⁸¹-1 = 2417851639229258349412351
        82: [3, 83, 13367, 164511353, 8831418697], # 2⁸²-1 = 4835703278458516698824703
        83: [167, 57912614113275649087721], # 2⁸³-1 = 9671406556917033397649407
        84: [3, 3, 5, 7, 7, 13, 29, 43, 113, 127, 337, 1429, 5419, 14449], # 2⁸⁴-1 = 19342813113834066795298815
        85: [31, 131071, 9520972806333758431], # 2⁸⁵-1 = 38685626227668133590597631
        86: [3, 431, 9719, 2099863, 2932031007403], # 2⁸⁶-1 = 77371252455336267181195263
        87: [7, 233, 1103, 2089, 4177, 9857737155463], # 2⁸⁷-1 = 154742504910672534362390527
        88: [3, 5, 17, 23, 89, 353, 397, 683, 2113, 2931542417], # 2⁸⁸-1 = 309485009821345068724781055
        89: [618970019642690137449562111], # 2⁸⁹-1 = 618970019642690137449562111
        90: [3, 3, 3, 7, 11, 19, 31, 73, 151, 331, 631, 23311, 18837001], # 2⁹⁰-1 = 1237940039285380274899124223
        91: [127, 911, 8191, 112901153, 23140471537], # 2⁹¹-1 = 2475880078570760549798248447
        92: [3, 5, 47, 277, 1013, 1657, 30269, 178481, 2796203], # 2⁹²-1 = 4951760157141521099596496895
        93: [7, 2147483647, 658812288653553079], # 2⁹³-1 = 9903520314283042199192993791
        94: [3, 283, 2351, 4513, 13264529, 165768537521], # 2⁹⁴-1 = 19807040628566084398385987583
        95: [31, 191, 524287, 420778751, 30327152671], # 2⁹⁵-1 = 39614081257132168796771975167
        96: [3, 3, 5, 7, 13, 17, 97, 193, 241, 257, 673, 65537, 22253377], # 2⁹⁶-1 = 79228162514264337593543950335
        97: [11447, 13842607235828485645766393], # 2⁹⁷-1 = 158456325028528675187087900671
        98: [3, 43, 127, 4363953127297, 4432676798593], # 2⁹⁸-1 = 316912650057057350374175801343
        99: [7, 23, 73, 89, 199, 153649, 599479, 33057806959], # 2⁹⁹-1 = 633825300114114700748351602687
        100: [3, 5, 5, 5, 11, 31, 41, 101, 251, 601, 1801, 4051, 8101, 268501], # 2¹⁰⁰-1 = 1267650600228229401496703205375
        101: [7432339208719, 341117531003194129], # 2¹⁰¹-1 = 2535301200456458802993406410751
        102: [3, 3, 7, 103, 307, 2143, 2857, 6529, 11119, 43691, 131071], # 2¹⁰²-1 = 5070602400912917605986812821503
        103: [2550183799, 3976656429941438590393], # 2¹⁰³-1 = 10141204801825835211973625643007
        104: [3, 5, 17, 53, 157, 1613, 2731, 8191, 858001, 308761441], # 2¹⁰⁴-1 = 20282409603651670423947251286015
        105: [7, 7, 31, 71, 127, 151, 337, 29191, 106681, 122921, 152041], # 2¹⁰⁵-1 = 40564819207303340847894502572031
        106: [3, 107, 6361, 69431, 20394401, 28059810762433], # 2¹⁰⁶-1 = 81129638414606681695789005144063
        107: [162259276829213363391578010288127], # 2¹⁰⁷-1 = 162259276829213363391578010288127
        108: [3, 3, 3, 3, 5, 7, 13, 19, 37, 73, 109, 87211, 246241, 262657, 279073], # 2¹⁰⁸-1 = 324518553658426726783156020576255
        109: [745988807, 870035986098720987332873], # 2¹⁰⁹-1 = 649037107316853453566312041152511
        110: [3, 11, 11, 23, 31, 89, 683, 881, 2971, 3191, 201961, 48912491], # 2¹¹⁰-1 = 1298074214633706907132624082305023
        111: [7, 223, 321679, 26295457, 319020217, 616318177], # 2¹¹¹-1 = 2596148429267413814265248164610047
        112: [3, 5, 17, 29, 43, 113, 127, 257, 5153, 15790321, 54410972897], # 2¹¹²-1 = 5192296858534827628530496329220095
        113: [3391, 23279, 65993, 1868569, 1066818132868207], # 2¹¹³-1 = 10384593717069655257060992658440191
        114: [3, 3, 7, 571, 32377, 174763, 524287, 1212847, 160465489], # 2¹¹⁴-1 = 20769187434139310514121985316880383
        115: [31, 47, 14951, 178481, 4036961, 2646507710984041], # 2¹¹⁵-1 = 41538374868278621028243970633760767
        116: [3, 5, 59, 233, 1103, 2089, 3033169, 107367629, 536903681], # 2¹¹⁶-1 = 83076749736557242056487941267521535
        117: [7, 73, 79, 937, 6553, 8191, 86113, 121369, 7830118297], # 2¹¹⁷-1 = 166153499473114484112975882535043071
        118: [3, 2833, 37171, 179951, 1824726041, 3203431780337], # 2¹¹⁸-1 = 332306998946228968225951765070086143
        119: [127, 239, 20231, 131071, 62983048367, 131105292137], # 2¹¹⁹-1 = 664613997892457936451903530140172287
        120: [3, 3, 5, 5, 7, 11, 13, 17, 31, 41, 61, 151, 241, 331, 1321, 61681, 4562284561], # 2¹²⁰-1 = 1329227995784915872903807060280344575
        121: [23, 89, 727, 1786393878363164227858270210279], # 2¹²¹-1 = 2658455991569831745807614120560689151
        # factor(1) is very slow for this one
        122: [3, 768614336404564651, 2305843009213693951], # 2¹²²-1 = 5316911983139663491615228241121378303
        123: [7, 13367, 3887047, 164511353, 177722253954175633], # 2¹²³-1 = 10633823966279326983230456482242756607
        124: [3, 5, 5581, 8681, 49477, 384773, 715827883, 2147483647], # 2¹²⁴-1 = 21267647932558653966460912964485513215
        125: [31, 601, 1801, 269089806001, 4710883168879506001], # 2¹²⁵-1 = 42535295865117307932921825928971026431
        126: [3, 3, 3, 7, 7, 19, 43, 73, 127, 337, 5419, 92737, 649657, 77158673929], # 2¹²⁶-1 = 85070591730234615865843651857942052863
        127: [170141183460469231731687303715884105727], # 2¹²⁷-1 = 170141183460469231731687303715884105727
        # factor(1) gives up at this point. WolframAlpha to the rescue!
        # (but actually I did this first one using MATH)
        128: [3, 5, 17, 257, 641, 65537, 274177, 6700417, 67280421310721], # 2¹²⁸-1 = 340282366920938463463374607431768211455
        129: [7, 431, 9719, 2099863, 11053036065049294753459639],
        130: [3, 11, 31, 131, 2731, 8191, 409891, 7623851, 145295143558111],
        131: [263, 10350794431055162386718619237468234569],
        132: [3, 3, 5, 7, 13, 23, 67, 89, 397, 683, 2113, 20857, 312709, 599479, 4327489],
        133: [127, 524287, 163537220852725398851434325720959],
        134: [3, 7327657, 193707721, 761838257287, 6713103182899],
        135: [7, 31, 73, 151, 271, 631, 23311, 262657, 348031, 49971617830801],
        136: [3, 5, 17, 17, 137, 953, 26317, 43691, 131071, 354689, 2879347902817],
        137: [32032215596496435569, 5439042183600204290159],
        138: [3, 3, 7, 47, 139, 178481, 2796203, 168749965921, 10052678938039],
        139: [5625767248687, 123876132205208335762278423601],
        140: [3, 5, 5, 11, 29, 31, 41, 43, 71, 113, 127, 281, 86171, 122921, 7416361, 47392381],
        141: [7, 2351, 4513, 13264529, 4375578271, 646675035253258729],
        142: [3, 228479, 48544121, 56409643, 212885833, 13952598148481],
        143: [23, 89, 8191, 724153, 158822951431, 5782172113400990737],
        144: [3, 3, 3, 5, 7, 13, 17, 19, 37, 73, 97, 109, 241, 257, 433, 577, 673, 38737, 487824887233],
        145: [31, 233, 1103, 2089, 2679895157783862814690027494144991],
        146: [3, 439, 1753, 2298041, 9361973132609, 1795918038741070627],
        147: [7, 7, 7, 127, 337, 4432676798593, 2741672362528725535068727],
        148: [3, 5, 149, 223, 593, 1777, 25781083, 184481113, 231769777, 616318177],
        149: [86656268566282183151, 8235109336690846723986161],
        150: [3, 3, 7, 11, 31, 151, 251, 331, 601, 1801, 4051, 100801, 10567201, 1133836730401],
        151: [18121, 55871, 165799, 2332951, 7289088383388253664437433],
        152: [3, 5, 17, 229, 457, 1217, 148961, 174763, 524287, 525313, 24517014940753],
        153: [7, 73, 103, 919, 2143, 11119, 131071, 75582488424179347083438319],
        154: [3, 23, 43, 89, 127, 617, 683, 78233, 35532364099, 581283643249112959],
        155: [31, 31, 311, 11471, 73471, 2147483647, 4649919401, 18158209813151],
        156: [3, 3, 5, 7, 13, 13, 53, 79, 157, 313, 1249, 1613, 2731, 3121, 8191, 21841, 121369, 22366891],
        157: [852133201, 60726444167, 1654058017289, 2134387368610417],
        158: [3, 2687, 202029703, 1113491139767, 201487636602438195784363],
        159: [7, 6361, 6679, 69431, 13960201, 20394401, 540701761, 229890275929],
        160: [3, 5, 5, 11, 17, 31, 41, 257, 61681, 65537, 414721, 4278255361, 44479210368001],
        161: [47, 127, 1289, 178481, 3188767, 45076044553, 14808607715315782481],
        162: [3, 3, 3, 3, 3, 7, 19, 73, 163, 2593, 71119, 87211, 135433, 262657, 97685839, 272010961],
        163: [150287, 704161, 110211473, 27669118297, 36230454570129675721],
        164: [3, 5, 83, 10169, 13367, 181549, 12112549, 43249589, 164511353, 8831418697],
        165: [7, 23, 31, 89, 151, 881, 3191, 201961, 599479, 2048568835297380486760231],
        166: [3, 167, 499, 1163, 2657, 155377, 13455809771, 57912614113275649087721],
        167: [2349023, 79638304766856507377778616296087448490695649],
        168: [3, 3, 5, 7, 7, 13, 17, 29, 43, 113, 127, 241, 337, 1429, 3361, 5419, 14449, 15790321, 88959882481],
        169: [4057, 8191, 6740339310641, 3340762283952395329506327023033],
        170: [3, 11, 31, 43691, 131071, 9520972806333758431, 26831423036065352611],
        171: [7, 73, 32377, 524287, 1212847, 93507247, 3042645634792541312037847],
        172: [3, 5, 173, 431, 9719, 101653, 500177, 2099863, 1759217765581, 2932031007403],
        173: [730753, 1505447, 70084436712553223, 155285743288572277679887],
        174: [3, 3, 7, 59, 233, 1103, 2089, 4177, 3033169, 9857737155463, 96076791871613611],
        175: [31, 71, 127, 601, 1801, 39551, 122921, 60816001, 535347624791488552837151],
        176: [3, 5, 17, 23, 89, 257, 353, 397, 683, 2113, 229153, 119782433, 2931542417, 43872038849],
        177: [7, 179951, 184081, 27989941729, 3203431780337, 9213624084535989031],
        178: [3, 179, 62020897, 18584774046020617, 618970019642690137449562111],
        179: [359, 1433, 1489459109360039866456940197095433721664951999121],
        180: [3, 3, 3, 5, 5, 7, 11, 13, 19, 31, 37, 41, 61, 73, 109, 151, 181, 331, 631, 1321, 23311, 54001, 18837001, 29247661],
        181: [43441, 1164193, 7648337, 7923871097285295625344647665764672671],
        182: [3, 43, 127, 911, 2731, 8191, 224771, 1210483, 112901153, 23140471537, 25829691707],
        183: [7, 367, 55633, 2305843009213693951, 37201708625305146303973352041],
        184: [3, 5, 17, 47, 277, 1013, 1657, 30269, 178481, 2796203, 291280009243618888211558641],
        185: [31, 223, 616318177, 1587855697992791, 7248808599285760001152755641],
        186: [3, 3, 7, 529510939, 715827883, 2147483647, 2903110321, 658812288653553079],
        187: [23, 89, 131071, 707983, 1032670816743843860998850056278950666491537],
        188: [3, 5, 283, 2351, 3761, 4513, 13264529, 7484047069, 165768537521, 140737471578113],
        189: [7, 7, 73, 127, 337, 92737, 262657, 649657, 1560007, 207617485544258392970753527],
        190: [3, 11, 31, 191, 2281, 174763, 524287, 420778751, 30327152671, 3011347479614249131],
        191: [383, 7068569257, 39940132241, 332584516519201, 87274497124602996457],
        192: [3, 3, 5, 7, 13, 17, 97, 193, 241, 257, 641, 673, 65537, 6700417, 22253377, 18446744069414584321],
        # WolframAlpha standard computation time exceeded, and I don't have Pro.
        #193: [],
        194: [3, 971, 1553, 11447, 31817, 1100876018364883721, 13842607235828485645766393],
        195: [7, 31, 79, 151, 8191, 121369, 145295143558111, 134304196845099262572814573351],
        196: [3, 5, 29, 43, 113, 127, 197, 19707683773, 4363953127297, 4432676798593, 4981857697937],
        197: [7487, 26828803997912886929710867041891989490486893845712448833],
        198: [3, 3, 3, 7, 19, 23, 67, 73, 89, 199, 683, 5347, 20857, 153649, 599479, 33057806959, 242099935645987],
        199: [164504919713, 4884164093883941177660049098586324302977543600799],
        200: [3, 5, 5, 5, 11, 17, 31, 41, 101, 251, 401, 601, 1801, 4051, 8101, 61681, 268501, 340801, 2787601, 3173389601],
        201: [7, 1609, 22111, 193707721, 761838257287, 87449423397425857942678833145441],
        202: [3, 7432339208719, 341117531003194129, 845100400152152934331135470251],
        203: [127, 233, 1103, 2089, 136417, 121793911, 11348055580883272011090856053175361113],
        204: [3, 3, 5, 7, 13, 103, 137, 307, 409, 953, 2143, 2857, 3061, 6529, 11119, 13669, 26317, 43691, 131071, 1326700741],
        205: [31, 13367, 2940521, 164511353, 70171342151, 3655725065508797181674078959681],
        206: [3, 2550183799, 415141630193, 8142767081771726171, 3976656429941438590393],
        207: [7, 47, 73, 79903, 178481, 634569679, 2232578641663, 10052678938039, 42166482463639],
        208: [3, 5, 17, 53, 157, 257, 1613, 2731, 8191, 858001, 308761441, 78919881726271091143763623681],
        209: [23, 89, 524287, 94803416684681, 1512348937147247, 5346950541323960232319657],
        210: [3, 3, 7, 7, 11, 31, 43, 71, 127, 151, 211, 281, 331, 337, 5419, 29191, 86171, 106681, 122921, 152041, 664441, 1564921],
        # WolframAlpha standard computation time exceeded, and I don't have Pro.
        #211: [],
        212: [3, 5, 107, 6361, 69431, 15358129, 20394401, 586477649, 28059810762433, 1801439824104653],
        213: [7, 66457, 228479, 48544121, 212885833, 2849881972114740679, 4205268574191396793],
        # WolframAlpha standard computation time exceeded, and I don't have Pro.
        # but I used MATH since unlike the previous ones, it's not prime
        # (and reported a bug)
        214: [3, 643, 84115747449047881488635567801, 162259276829213363391578010288127],
        215: [31, 431, 1721, 9719, 2099863, 731516431, 514851898711, 297927289744047764444862191],
        216: [3, 3, 3, 3, 5, 7, 13, 17, 19, 37, 73, 109, 241, 433, 38737, 87211, 246241, 262657, 279073, 33975937, 138991501037953],
        217: [127, 5209, 62497, 2147483647, 6268703933840364033151, 378428804431424484082633],
        # MATH again
        218: [3, 104124649, 745988807, 870035986098720987332873, 2077756847362348863128179],
        219: [7, 439, 3943, 2298041, 9361973132609, 671165898617413417, 4815314615204347717321],
        220: [3, 5, 5, 11, 11, 23, 31, 41, 89, 397, 683, 881, 2113, 2971, 3191, 201961, 48912491, 415878438361, 3630105520141],
        221: [1327, 8191, 131071, 2365454398418399772605086209214363458552839866247069233],
        222: [3, 3, 7, 223, 1777, 3331, 17539, 321679, 25781083, 26295457, 319020217, 616318177, 107775231312019],
        223: [18287, 196687, 1466449, 2916841, 1469495262398780123809, 596242599987116128415063],
        224: [3, 5, 17, 29, 43, 113, 127, 257, 449, 2689, 5153, 65537, 15790321, 183076097, 54410972897, 358429848460993],
        225: [7, 31, 73, 151, 601, 631, 1801, 23311, 100801, 115201, 617401, 10567201, 1348206751, 13861369826299351],
        226: [3, 227, 3391, 23279, 48817, 65993, 1868569, 636190001, 1066818132868207, 491003369344660409],
        # WolframAlpha standard computation time exceeded, and I don't have Pro.
        #227: [],
        228: [3, 3, 5, 7, 13, 229, 457, 571, 32377, 131101, 160969, 174763, 524287, 525313, 1212847, 160465489, 275415303169],
        # WolframAlpha standard computation time exceeded, and I don't have Pro.
        #229: [],
        230: [3, 11, 31, 47, 691, 14951, 178481, 2796203, 4036961, 1884103651, 345767385170491, 2646507710984041],
        231: [7, 7, 23, 89, 127, 337, 463, 599479, 581283643249112959, 4982397651178256151338302204762057 ],
        232: [3, 5, 17, 59, 233, 1103, 2089, 59393, 3033169, 107367629, 536903681, 82280195167144119832390568177],
        233: [1399, 135607, 622577, 116868129879077600270344856324766260085066532853492178431],
        234: [3, 3, 3, 7, 19, 73, 79, 937, 2731, 6553, 8191, 86113, 121369, 22366891, 7830118297, 5302306226370307681801],
        235: [31, 2351, 4513, 13264529, 2391314881, 72296287361, 73202300395158005845473537146974751],
        236: [3, 5, 1181, 2833, 3541, 37171, 157649, 174877, 179951, 5521693, 1824726041, 104399276341, 3203431780337],
        237: [7, 1423, 2687, 49297, 202029703, 1113491139767, 23728823512345609279, 31357373417090093431],
        238: [3, 43, 127, 239, 20231, 43691, 131071, 823679683, 62983048367, 131105292137, 143162553165560959297],
        239: [479, 1913, 5737, 176383, 134000609, 7110008717824458123105014279253754096863768062879],
        240: [3, 3, 5, 5, 7, 11, 13, 17, 31, 41, 61, 97, 151, 241, 257, 331, 673, 1321, 61681, 394783681, 4278255361, 4562284561, 46908728641],
        241: [22000409, 160619474372352289412737508720216839225805656328990879953332340439],
        # MATH again
        242: [3, 23, 89, 683, 727, 117371, 11054184582797800455736061107, 1786393878363164227858270210279],
        243: [7, 73, 487, 2593, 71119, 262657, 97685839, 16753783618801, 192971705688577, 3712990163251158343],
        244: [3, 5, 733, 1709, 3456749, 368140581013, 667055378149, 768614336404564651, 2305843009213693951],
        245: [31, 71, 127, 1471, 122921, 4432676798593, 252359902034571016856214298851708529738525821631],
        246: [3, 3, 7, 83, 739, 13367, 165313, 3887047, 164511353, 8831418697, 13194317913029593, 177722253954175633],
        247: [8191, 15809, 524287, 6459570124697, 402004106269663, 1282816117617265060453496956212169],
        248: [3, 5, 17, 5581, 8681, 49477, 290657, 384773, 715827883, 2147483647, 3770202641, 1141629180401976895873],
        # MATH, but fancier
        249: [7, 167, 1621324657, 57912614113275649087721, 8241594690167137359552274418432855740327],
        250: [3, 11, 31, 251, 601, 1801, 4051, 229668251, 269089806001, 4710883168879506001, 5519485418336288303251],
        # WolframAlpha standard computation time exceeded, and I don't have Pro.
        #251: [],
        252: [3, 3, 3, 5, 7, 7, 13, 19, 29, 37, 43, 73, 109, 113, 127, 337, 1429, 5419, 14449, 92737, 649657, 40388473189, 77158673929, 118750098349],
        # MATH not helpful, the hard factor is part of both 2¹¹+1 and 2²³+1
        #253: [],
        254: [3, 56713727820156410577229101238628035243, 170141183460469231731687303715884105727],
        255: [7, 31, 103, 151, 2143, 11119, 106591, 131071, 949111, 9520972806333758431, 5702451577639775545838643151],
        256: [3, 5, 17, 257, 641, 65537, 274177, 6700417, 67280421310721, 59649589127497217, 5704689200685129054721],
        # MATH again
        512: [3, 5, 17, 257, 641, 65537, 274177, 6700417, 67280421310721, 1238926361552897, 59649589127497217, 5704689200685129054721, 93461639715357977769163558199606896584051237541638188580280321],
        # MATH not helpful since 2⁵¹²+1 isn't easy to factor.
        # 1024: [], # 2¹⁰²⁴-1
        # 2048: [], # 2²⁰⁴⁸-1
        # 4096: [], # 2⁴⁰⁹⁶-1
}

known_lfsrs = [
        # 2 taps
        LFSR(2, 1),
        LFSR(3, 2),
        LFSR(4, 3),
        LFSR(5, 3),
        LFSR(6, 5),
        LFSR(7, 6),
        LFSR(9, 5),
        LFSR(10, 7),
        LFSR(11, 9),
        LFSR(15, 14),
        LFSR(17, 14),
        LFSR(18, 11),
        LFSR(20, 17),
        LFSR(21, 19),
        LFSR(22, 21),
        LFSR(23, 18),
        LFSR(25, 22),
        LFSR(28, 25),
        LFSR(29, 27),
        LFSR(31, 28),
        LFSR(33, 20),
        LFSR(35, 33),
        LFSR(36, 25),
        LFSR(39, 35),
        LFSR(41, 38),
        LFSR(47, 42),
        LFSR(49, 40),
        LFSR(52, 49),
        LFSR(55, 31),
        LFSR(57, 50),
        LFSR(58, 39),
        LFSR(60, 59),
        LFSR(63, 62),
        LFSR(65, 47),
        LFSR(68, 59),
        LFSR(71, 65),
        LFSR(73, 48),
        LFSR(79, 70),
        LFSR(81, 77),
        LFSR(84, 71),
        LFSR(87, 74),
        LFSR(89, 51),
        LFSR(93, 91),
        LFSR(94, 73),
        LFSR(95, 84),
        LFSR(97, 91),
        LFSR(98, 87),
        LFSR(100, 63),
        LFSR(103, 94),
        LFSR(105, 89),
        LFSR(106, 91),
        LFSR(108, 77),
        LFSR(111, 101),
        LFSR(113, 104),
        LFSR(118, 85),
        LFSR(119, 111),
        LFSR(121, 103),
        LFSR(123, 121),
        LFSR(124, 87),
        LFSR(127, 126),
        LFSR(129, 124),
        LFSR(130, 127),
        LFSR(132, 103),
        LFSR(134, 77),
        LFSR(135, 124),
        LFSR(137, 116),
        LFSR(140, 111),
        LFSR(142, 121),
        LFSR(145, 93),
        LFSR(148, 121),
        LFSR(150, 97),
        LFSR(151, 148),
        LFSR(153, 152),
        LFSR(159, 128),
        LFSR(161, 143),
        LFSR(167, 161),
        LFSR(169, 135),
        LFSR(170, 147),
        LFSR(172, 165),
        LFSR(174, 161),
        LFSR(175, 169),
        LFSR(177, 169),
        LFSR(178, 91),
        LFSR(183, 127),
        LFSR(185, 161),
        LFSR(191, 182),
        LFSR(193, 178),
        LFSR(194, 107),
        LFSR(198, 133),
        LFSR(199, 165),
        LFSR(201, 187),
        LFSR(202, 147),
        LFSR(207, 164),
        LFSR(209, 203),
        LFSR(212, 107),
        LFSR(215, 192),
        LFSR(217, 172),
        LFSR(218, 207),
        LFSR(223, 190),
        LFSR(225, 193),
        LFSR(231, 205),
        LFSR(233, 159),
        LFSR(234, 203),
        LFSR(236, 231),
        LFSR(239, 203),
        LFSR(241, 171),
        LFSR(247, 165),
        LFSR(249, 163),
        LFSR(250, 147),
        LFSR(252, 185),
        LFSR(255, 203),
        LFSR(257, 245),
        LFSR(258, 175),
        LFSR(263, 170),
        LFSR(265, 223),
        LFSR(266, 219),
        LFSR(268, 243),
        LFSR(270, 217),
        LFSR(271, 213),
        LFSR(273, 250),
        LFSR(274, 207),
        LFSR(278, 273),
        LFSR(279, 274),
        LFSR(281, 188),
        LFSR(282, 247),
        LFSR(284, 165),
        LFSR(286, 217),
        LFSR(287, 216),
        LFSR(289, 268),
        LFSR(292, 195),
        LFSR(294, 233),
        LFSR(295, 247),
        LFSR(297, 292),
        LFSR(300, 293),
        LFSR(302, 261),
        LFSR(305, 203),
        LFSR(313, 234),
        LFSR(314, 299),
        LFSR(316, 181),
        LFSR(319, 283),
        LFSR(321, 290),
        LFSR(322, 255),
        LFSR(327, 293),
        LFSR(329, 279),
        LFSR(332, 209),
        LFSR(333, 331),
        LFSR(337, 282),
        LFSR(342, 217),
        LFSR(343, 268),
        LFSR(345, 323),
        LFSR(350, 297),
        LFSR(351, 317),
        LFSR(353, 284),
        LFSR(359, 291),
        LFSR(362, 299),
        LFSR(364, 297),
        LFSR(366, 337),
        LFSR(367, 346),
        LFSR(369, 278),
        LFSR(370, 231),
        LFSR(375, 359),
        LFSR(377, 336),
        LFSR(378, 335),
        LFSR(380, 333),
        LFSR(382, 301),
        LFSR(383, 293),
        LFSR(385, 379),
        LFSR(386, 303),
        LFSR(390, 301),
        LFSR(391, 363),
        LFSR(393, 386),
        LFSR(394, 259),
        LFSR(396, 371),
        LFSR(399, 313),
        LFSR(401, 249),
        LFSR(404, 215),
        LFSR(406, 249),
        LFSR(407, 336),
        LFSR(409, 322),
        LFSR(412, 265),
        LFSR(415, 313),
        LFSR(417, 310),
        LFSR(422, 273),
        LFSR(423, 398),
        LFSR(425, 413),
        LFSR(428, 323),
        LFSR(431, 311),
        LFSR(433, 400),
        LFSR(436, 271),
        LFSR(438, 373),
        LFSR(439, 390),
        LFSR(441, 410),
        LFSR(446, 341),
        LFSR(447, 374),
        LFSR(449, 315),
        LFSR(450, 371),
        LFSR(455, 417),
        LFSR(457, 441),
        LFSR(458, 255),
        LFSR(460, 399),
        LFSR(462, 389),
        LFSR(463, 370),
        LFSR(465, 406),
        LFSR(470, 321),
        LFSR(471, 470),
        LFSR(474, 283),
        LFSR(476, 461),
        LFSR(478, 357),
        LFSR(479, 375),
        LFSR(481, 343),
        LFSR(484, 379),
        LFSR(487, 393),
        LFSR(489, 406),
        LFSR(490, 271),
        LFSR(494, 357),
        LFSR(495, 419),
        LFSR(497, 419),
        LFSR(503, 500),
        LFSR(505, 349),
        LFSR(506, 411),
        LFSR(508, 399),
        LFSR(511, 501),
        LFSR(513, 428),
        LFSR(518, 485),
        LFSR(519, 440),
        LFSR(521, 489),
        LFSR(524, 357),
        LFSR(527, 480),
        LFSR(529, 487),
        LFSR(532, 531),
        LFSR(537, 443),
        LFSR(540, 361),
        LFSR(543, 527),
        LFSR(545, 423),
        LFSR(550, 357),
        LFSR(551, 416),
        LFSR(553, 514),
        LFSR(556, 403),
        LFSR(559, 525),
        LFSR(561, 490),
        LFSR(564, 401),
        LFSR(566, 413),
        LFSR(567, 424),
        LFSR(569, 492),
        LFSR(570, 503),
        LFSR(574, 561),
        LFSR(575, 429),
        LFSR(577, 552),
        LFSR(582, 497),
        LFSR(583, 453),
        LFSR(585, 464),
        LFSR(588, 437),
        LFSR(590, 497),
        LFSR(593, 507),
        LFSR(594, 575),
        LFSR(599, 569),
        LFSR(601, 400),
        LFSR(607, 502),
        LFSR(609, 578),
        LFSR(610, 483),
        LFSR(615, 404),
        LFSR(617, 417),
        LFSR(622, 325),
        LFSR(623, 555),
        LFSR(625, 492),
        LFSR(628, 405),
        LFSR(631, 324),
        LFSR(633, 532),
        LFSR(634, 319),
        LFSR(639, 623),
        LFSR(641, 630),
        LFSR(642, 523),
        LFSR(646, 397),
        LFSR(647, 642),
        LFSR(649, 612),
        LFSR(650, 647),
        LFSR(652, 559),
        LFSR(655, 567),
        LFSR(657, 619),
        LFSR(658, 603),
        LFSR(662, 365),
        LFSR(663, 406),
        LFSR(665, 632),
        LFSR(670, 517),
        LFSR(671, 656),
        LFSR(673, 645),
        LFSR(676, 435),
        LFSR(679, 613),
        LFSR(686, 489),
        LFSR(687, 674),
        LFSR(689, 675),
        LFSR(692, 393),
        LFSR(695, 483),
        LFSR(697, 430),
        LFSR(698, 483),
        LFSR(702, 665),
        LFSR(705, 686),
        LFSR(708, 421),
        LFSR(711, 619),
        LFSR(713, 672),
        LFSR(714, 691),
        LFSR(716, 533),
        LFSR(719, 569),
        LFSR(721, 712),
        LFSR(722, 491),
        LFSR(726, 721),
        LFSR(727, 547),
        LFSR(729, 671),
        LFSR(730, 583),
        LFSR(735, 691),
        LFSR(737, 732),
        LFSR(738, 391),
        LFSR(740, 587),
        LFSR(743, 653),
        LFSR(745, 487),
        LFSR(746, 395),
        LFSR(751, 733),
        LFSR(753, 595),
        LFSR(754, 735),
        LFSR(756, 407),
        LFSR(759, 661),
        LFSR(761, 758),
        LFSR(762, 679),
        LFSR(767, 599),
        LFSR(769, 649),
        LFSR(772, 765),
        LFSR(774, 589),
        LFSR(775, 408),
        LFSR(777, 748),
        LFSR(778, 403),
        LFSR(782, 453),
        LFSR(783, 715),
        LFSR(785, 693),

        # 4 taps
        LFSR(5, 4, 3, 2),
        LFSR(6, 5, 3, 2),
        LFSR(7, 6, 5, 4),
        LFSR(8, 6, 5, 4),
        LFSR(9, 8, 6, 5),
        LFSR(10, 9, 7, 6),
        LFSR(11, 10, 9, 7),
        LFSR(12, 6, 4, 1),
        LFSR(12, 11, 8, 6),
        LFSR(13, 4, 3, 1),
        LFSR(13, 12, 10, 9),
        LFSR(14, 5, 3, 1),
        LFSR(14, 13, 11, 9),
        LFSR(15, 14, 13, 11),
        LFSR(16, 14, 13, 11),
        LFSR(16, 15, 13, 4),
        LFSR(17, 16, 15, 14),
        LFSR(18, 17, 16, 13),
        LFSR(19, 6, 2, 1),
        LFSR(19, 18, 17, 14),
        LFSR(20, 19, 16, 14),
        LFSR(21, 20, 19, 16),
        LFSR(22, 19, 18, 17),
        LFSR(23, 22, 20, 18),
        LFSR(24, 23, 21, 20),
        LFSR(24, 23, 22, 17),
        LFSR(25, 24, 23, 22),
        LFSR(26, 6, 2, 1),
        LFSR(26, 25, 24, 20),
        LFSR(27, 5, 2, 1),
        LFSR(27, 26, 25, 22),
        LFSR(28, 27, 24, 22),
        LFSR(29, 28, 27, 25),
        LFSR(30, 6, 4, 1),
        LFSR(30, 29, 26, 24),
        LFSR(31, 30, 29, 28),
        LFSR(32, 22, 2, 1),
        LFSR(32, 30, 26, 25),
        LFSR(33, 32, 29, 27),
        LFSR(34, 27, 2, 1),
        LFSR(34, 31, 30, 26),
        LFSR(35, 34, 28, 27),
        LFSR(36, 35, 29, 28),
        LFSR(37, 36, 33, 31),
        LFSR(38, 6, 5, 1),
        LFSR(38, 37, 33, 32),
        LFSR(39, 38, 35, 32),
        LFSR(40, 37, 36, 35),
        LFSR(40, 38, 21, 19),
        LFSR(41, 40, 39, 38),
        LFSR(42, 40, 37, 35),
        LFSR(42, 41, 20, 19),
        LFSR(43, 42, 38, 37),
        LFSR(44, 42, 39, 38),
        LFSR(44, 43, 18, 17),
        LFSR(45, 44, 42, 41),
        LFSR(46, 40, 39, 38),
        LFSR(46, 45, 26, 25),
        LFSR(47, 46, 43, 42),
        LFSR(48, 44, 41, 39),
        LFSR(48, 47, 21, 20),
        LFSR(49, 45, 44, 43),
        LFSR(50, 48, 47, 46),
        LFSR(50, 49, 24, 23),
        LFSR(51, 50, 36, 35),
        LFSR(51, 50, 48, 45),
        LFSR(52, 51, 49, 46),
        LFSR(53, 52, 38, 37),
        LFSR(53, 52, 51, 47),
        LFSR(54, 51, 48, 46),
        LFSR(54, 53, 18, 17),
        LFSR(55, 54, 53, 49),
        LFSR(56, 54, 52, 49),
        LFSR(56, 55, 35, 34),
        LFSR(57, 55, 54, 52),
        LFSR(58, 57, 53, 52),
        LFSR(59, 57, 55, 52),
        LFSR(59, 58, 38, 37),
        LFSR(60, 58, 56, 55),
        LFSR(61, 60, 46, 45),
        LFSR(61, 60, 59, 56),
        LFSR(62, 59, 57, 56),
        LFSR(62, 61, 6, 5),
        LFSR(63, 62, 59, 58),
        LFSR(64, 63, 61, 60),
        LFSR(65, 64, 62, 61),
        LFSR(66, 60, 58, 57),
        LFSR(66, 65, 57, 56),
        LFSR(67, 66, 58, 57),
        LFSR(67, 66, 65, 62),
        LFSR(68, 67, 63, 61),
        LFSR(69, 67, 42, 40),
        LFSR(69, 67, 64, 63),
        LFSR(70, 69, 55, 54),
        LFSR(70, 69, 67, 65),
        LFSR(71, 70, 68, 66),
        LFSR(72, 66, 25, 19),
        LFSR(72, 69, 63, 62),
        LFSR(73, 71, 70, 69),
        LFSR(74, 71, 70, 67),
        LFSR(74, 73, 59, 58),
        LFSR(75, 74, 65, 64),
        LFSR(75, 74, 72, 69),
        LFSR(76, 74, 72, 71),
        LFSR(76, 75, 41, 40),
        LFSR(77, 75, 72, 71),
        LFSR(77, 76, 47, 46),
        LFSR(78, 77, 59, 58),
        LFSR(78, 77, 76, 71),
        LFSR(79, 77, 76, 75),
        LFSR(80, 78, 76, 71),
        LFSR(80, 79, 43, 42),
        LFSR(81, 79, 78, 75),
        LFSR(82, 78, 76, 73),
        LFSR(82, 79, 47, 44),
        LFSR(83, 81, 79, 76),
        LFSR(83, 82, 38, 37),
        LFSR(84, 83, 77, 75),
        LFSR(85, 84, 58, 57),
        LFSR(85, 84, 83, 77),
        LFSR(86, 84, 81, 80),
        LFSR(86, 85, 74, 73),
        LFSR(87, 86, 82, 80),
        LFSR(88, 80, 79, 77),
        LFSR(88, 87, 17, 16),
        LFSR(89, 86, 84, 83),
        LFSR(90, 88, 87, 85),
        LFSR(90, 89, 72, 71),
        LFSR(91, 90, 8, 7),
        LFSR(91, 90, 86, 83),
        LFSR(92, 90, 87, 86),
        LFSR(92, 91, 80, 79),
        LFSR(93, 91, 90, 87),
        LFSR(94, 93, 89, 88),
        LFSR(95, 94, 90, 88),
        LFSR(96, 90, 87, 86),
        LFSR(96, 94, 49, 47),
        LFSR(97, 95, 93, 91),
        LFSR(98, 97, 91, 90),
        LFSR(99, 95, 94, 92),
        LFSR(99, 97, 54, 52),
        LFSR(100, 98, 93, 92),
        LFSR(101, 100, 95, 94),
        LFSR(102, 99, 97, 96),
        LFSR(102, 101, 36, 35),
        LFSR(103, 102, 99, 94),
        LFSR(104, 103, 94, 93),
        LFSR(105, 104, 99, 98),
        LFSR(106, 105, 101, 100),
        LFSR(107, 105, 44, 42),
        LFSR(107, 105, 99, 98),
        LFSR(108, 103, 97, 96),
        LFSR(109, 107, 105, 104),
        LFSR(109, 108, 103, 102),
        LFSR(110, 109, 98, 97),
        LFSR(110, 109, 106, 104),
        LFSR(111, 109, 107, 104),
        LFSR(112, 108, 106, 101),
        LFSR(112, 110, 69, 67),
        LFSR(113, 111, 110, 108),
        LFSR(114, 113, 33, 32),
        LFSR(114, 113, 112, 103),
        LFSR(115, 110, 108, 107),
        LFSR(115, 114, 101, 100),
        LFSR(116, 114, 111, 110),
        LFSR(116, 115, 46, 45),
        LFSR(117, 115, 99, 97),
        LFSR(117, 116, 115, 112),
        LFSR(118, 116, 113, 112),
        LFSR(119, 116, 111, 110),
        LFSR(120, 113, 9, 2),
        LFSR(120, 118, 114, 111),
        LFSR(121, 120, 116, 113),
        LFSR(122, 121, 63, 62),
        LFSR(122, 121, 120, 116),
        LFSR(123, 122, 119, 115),
        LFSR(124, 119, 118, 117),
        LFSR(125, 120, 119, 118),
        LFSR(125, 124, 18, 17),
        LFSR(126, 124, 122, 119),
        LFSR(126, 125, 90, 89),
        LFSR(127, 126, 124, 120),
        LFSR(128, 126, 101, 99),
        LFSR(128, 127, 126, 121),
        LFSR(129, 128, 125, 124),
        LFSR(130, 129, 128, 125),
        LFSR(131, 129, 128, 123),
        LFSR(131, 130, 84, 83),
        LFSR(132, 130, 127, 123),
        LFSR(133, 131, 125, 124),
        LFSR(133, 132, 82, 81),
        LFSR(134, 133, 129, 127),
        LFSR(135, 132, 131, 129),
        LFSR(136, 134, 133, 128),
        LFSR(136, 135, 11, 10),
        LFSR(137, 136, 133, 126),
        LFSR(138, 137, 131, 130),
        LFSR(139, 136, 134, 131),
        LFSR(140, 139, 136, 132),
        LFSR(141, 140, 110, 109),
        LFSR(141, 140, 135, 128),
        LFSR(142, 141, 139, 132),
        LFSR(143, 141, 140, 138),
        LFSR(143, 142, 123, 122),
        LFSR(144, 142, 140, 137),
        LFSR(144, 143, 75, 74),
        LFSR(145, 144, 140, 139),
        LFSR(146, 144, 143, 141),
        LFSR(146, 145, 87, 86),
        LFSR(147, 145, 143, 136),
        LFSR(147, 146, 110, 109),
        LFSR(148, 145, 143, 141),
        LFSR(149, 142, 140, 139),
        LFSR(149, 148, 40, 39),
        LFSR(150, 148, 147, 142),
        LFSR(151, 150, 149, 148),
        LFSR(152, 150, 149, 146),
        LFSR(152, 151, 87, 86),
        LFSR(153, 149, 148, 145),
        LFSR(154, 152, 27, 25),
        LFSR(154, 153, 149, 145),
        LFSR(155, 151, 150, 148),
        LFSR(155, 154, 124, 123),
        LFSR(156, 153, 151, 147),
        LFSR(156, 155, 41, 40),
        LFSR(157, 155, 152, 151),
        LFSR(157, 156, 131, 130),
        LFSR(158, 153, 152, 150),
        LFSR(158, 157, 132, 131),
        LFSR(159, 156, 153, 148),
        LFSR(160, 158, 157, 155),
        LFSR(160, 159, 142, 141),
        LFSR(161, 159, 158, 155),
        LFSR(162, 158, 155, 154),
        LFSR(162, 161, 75, 74),
        LFSR(163, 160, 157, 156),
        LFSR(163, 162, 104, 103),
        LFSR(164, 159, 158, 152),
        LFSR(164, 163, 151, 150),
        LFSR(165, 162, 157, 156),
        LFSR(165, 164, 135, 134),
        LFSR(166, 164, 163, 156),
        LFSR(166, 165, 128, 127),
        LFSR(167, 165, 163, 161),
        LFSR(168, 162, 159, 152),
        LFSR(168, 166, 153, 151),
        LFSR(169, 164, 163, 161),
        LFSR(170, 169, 166, 161),
        LFSR(171, 169, 166, 165),
        LFSR(172, 169, 165, 161),
        LFSR(173, 171, 168, 165),
        LFSR(174, 169, 166, 165),
        LFSR(175, 173, 171, 169),
        LFSR(176, 167, 165, 164),
        LFSR(177, 175, 174, 172),
        LFSR(178, 176, 171, 170),
        LFSR(179, 178, 177, 175),
        LFSR(180, 173, 170, 168),
        LFSR(181, 180, 175, 174),
        LFSR(182, 181, 176, 174),
        LFSR(183, 179, 176, 175),
        LFSR(184, 177, 176, 175),
        LFSR(185, 184, 182, 177),
        LFSR(186, 180, 178, 177),
        LFSR(187, 182, 181, 180),
        LFSR(188, 186, 183, 182),
        LFSR(189, 187, 184, 183),
        LFSR(190, 188, 184, 177),
        LFSR(191, 187, 185, 184),
        LFSR(192, 190, 178, 177),
        LFSR(193, 189, 186, 184),
        LFSR(194, 192, 191, 190),
        LFSR(195, 193, 192, 187),
        LFSR(196, 194, 187, 185),
        LFSR(197, 195, 193, 188),
        LFSR(198, 193, 190, 183),
        LFSR(199, 198, 195, 190),
        LFSR(200, 198, 197, 195),
        LFSR(201, 199, 198, 195),
        LFSR(202, 198, 196, 195),
        LFSR(203, 202, 196, 195),
        LFSR(204, 201, 200, 194),
        LFSR(205, 203, 200, 196),
        LFSR(206, 201, 197, 196),
        LFSR(207, 206, 201, 198),
        LFSR(208, 207, 205, 199),
        LFSR(209, 207, 206, 204),
        LFSR(210, 207, 206, 198),
        LFSR(211, 203, 201, 200),
        LFSR(212, 209, 208, 205),
        LFSR(213, 211, 208, 207),
        LFSR(214, 213, 211, 209),
        LFSR(215, 212, 210, 209),
        LFSR(216, 215, 213, 209),
        LFSR(217, 213, 212, 211),
        LFSR(218, 217, 211, 210),
        LFSR(219, 218, 215, 211),
        LFSR(220, 211, 210, 208),
        LFSR(221, 219, 215, 213),
        LFSR(222, 220, 217, 214),
        LFSR(223, 221, 219, 218),
        LFSR(224, 222, 217, 212),
        LFSR(225, 224, 220, 215),
        LFSR(226, 223, 219, 216),
        LFSR(227, 223, 218, 217),
        LFSR(228, 226, 217, 216),
        LFSR(229, 228, 225, 219),
        LFSR(230, 224, 223, 222),
        LFSR(231, 229, 227, 224),
        LFSR(232, 228, 223, 221),
        LFSR(233, 232, 229, 224),
        LFSR(234, 232, 225, 223),
        LFSR(235, 234, 229, 226),
        LFSR(236, 229, 228, 226),
        LFSR(237, 236, 233, 230),
        LFSR(238, 237, 236, 233),
        LFSR(239, 238, 232, 227),
        LFSR(240, 237, 235, 232),
        LFSR(241, 237, 233, 232),
        LFSR(242, 241, 236, 231),
        LFSR(243, 242, 238, 235),
        LFSR(244, 243, 240, 235),
        LFSR(245, 244, 241, 239),
        LFSR(246, 245, 244, 235),
        LFSR(247, 245, 243, 238),
        LFSR(248, 238, 234, 233),
        LFSR(249, 248, 245, 242),
        LFSR(250, 247, 245, 240),
        LFSR(251, 249, 247, 244),
        LFSR(252, 251, 247, 241),
        LFSR(253, 252, 247, 246),
        LFSR(254, 253, 252, 247),
        LFSR(255, 253, 252, 250),
        LFSR(256, 254, 251, 246),
        LFSR(257, 255, 251, 250),
        LFSR(258, 254, 252, 249),
        LFSR(259, 257, 253, 249),
        LFSR(260, 253, 252, 250),
        LFSR(261, 257, 255, 254),
        LFSR(262, 258, 254, 253),
        LFSR(263, 261, 258, 252),
        LFSR(264, 263, 255, 254),
        LFSR(265, 263, 262, 260),
        LFSR(266, 265, 260, 259),
        LFSR(267, 264, 261, 259),
        LFSR(268, 267, 264, 258),
        LFSR(269, 268, 263, 262),
        LFSR(270, 267, 263, 260),
        LFSR(271, 265, 264, 260),
        LFSR(272, 270, 266, 263),
        LFSR(273, 272, 271, 266),
        LFSR(274, 272, 267, 265),
        LFSR(275, 266, 265, 264),
        LFSR(276, 275, 273, 270),
        LFSR(277, 274, 271, 265),
        LFSR(278, 277, 274, 273),
        LFSR(279, 278, 275, 274),
        LFSR(280, 278, 275, 271),
        LFSR(281, 280, 277, 272),
        LFSR(282, 278, 277, 272),
        LFSR(283, 278, 276, 271),
        LFSR(284, 279, 278, 276),
        LFSR(285, 280, 278, 275),
        LFSR(286, 285, 276, 271),
        LFSR(287, 285, 282, 281),
        LFSR(288, 287, 278, 277),
        LFSR(289, 286, 285, 277),
        LFSR(290, 288, 287, 285),
        LFSR(291, 286, 280, 279),
        LFSR(292, 291, 289, 285),
        LFSR(293, 292, 287, 282),
        LFSR(294, 292, 291, 285),
        LFSR(295, 293, 291, 290),
        LFSR(296, 292, 287, 285),
        LFSR(297, 296, 293, 292),
        LFSR(298, 294, 290, 287),
        LFSR(299, 295, 293, 288),
        LFSR(300, 290, 288, 287),
        LFSR(301, 299, 296, 292),
        LFSR(302, 297, 293, 290),
        LFSR(303, 297, 291, 290),
        LFSR(304, 303, 302, 293),
        LFSR(305, 303, 299, 298),
        LFSR(306, 305, 303, 299),
        LFSR(307, 305, 303, 299),
        LFSR(308, 306, 299, 293),
        LFSR(309, 307, 302, 299),
        LFSR(310, 309, 305, 302),
        LFSR(311, 308, 306, 304),
        LFSR(312, 307, 302, 301),
        LFSR(313, 312, 310, 306),
        LFSR(314, 311, 305, 300),
        LFSR(315, 314, 306, 305),
        LFSR(316, 309, 305, 304),
        LFSR(317, 315, 313, 310),
        LFSR(318, 313, 312, 310),
        LFSR(319, 318, 317, 308),
        LFSR(320, 319, 317, 316),
        LFSR(321, 319, 316, 314),
        LFSR(322, 321, 320, 305),
        LFSR(323, 322, 320, 313),
        LFSR(324, 321, 320, 318),
        LFSR(325, 323, 320, 315),
        LFSR(326, 325, 323, 316),
        LFSR(327, 325, 322, 319),
        LFSR(328, 323, 321, 319),
        LFSR(329, 326, 323, 321),
        LFSR(330, 328, 323, 322),
        LFSR(331, 329, 325, 321),
        LFSR(332, 325, 321, 320),
        LFSR(333, 331, 329, 325),
        LFSR(334, 333, 330, 327),
        LFSR(335, 333, 328, 325),
        LFSR(336, 335, 332, 329),
        LFSR(337, 336, 331, 327),
        LFSR(338, 336, 335, 332),
        LFSR(339, 332, 329, 323),
        LFSR(340, 337, 336, 329),
        LFSR(341, 336, 330, 327),
        LFSR(342, 341, 340, 331),
        LFSR(343, 338, 335, 333),
        LFSR(344, 338, 334, 333),
        LFSR(345, 343, 341, 337),
        LFSR(346, 344, 339, 335),
        LFSR(347, 344, 337, 336),
        LFSR(348, 344, 341, 340),
        LFSR(349, 347, 344, 343),
        LFSR(350, 340, 337, 336),
        LFSR(351, 348, 345, 343),
        LFSR(352, 346, 341, 339),
        LFSR(353, 349, 346, 344),
        LFSR(354, 349, 341, 340),
        LFSR(355, 354, 350, 349),
        LFSR(356, 349, 347, 346),
        LFSR(357, 355, 347, 346),
        LFSR(358, 351, 350, 344),
        LFSR(359, 358, 352, 350),
        LFSR(360, 359, 335, 334),
        LFSR(361, 360, 357, 354),
        LFSR(362, 360, 351, 344),
        LFSR(363, 362, 356, 355),
        LFSR(364, 363, 359, 352),
        LFSR(365, 360, 359, 356),
        LFSR(366, 362, 359, 352),
        LFSR(367, 365, 363, 358),
        LFSR(368, 361, 359, 351),
        LFSR(369, 367, 359, 358),
        LFSR(370, 368, 367, 365),
        LFSR(371, 369, 368, 363),
        LFSR(372, 369, 365, 357),
        LFSR(373, 371, 366, 365),
        LFSR(374, 369, 368, 366),
        LFSR(375, 374, 368, 367),
        LFSR(376, 371, 369, 368),
        LFSR(377, 376, 374, 369),
        LFSR(378, 374, 365, 363),
        LFSR(379, 375, 370, 369),
        LFSR(380, 377, 374, 366),
        LFSR(381, 380, 379, 376),
        LFSR(382, 379, 375, 364),
        LFSR(383, 382, 378, 374),
        LFSR(384, 378, 369, 368),
        LFSR(385, 383, 381, 379),
        LFSR(386, 381, 380, 376),
        LFSR(387, 385, 379, 378),
        LFSR(388, 387, 385, 374),
        LFSR(389, 384, 380, 379),
        LFSR(390, 388, 380, 377),
        LFSR(391, 390, 389, 385),
        LFSR(392, 386, 382, 379),
        LFSR(393, 392, 391, 386),
        LFSR(394, 392, 387, 386),
        LFSR(395, 390, 389, 384),
        LFSR(396, 392, 390, 389),
        LFSR(397, 392, 387, 385),
        LFSR(398, 393, 392, 384),
        LFSR(399, 397, 390, 388),
        LFSR(400, 398, 397, 395),
        LFSR(401, 399, 392, 389),
        LFSR(402, 399, 398, 393),
        LFSR(403, 398, 395, 394),
        LFSR(404, 400, 398, 397),
        LFSR(405, 398, 397, 388),
        LFSR(406, 402, 397, 393),
        LFSR(407, 402, 400, 398),
        LFSR(408, 407, 403, 401),
        LFSR(409, 406, 404, 402),
        LFSR(410, 407, 406, 400),
        LFSR(411, 408, 401, 399),
        LFSR(412, 409, 404, 401),
        LFSR(413, 407, 406, 403),
        LFSR(414, 405, 401, 398),
        LFSR(415, 413, 411, 406),
        LFSR(416, 414, 411, 407),
        LFSR(417, 416, 414, 407),
        LFSR(418, 417, 415, 403),
        LFSR(419, 415, 414, 404),
        LFSR(420, 412, 410, 407),
        LFSR(421, 419, 417, 416),
        LFSR(422, 421, 416, 412),
        LFSR(423, 420, 418, 414),
        LFSR(424, 422, 417, 415),
        LFSR(425, 422, 421, 418),
        LFSR(426, 415, 414, 412),
        LFSR(427, 422, 421, 416),
        LFSR(428, 426, 425, 417),
        LFSR(429, 422, 421, 419),
        LFSR(430, 419, 417, 415),
        LFSR(431, 430, 428, 426),
        LFSR(432, 429, 428, 419),
        LFSR(433, 430, 428, 422),
        LFSR(434, 429, 423, 422),
        LFSR(435, 430, 426, 423),
        LFSR(436, 432, 431, 430),
        LFSR(437, 436, 435, 431),
        LFSR(438, 436, 432, 421),
        LFSR(439, 437, 436, 431),
        LFSR(440, 439, 437, 436),
        LFSR(441, 440, 433, 430),
        LFSR(442, 440, 437, 435),
        LFSR(443, 442, 437, 433),
        LFSR(444, 435, 432, 431),
        LFSR(445, 441, 439, 438),
        LFSR(446, 442, 439, 431),
        LFSR(447, 446, 441, 438),
        LFSR(448, 444, 442, 437),
        LFSR(449, 446, 440, 438),
        LFSR(450, 443, 438, 434),
        LFSR(451, 450, 441, 435),
        LFSR(452, 448, 447, 446),
        LFSR(453, 449, 447, 438),
        LFSR(454, 449, 445, 444),
        LFSR(455, 453, 449, 444),
        LFSR(456, 454, 445, 433),
        LFSR(457, 454, 449, 446),
        LFSR(458, 453, 448, 445),
        LFSR(459, 457, 454, 447),
        LFSR(460, 459, 455, 451),
        LFSR(461, 460, 455, 454),
        LFSR(462, 457, 451, 450),
        LFSR(463, 456, 455, 452),
        LFSR(464, 460, 455, 441),
        LFSR(465, 463, 462, 457),
        LFSR(466, 460, 455, 452),
        LFSR(467, 466, 461, 456),
        LFSR(468, 464, 459, 453),
        LFSR(469, 467, 464, 460),
        LFSR(470, 468, 462, 461),
        LFSR(471, 469, 468, 465),
        LFSR(472, 470, 469, 461),
        LFSR(473, 470, 467, 465),
        LFSR(474, 465, 463, 456),
        LFSR(475, 471, 467, 466),
        LFSR(476, 475, 468, 466),
        LFSR(477, 470, 462, 461),
        LFSR(478, 477, 474, 472),
        LFSR(479, 475, 472, 470),
        LFSR(480, 473, 467, 464),
        LFSR(481, 480, 472, 471),
        LFSR(482, 477, 476, 473),
        LFSR(483, 479, 477, 474),
        LFSR(484, 483, 482, 470),
        LFSR(485, 479, 469, 468),
        LFSR(486, 481, 478, 472),
        LFSR(487, 485, 483, 478),
        LFSR(488, 487, 485, 484),
        LFSR(489, 484, 483, 480),
        LFSR(490, 485, 483, 481),
        LFSR(491, 488, 485, 480),
        LFSR(492, 491, 485, 484),
        LFSR(493, 490, 488, 483),
        LFSR(494, 493, 489, 481),
        LFSR(495, 494, 486, 480),
        LFSR(496, 494, 491, 480),
        LFSR(497, 493, 488, 486),
        LFSR(498, 495, 489, 487),
        LFSR(499, 494, 493, 488),
        LFSR(500, 499, 494, 490),
        LFSR(501, 499, 497, 496),
        LFSR(502, 498, 497, 494),
        LFSR(503, 502, 501, 500),
        LFSR(504, 502, 490, 483),
        LFSR(505, 500, 497, 493),
        LFSR(506, 501, 494, 491),
        LFSR(507, 504, 501, 494),
        LFSR(508, 505, 500, 495),
        LFSR(509, 506, 502, 501),
        LFSR(510, 501, 500, 498),
        LFSR(511, 509, 503, 501),
        LFSR(512, 510, 507, 504),
        LFSR(513, 505, 503, 500),
        LFSR(514, 511, 509, 507),
        LFSR(515, 511, 508, 501),
        LFSR(516, 514, 511, 509),
        LFSR(517, 515, 507, 505),
        LFSR(518, 516, 515, 507),
        LFSR(519, 517, 511, 507),
        LFSR(520, 509, 507, 503),
        LFSR(521, 519, 514, 512),
        LFSR(522, 518, 509, 507),
        LFSR(523, 521, 517, 510),
        LFSR(524, 523, 519, 515),
        LFSR(525, 524, 521, 519),
        LFSR(526, 525, 521, 517),
        LFSR(527, 526, 520, 518),
        LFSR(528, 526, 522, 517),
        LFSR(529, 528, 525, 522),
        LFSR(530, 527, 523, 520),
        LFSR(531, 529, 525, 519),
        LFSR(532, 529, 528, 522),
        LFSR(533, 531, 530, 529),
        LFSR(534, 533, 529, 527),
        LFSR(535, 533, 529, 527),
        LFSR(536, 533, 531, 529),
        LFSR(537, 536, 535, 527),
        LFSR(538, 537, 536, 533),
        LFSR(539, 535, 534, 529),
        LFSR(540, 537, 534, 529),
        LFSR(541, 537, 531, 528),
        LFSR(542, 540, 539, 533),
        LFSR(543, 538, 536, 532),
        LFSR(544, 538, 535, 531),
        LFSR(545, 539, 537, 532),
        LFSR(546, 545, 544, 538),
        LFSR(547, 543, 540, 534),
        LFSR(548, 545, 543, 538),
        LFSR(549, 546, 545, 533),
        LFSR(550, 546, 533, 529),
        LFSR(551, 550, 547, 542),
        LFSR(552, 550, 547, 532),
        LFSR(553, 550, 549, 542),
        LFSR(554, 551, 546, 543),
        LFSR(555, 551, 546, 545),
        LFSR(556, 549, 546, 540),
        LFSR(557, 552, 551, 550),
        LFSR(558, 553, 549, 544),
        LFSR(559, 557, 552, 550),
        LFSR(560, 554, 551, 549),
        LFSR(561, 558, 552, 550),
        LFSR(562, 560, 558, 551),
        LFSR(563, 561, 554, 549),
        LFSR(564, 563, 561, 558),
        LFSR(565, 564, 559, 554),
        LFSR(566, 564, 561, 560),
        LFSR(567, 563, 557, 556),
        LFSR(568, 558, 557, 551),
        LFSR(569, 568, 559, 557),
        LFSR(570, 563, 558, 552),
        LFSR(571, 569, 566, 561),
        LFSR(572, 571, 564, 560),
        LFSR(573, 569, 567, 563),
        LFSR(574, 569, 565, 560),
        LFSR(575, 572, 570, 569),
        LFSR(576, 573, 572, 563),
        LFSR(577, 575, 574, 569),
        LFSR(578, 562, 556, 555),
        LFSR(579, 572, 570, 567),
        LFSR(580, 579, 576, 574),
        LFSR(581, 575, 574, 568),
        LFSR(582, 579, 576, 571),
        LFSR(583, 581, 577, 575),
        LFSR(584, 581, 571, 570),
        LFSR(585, 583, 582, 577),
        LFSR(586, 584, 581, 579),
        LFSR(587, 586, 581, 576),
        LFSR(588, 577, 572, 571),
        LFSR(589, 586, 585, 579),
        LFSR(590, 588, 587, 578),
        LFSR(591, 587, 585, 582),
        LFSR(592, 591, 573, 568),
        LFSR(593, 588, 585, 584),
        LFSR(594, 586, 584, 583),
        LFSR(595, 594, 593, 586),
        LFSR(596, 592, 591, 590),
        LFSR(597, 588, 585, 583),
        LFSR(598, 597, 592, 591),
        LFSR(599, 593, 591, 590),
        LFSR(600, 599, 590, 589),
        LFSR(601, 600, 597, 589),
        LFSR(602, 596, 594, 591),
        LFSR(603, 600, 599, 597),
        LFSR(604, 600, 598, 589),
        LFSR(605, 600, 598, 595),
        LFSR(606, 602, 599, 591),
        LFSR(607, 600, 598, 595),
        LFSR(608, 606, 602, 585),
        LFSR(609, 601, 600, 597),
        LFSR(610, 602, 600, 599),
        LFSR(611, 609, 607, 601),
        LFSR(612, 607, 602, 598),
        LFSR(613, 609, 603, 594),
        LFSR(614, 613, 612, 607),
        LFSR(615, 614, 609, 608),
        LFSR(616, 614, 602, 597),
        LFSR(617, 612, 608, 607),
        LFSR(618, 615, 604, 598),
        LFSR(619, 614, 611, 610),
        LFSR(620, 619, 618, 611),
        LFSR(621, 616, 615, 609),
        LFSR(622, 612, 610, 605),
        LFSR(623, 614, 613, 612),
        LFSR(624, 617, 615, 612),
        LFSR(625, 620, 617, 613),
        LFSR(626, 623, 621, 613),
        LFSR(627, 622, 617, 613),
        LFSR(628, 626, 617, 616),
        LFSR(629, 627, 624, 623),
        LFSR(630, 628, 626, 623),
        LFSR(631, 625, 623, 617),
        LFSR(632, 629, 619, 613),
        LFSR(633, 632, 631, 626),
        LFSR(634, 631, 629, 627),
        LFSR(635, 631, 625, 621),
        LFSR(636, 632, 628, 623),
        LFSR(637, 636, 628, 623),
        LFSR(638, 637, 633, 632),
        LFSR(639, 636, 635, 629),
        LFSR(640, 638, 637, 626),
        LFSR(641, 640, 636, 622),
        LFSR(642, 636, 633, 632),
        LFSR(643, 641, 640, 632),
        LFSR(644, 634, 633, 632),
        LFSR(645, 641, 637, 634),
        LFSR(646, 635, 634, 633),
        LFSR(647, 646, 643, 642),
        LFSR(648, 647, 626, 625),
        LFSR(649, 648, 644, 638),
        LFSR(650, 644, 635, 632),
        LFSR(651, 646, 638, 637),
        LFSR(652, 647, 643, 641),
        LFSR(653, 646, 645, 643),
        LFSR(654, 649, 643, 640),
        LFSR(655, 653, 639, 638),
        LFSR(656, 646, 638, 637),
        LFSR(657, 656, 650, 649),
        LFSR(658, 651, 648, 646),
        LFSR(659, 657, 655, 644),
        LFSR(660, 657, 656, 648),
        LFSR(661, 657, 650, 649),
        LFSR(662, 659, 656, 650),
        LFSR(663, 655, 652, 649),
        LFSR(664, 662, 660, 649),
        LFSR(665, 661, 659, 654),
        LFSR(666, 664, 659, 656),
        LFSR(667, 664, 660, 649),
        LFSR(668, 658, 656, 651),
        LFSR(669, 667, 665, 664),
        LFSR(670, 669, 665, 664),
        LFSR(671, 669, 665, 662),
        LFSR(672, 667, 666, 661),
        LFSR(673, 666, 664, 663),
        LFSR(674, 671, 665, 660),
        LFSR(675, 674, 672, 669),
        LFSR(676, 675, 671, 664),
        LFSR(677, 674, 673, 669),
        LFSR(678, 675, 673, 663),
        LFSR(679, 676, 667, 661),
        LFSR(680, 679, 650, 645),
        LFSR(681, 678, 672, 670),
        LFSR(682, 681, 679, 675),
        LFSR(683, 682, 677, 672),
        LFSR(684, 681, 671, 666),
        LFSR(685, 684, 682, 681),
        LFSR(686, 684, 674, 673),
        LFSR(687, 682, 675, 673),
        LFSR(688, 682, 674, 669),
        LFSR(689, 686, 683, 681),
        LFSR(690, 687, 683, 680),
        LFSR(691, 689, 685, 678),
        LFSR(692, 687, 686, 678),
        LFSR(693, 691, 685, 678),
        LFSR(694, 691, 681, 677),
        LFSR(695, 694, 691, 686),
        LFSR(696, 694, 686, 673),
        LFSR(697, 689, 685, 681),
        LFSR(698, 690, 689, 688),
        LFSR(699, 698, 689, 684),
        LFSR(700, 698, 695, 694),
        LFSR(701, 699, 697, 685),
        LFSR(702, 701, 699, 695),
        LFSR(703, 702, 696, 691),
        LFSR(704, 701, 699, 692),
        LFSR(705, 704, 698, 697),
        LFSR(706, 697, 695, 692),
        LFSR(707, 702, 699, 692),
        LFSR(708, 706, 704, 703),
        LFSR(709, 708, 706, 705),
        LFSR(710, 709, 696, 695),
        LFSR(711, 704, 703, 700),
        LFSR(712, 709, 708, 707),
        LFSR(713, 706, 703, 696),
        LFSR(714, 709, 707, 701),
        LFSR(715, 714, 711, 708),
        LFSR(716, 706, 705, 704),
        LFSR(717, 716, 710, 701),
        LFSR(718, 717, 716, 713),
        LFSR(719, 711, 710, 707),
        LFSR(720, 718, 712, 709),
        LFSR(721, 720, 713, 712),
        LFSR(722, 721, 718, 707),
        LFSR(723, 717, 710, 707),
        LFSR(724, 719, 716, 711),
        LFSR(725, 720, 719, 716),
        LFSR(726, 725, 722, 721),
        LFSR(727, 721, 719, 716),
        LFSR(728, 726, 725, 724),
        LFSR(729, 726, 724, 718),
        LFSR(730, 726, 715, 711),
        LFSR(731, 729, 725, 723),
        LFSR(732, 729, 728, 725),
        LFSR(733, 731, 726, 725),
        LFSR(734, 724, 721, 720),
        LFSR(735, 733, 728, 727),
        LFSR(736, 730, 728, 723),
        LFSR(737, 736, 733, 732),
        LFSR(738, 730, 729, 727),
        LFSR(739, 731, 723, 721),
        LFSR(740, 737, 728, 716),
        LFSR(741, 738, 733, 732),
        LFSR(742, 741, 738, 730),
        LFSR(743, 742, 731, 730),
        LFSR(744, 743, 733, 731),
        LFSR(745, 740, 738, 737),
        LFSR(746, 738, 733, 728),
        LFSR(747, 743, 741, 737),
        LFSR(748, 744, 743, 733),
        LFSR(749, 748, 743, 742),
        LFSR(750, 746, 741, 734),
        LFSR(751, 750, 748, 740),
        LFSR(752, 749, 732, 731),
        LFSR(753, 748, 745, 740),
        LFSR(754, 742, 740, 735),
        LFSR(755, 754, 745, 743),
        LFSR(756, 755, 747, 740),
        LFSR(757, 756, 751, 750),
        LFSR(758, 757, 746, 741),
        LFSR(759, 757, 756, 750),
        LFSR(760, 757, 747, 734),
        LFSR(761, 760, 759, 758),
        LFSR(762, 761, 755, 745),
        LFSR(763, 754, 749, 747),
        LFSR(764, 761, 759, 758),
        LFSR(765, 760, 755, 754),
        LFSR(766, 757, 747, 744),
        LFSR(767, 763, 760, 759),
        LFSR(768, 764, 751, 749),
        LFSR(769, 763, 762, 760),
        LFSR(770, 768, 765, 756),
        LFSR(771, 765, 756, 754),
        LFSR(772, 767, 766, 764),
        LFSR(773, 767, 765, 763),
        LFSR(774, 767, 760, 758),
        LFSR(775, 771, 769, 768),
        LFSR(776, 773, 764, 759),
        LFSR(777, 776, 767, 761),
        LFSR(778, 775, 762, 759),
        LFSR(779, 776, 771, 769),
        LFSR(780, 775, 772, 764),
        LFSR(781, 779, 765, 764),
        LFSR(782, 780, 779, 773),
        LFSR(783, 782, 776, 773),
        LFSR(784, 778, 775, 771),
        LFSR(785, 780, 776, 775),
        LFSR(786, 782, 780, 771),
        LFSR(1024, 1015, 1002, 1001),
        LFSR(2048, 2035, 2034, 2029),
        LFSR(4096, 4095, 4081, 4069),

        # 6 taps
        # (why the hell did that xilinx sheet list this)
        LFSR(37, 5, 4, 3, 2, 1),
]


bad_periods = {}
lfsrs_by_bits = {}

def _calculate_stuff():
    for tmp in known_lfsrs:
        lfsrs_by_bits.setdefault(tmp.bits, []).append(tmp)
    for k, v in mask_factors.items():
        assert v == sorted(v)
        n = (1<<k)-1
        assert n == product(v)
        v = sorted(set(v))
        assert all([n % e == 0 for e in v])
        bad_periods[k] = [n // e for e in v]
_calculate_stuff()


def lfsr_for_width(bits):
    choices = lfsrs_by_bits[bits]
    if len(choices) == 1:
        return choices[0]
    return random.choice(choices)


def lfsr_iter(bits, *, xnor=False):
    lfsr = lfsr_for_width(bits)
    initial = random.randint(1, lfsr.full_mask) - xnor

    state = initial
    while True:
        yield state
        state = lfsr(state, xnor=xnor)
        if state == initial:
            return


def test():
    for width in range(2, 64+1):
        for lfsr in lfsrs_by_bits[width]:
            lfsr.verify()
        print('OK:', width)


def main():
    print('demo0:', *lfsr_iter(4, xnor=False))
    print('demo1:', *lfsr_iter(4, xnor=True))
    print()
    print('verifying ...')
    test()


if __name__ == '__main__':
    main()