Linear Feedback Shift Registers and Cyclic Codes in SAGE

Authors

Timothy Brock, United States Naval AcademyFollow

Abstract

This talk will discuss the history of linear feedback shift registers (LFSR) in cryptographic applications and will attempt to implement an algorithm in SAGE and Python to create a linear feedback shift register sequence (LFSR sequence) in cryptography. Also, this talk will describe an implementation of the Berlekamp-Massey Iterative Algorithm in SAGE and Python. This algorithm will be able to use the Linear Feedback Shift Register sequence generated by the first algorithm to find the sequence's connection polynomial. I will attempt to show that the connection polynomial of a given LFSR sequence is the reverse of a generator polynomial of the cyclic code of length p , where p is also the period of the LFSR sequence. This will provide a connection between cyclic error-correcting codes and LFSR sequences.

Author Bio

Ensign Timothy Brock attended the United States Naval Academy from June 2002 to May 2006. He was a member of the Class of 2006 and earned a Bachelors of Science Degree in Mathematics. As part of his honors course work, he did research in coding theory, specifically looking at the use of Linear Feedback Shift Register Sequences in cryptology. Upon graduation, he will attend the Naval Postgraduate School in Monterey, CA, where he will be working towards a Masters of Science degree in Applied Science (Operations Research).

Faculty Sponsor

David Joyner

Recommended Citation

Brock, Timothy (2006) "Linear Feedback Shift Registers and Cyclic Codes in SAGE," Rose-Hulman Undergraduate Mathematics Journal: Vol. 7: Iss. 2, Article 7.
Available at: https://scholar.rose-hulman.edu/rhumj/vol7/iss2/7