Finding the initial state of LFSR from partial known sequence

Question

Is there a faster way (or even possible) to find the initial state of m-bit LFSR, if I know the part of the generated sequence?

Example: Given m=16, feedback polynomial as x^16 + x^12 + x^3 + x^1 + 1 and part of sequence is '0010100010000110010011100011100100001000110111000000011010001001100101110101001100000011111010111000100001101011101011011011101111110000000001111111010010110100001011000101011111100110101010001110000000'

Can we even find out what was the initial state of the LFSR? if we can, what is the minimum length of known sequence requred?

The example above has all ones as initial state and is generate using as follow:

import pylfsr
L1 = pylfsr.LFSR(fpoly=[16,12,3,1], initstate='ones')
seq = L1.runKCycle(2**16)
seq = L1.arr2str(seq)

Expecting: I am expecting anyone, who know how to write a program and code to get the initial state

Answer 1

In principle this is possible. See: https://en.wikipedia.org/wiki/Berlekamp–Massey_algorithm (For a bit more background see also: https://crypto.stackexchange.com/questions/16203/berlekamp-massey-to-construct-minimal-lfsr)

In Python, you could also set up the appropriate system of linear equations, based on the observed bits, and then use a package like z3-solver to try to solve them.

Here is one way to do it, using both pylfsr for the initial "secret" setup and class LFSR as implemented in https://github.com/thewhiteninja/lfsr-berlekamp-massey. Note that the BerlekampMassey class does not know about your polynomial. If you have that information then it should be easier to reconstruct the initial state (or a possible state that generates the same sequences as the original initial state).

import pylfsr

L1 = pylfsr.LFSR(fpoly=[16,12,3,1], initstate="ones")
print("Initial state:", L1.initstate)
    
seq = L1.runKCycle(2**16)
bits = L1.arr2str(seq)
print("Bits:", bits[:256], "...")
    
bm = BerlekampMassey(bytes_to_bin(bits[:17]))
poly2 = LFSR(bm.get_polynomial(), 
             bytes_to_bin(bits)[:bm.get_polynomial_degree()])
    
bits = "".join([chr(poly2.next_byte()) for _ in range(16)])
print("LFSR initialstate    :", bits)

If the initial state is all ones, then in this case you only need 17 bits, apparently. If it is random, you may need more observed bits. I don't know how many.