I am currently trying to generate a four digit Linear Feedback Shift Register with digits in Mod 5 using polynomials and finite fields.
I am attempting to do so with the following algorithm:
1) First find a monic primitive polynomial of degree four, with coefficients that are all mod 5. I have found one that I wanted to use here: x4 + x2 + 3x + 2
2) Now I need to take the reciprocal of this polynomial to get another primitive polynomial with 1 in the x0 position. The reciprocal is now: 2x4 + 3x3 + x2 + 1
3) This polynomial now indicates where my taps should be for my digit. According to my reciprocal polynomial, I take the current LFSR state and multiply the 4th (counting left to right) digit by two, 3rd digit by three, and 1st digit by one and add them all up mod 5 for my new input digit. For example, if I have starting LFSR state as 4321, the next input digit will be 1 * 2 + 2 * 3 + 3 * 1 = 1 (mod 5).
4) Now I shift all the digits over to the right by one slot, and tack on the input digit that I calculated in step 3 to the first position. Thus the new LFSR state is 1432.
5) I repeat the above steps over and over, and according to theory, this should generate 4^5 - 1 = 624 unique LFSR states before hitting its period and cycling through all the states again.
I wrote a program to do this, and it indeed first generates 4321, then 1432 (expected), 2143 (expected), then 4214 and so on. However the LFSR states generated end up terminating on the 124th iteration. I tried using the above steps with other primitive polynomials but none of them terminate on the 624th iteration. What is especially worrying is that the period values aren't even divisors of 624 which implies that the polynomial is reducible, even though I know for sure that they are irreducible (used Maple to check and verified with online tables).
Can someone point out what I am doing wrong? Thank you in advance.