#!/usr/bin/env python
# coding: utf-8

# # LFSR in Sage
# 
# We 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.

# In[1]:


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]]


# In[2]:


lfsr_sequence(key, fill, 20)


# Let us determine the periods of the LFSR.

# In[3]:


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


# In[4]:


periods(key)


# 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$.

# In[5]:


P.<z> = PolynomialRing(F)
C = -1 + sum(a*z^i for i, a in enumerate(reversed(key), 1))


# In[6]:


C.factor()


# In[7]:


(z^5 - 1) / C


# Let us now consider a LFSR with the same recursion, only over a field of size 5.

# In[8]:


F = GF(5)
one = F.one()
key = [x*one for x in [1, 1, 1, 1]]


# In[9]:


periods(key)


# 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$.

# In[10]:


P.<z> = PolynomialRing(F)
C = -1 + sum(a*z^i for i, a in enumerate(reversed(key), 1))


# In[11]:


C.factor()


# In[12]:


(z^312 - 1) / C


# `lfsr_sequence` only works with finite fields. We provide the function `lfsr_ring` which also lets us use ring elements.

# In[13]:


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


# In[14]:


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]]


# In[15]:


gen = lfsr_ring(key, fill)
seq = [next(gen) for _ in range(10000)]
print(seq[:100])


# Let us determine the period of a sequence.

# In[16]:


period(seq, 4)


# In[17]:


1560 / 5


# 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.

# In[18]:


periods(key, lfsr_ring)