nikeshbajaj / linear_feedback_shift_register Goto Github PK

Looks like self.seq starts off as a numpy.int32 and not a list like info() expects.

Steps to reproduce:

import pylfsr
l = pylfsr.LFSR(fpoly=[8,7,5,3])
l.next()
l.info()

8 bit LFSR with feedback polynomial  x^8 + x^7 + x^5 + x^3 + 1
Expected Period (if polynomial is primitive) =  255
Current :
 State        :  [0 1 1 1 1 1 1 1]
 Count        :  1
 Output bit   :  1
 feedback bit :  0
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-4-91f548e48c86> in <module>
----> 1 l.info()

c:\python37\lib\site-packages\pylfsr\pylfsr.py in info(self)
    247                 print(' feedback bit : ', self.feedbackbit)
    248                 if self.count > 0 and self.count < 1000:
--> 249                         print(' Output Sequence %s' % (''.join([str(int(x)) for x in self.seq])))
    250
    251         def check(self):

The speed of the functions can be considerably increased by a few changes.
I have looked especially at LFSRv3.m
In the original version a 20 Bit register with taps at 20 &17 (cycle length: 1048575) took
1.39 s for N=50000, 9.5 s for N=100000 , 46.2 s for N=200000 and 108.5 s for N=300000.
A major speed increase can be achieved by initializing seq to the required size in the function body before first use, e.g. by seq=zeros(N,1); .
This avoids time consuming memory re-allocations for the otherwise increasing size of seq within the for-loop.
Furthermore some index expressions can calculated in advance before loop execution because they are never changed.
Many LFSRs only need two taps. For this case further simplifications are possible.
In the latter case my modified version took
1.28 s for N=200000, 1.89 s for N=300000, 3.15 s for N=500000 and 6.25 s for N=1000000 .
Modified LFSRv3 body :

n=length(s);
m=length(t);
m1=m-1;
m2=m-2;
seq=zeros(N,1);
seq(1) = s(n);
j=1:n-1;
n1=n+1;
n1j=n1-j;
nj=n-j;
for k=2:N;
    b(1)=xor(s(t(1)), s(t(2)));
    if m>2;
        for i=1:m2;
        b(i+1)=xor(s(t(i+2)), b(i));
        end
    end
    s(n1j)=s(nj);
    s(1)=b(m1);
    seq(k)=s(n);
end

Special version of the function body for LFSRs with 2 taps :

n=length(s);
seq=zeros(N,1);
seq(1) = s(n);
j=1:n-1;  % e.g. 1:19 for n=20
n1=n+1;   %      21
n1j=n1-j; %      20:-1:2
nj=n-j;   %      19:-1:1
for k=2:N;
    b=xor(s(t(1)), s(t(2)));
    s(n1j)=s(nj);
    s(1)=b;
    seq(k)=s(n);
end

It's more common in computer scene compare with Fibonacci.

I've used this library to answer this question in cryptography.se. During my implementation, I've seen that the first output is -1. This creates inconsistency or extra code to mitigate.

This is very unusual, at least for me. The output should be the last cell of the LFSR, not -1. The easiest solution should be setting the output immediately.

          I agree. There is a faster version of matlab file available too.

Check function seq = LFSRv3(s,t,N)

Your idea of initializing for fix memory is good too.

To even faster, try python version, that is faster.

Originally posted by @Nikeshbajaj in #10 (comment)