On Tue, 21 May 2002, gfgs pedo wrote: > Its regarding maximum period LSFR's (Linear feed back > shift registers) used for generating > pseudo random numbers. > A tap sequence for an LFSR is the xor of certain bits > in the register. > > For eg: I choose a primitive polynomail mod 2 > > x^32+x^7+x^5+x^3+x^2+x+1 is a primitive polynomial mod > 2(chosen from a table) > > It says for an LSFR to be a maximum period LSFR, > the polynomial from a tap sequence plus constant one > must be a primitive polynomail mod 2
Right so far. > How ever what is the polynomial formed the tap > sequence & how is it found,I dont understand. the tap sequence is just the bits from the polynomial: x^32 + x^7 is the xor of 2 bits. + x^5 is the xor of a 3rd bit, and so on. So you just do what the polynomial says, add up the bits! Then you shift them one place (multiply or divide by x basicly). The new bit you computed is rotated in, and the ms or ls bit is lost (depending on which way you shift). > It further says the degree of the polynomail is the > length of the shift register. Yup. > Here 32 is the degree,hence is a 32 bit shift > register. > > It says a primitive polynomial of degree n is > irreducable polynomial that divides > (x^2)^(n-1) +1 but not (x^d)+1 for any d that divides > (2^n-1) Where did you find that? It's irreducible if it is a member of x^(2^n) + 1. I didn't know there was that simple a test for primitive. > Now what is the polynomial of degree n? Your tap sequence. > I thought I already had one with degree 32. Yup, you do. > which is the primitive polynomial of degree n that > divides > (x^2)^(n-1) +1 but not (x^d)+1 for any d that divides > (2^n-1) > and where did it come from? It comes from cyclotomic polynomials and finding out that all the irreducible polynomials combine to form a really simple expression. Quite amazing really - that's one of those "beautiful" things in math. I would like to know where you got it too. Usually you have to test by brute force if a polynomial is primitive or not. Patience, persistence, truth, Dr. mike
