Monday, 3 June 2019

finite fields - Understanding Primitive Polynomials in GF(2)?

This is an entire field over my head right now, but my research into LFSRs has brought me here.



It's my understanding that a primitive polynomial in GF(2) of degree n indicates which taps will create an LFSR. Such as x4+x3+1 is primitive in GF(2) and has degree 4, so a 4 bit LFSR will have taps on bits 4 and 3.




Let's say I didn't have tables telling me what taps work for what sizes of LFSRs. What process can I go through to determine that x4+x3+1 is primitive and also show that x4+x2+x+1 is not (I made that equation up off the top of my head from what I understand about LFSRs, I think it's not primitive)?



Several pages online say that you should divide xe+1 (where e is 2n1 and n is the degree of the polynomial) by the polynomial, e.g. for x4+x3+1, you do (x15+1)/(x4+x3+1). I can divide polynomials but I don't know what the result of that division will tell me? Am I looking for something that divides evenly? Does that mean it's not primitive?

No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...