Berlekamp-Massey algorithm is an algorithm that will find the shortest linear feedback shift register (LFSR) for a given binary output sequence. Here we present a web-based implementation to compute the shortest LFSR and linear span of a given binary sequence. If you have any questions or suggestions, please do not hesitate to contact Bo Zhu.

Please enter the binary sequence (separated by commas):

LFSR: Linear Span: Time Used:
Please note the output polynomial is using the form that its degree is always equal to the linear span. For example, x^3 + x + 1 means tap positions are 0th and 1st (not 0th and 2nd).

If the input sequence is too long, it may take a long time to process. As a result, the Google App Engine server may cut off HTTP connections, so the final result won't be sent back. In this case, please download the Python source code from here, and run it on local computers.