<jupyter_start><jupyter_text>LFSR in SageWe may generate a keystream using the `lfsr_sequence` function, which takes as input the key (characteristic polynomial coefficients) and the initial state as vectors over a finite field, and the length of the keystream to be generated.<jupyter_code>F = GF(2)
one = F.one()
key = [x*one for x in [1, 1, 1, 1]]
fill = [x*one for x in [0, 0, 0, 1]]
lfsr_sequence(key, fill, 20)<jupyter_output><empty_output><jupyter_text>Let us determine the periods of the LFSR.<jupyter_code>def period(s, n):
    try:
        return next(i for i in range(1, len(s)) if s[i:i+n] == s[:n])
    except StopIteration:
        return None

def periods(key, lfsr=lfsr_sequence):
    F = key[0].parent()
    q = len(F)
    n = len(key)
    seen = []
    periods = {}
    l = q^n
    for fill in F^n:
        s = ''.join(str(x) for x in fill)
        if any(s in ss for ss in seen):
            continue
        seq = list(lfsr(list(key), list(fill), l+n))
        p = period(seq, n)
        periods[tuple(fill)] = p
        l -= p
        seen.append(''.join(str(x) for x in seq))
    return periods
periods(key)<jupyter_output><empty_output><jupyter_text>We observe that all nonzero states give a sequence of period 5. Let us verify that the connection polynomial $C(z)$ is irreducible and divides $z^5 - 1$.<jupyter_code>P.<z> = PolynomialRing(F)
C = -1 + sum(a*z^i for i, a in enumerate(reversed(key), 1))
C.factor()
(z^5 - 1) / C<jupyter_output><empty_output><jupyter_text>Let us now consider a LFSR with the same recursion, only over a field of size 5.<jupyter_code>F = GF(5)
one = F.one()
key = [x*one for x in [1, 1, 1, 1]]
periods(key)<jupyter_output><empty_output><jupyter_text>We observe that all nonzero states give a sequence of period 312. Let us verify that the connection polynomial $C(z)$ is irreducible and divides $z^{312} - 1$.<jupyter_code>P.<z> = PolynomialRing(F)
C = -1 + sum(a*z^i for i, a in enumerate(reversed(key), 1))
C.factor()
(z^312 - 1) / C<jupyter_output><empty_output><jupyter_text>`lfsr_sequence` only works with finite fields. We provide the function `lfsr_ring` which also lets us use ring elements.<jupyter_code>def lfsr_ring(key, fill, n=-1):
    m = len(key)
    assert m == len(fill)
    i = 0
    for x in fill:
        yield x
        i += 1
        if i == n:
            return
    while i != n:
        x = sum([key[j] * fill[j] for j in range(m)])
        fill = fill[1:] + [x]
        yield x
        i += 1
R = Integers(10)
one = R.one()
key = [x*one for x in [1, 1, 1, 1]]
fill = [x*one for x in [0, 0, 0, 1]]
gen = lfsr_ring(key, fill)
seq = [next(gen) for _ in range(10000)]
print(seq[:100])<jupyter_output>[0, 0, 0, 1, 1, 2, 4, 8, 5, 9, 6, 8, 8, 1, 3, 0, 2, 6, 1, 9, 8, 4, 2, 3, 7, 6, 8, 4, 5, 3, 0, 2, 0, 5, 7, 4, 6, 2, 9, 1, 8, 0, 8, 7, 3, 8, 6, 4, 1, 9, 0, 4, 4, 7, 5, 0, 6, 8, 9, 3, 6, 6, 4, 9, 5, 4, 2, 0, 1, 7, 0, 8, 6, 1, 5, 0, 2, 8, 5, 5, 0, 8, 8, 1, 7, 4, 0, 2, 3, 9, 4, 8, 4, 5, 1, 8, 8, 2, 9, 7]<jupyter_text>Let us determine the period of a sequence.<jupyter_code>period(seq, 4)
1560 / 5<jupyter_output><empty_output><jupyter_text>We see that the period of the sequence is the least common multiple of the periods appearing with the fields of sizes 2 and 5, which are prime factors of 10. In fact, every period will be obtained in this manner.<jupyter_code>periods(key, lfsr_ring)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14652122641509435, 'fraction_numerical': 0.05070754716981132, 'mean_word_length': 3.3444302176696543, 'pattern_counts': {'":': 0, '<': 34, '<?xml version=': 0, '>': 34, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '551319', 'license': 'MIT', 'n_tokens_mistral': 1496, 'n_tokens_neox': 1320, 'n_words': 482, 'path': 'notebooks/LFSR.ipynb', 'repo_name': 'tp4348/kirv', 'size': '3392'}