Re: Text on LFSR

From: Francois Grieu (fgrieu@micronet.fr)
Date: 02/03/03 

From: Francois Grieu <fgrieu@micronet.fr>
Date: Mon, 03 Feb 2003 22:56:56 +0100

In article <b1mieh$t7s$3@agate.berkeley.edu>,
 daw@mozart.cs.berkeley.edu (David Wagner) wrote:

> Francois Grieu wrote:
> >the problem of finding the periods of the
> >various cycles when the polynomial is not primitive.

> If p(t) is irreducible with degree d:
> We can factor 2^d - 1, and for each prime
> factor q, check whether t^{(2^d - 1)/q} = 1 in F^*,
> and go from there.

Thanks, I (now) get how I find the period of an LFSR with
irreductible polynomial of degree d, starting from
element t: I begin with a known multiple of the period
which is 2^d - 1, and attempt to divide the period by
prime factors q of 2^d - 1, testing if I still get a multiple
of the period. Reasonably feasible for d in the hundreds
and a given t.

However that does not tell me all the possible periods,
how many of each size exist, or the smallest period >1,
among things I'd like (I'm trying to figure out the odds
of starting from a t with a period below some bound).

> If p(t) isn't irreducible, factor it, then proceed as
> above, and use the Chinese remainder theorem.

I vaguely understand you suggest I compute something
modulo each of the irreducible polynomials which product
is my polynomial under study, then recompute that something
using the CRT. But I fail to get what this something is.

  Francois Grieu

Relevant Pages

  • Re: multiple.....
    ... ad is multiple of u. ... So any u in Z that divides rsmust divide rs. ... and if f,g are monic polynomials in Ksuch that fg is in Dthen ... Contents of polynomials and invertibility, ...
    (sci.math)
  • Re: decomposition of polynomials
    ... So now if x is any root of f, it makes the product of these two ... Don't forget that you can throw away any multiple of f. ... polynomials g and h with f | g o h, then any root x of f ... So the field extension can be done in two steps, ...
    (sci.math)
  • Re: MINIMAL POLYNOMIALS FOR TANGENTS
    ... The assertion was that the algebraic degrees of these values are phiunless n is a multiple of 4 /2). ... Polynomials Tof degree phihave been constructed which have these tangents as their root sets. ... The only remaining point to be rigorously established is that Tis irreducible if n is not a multiple of 4. ... It will suffice to show Tis irreducible if n is odd, because in this case irreducibility of ...
    (sci.math)
  • Re: derivatives and determinant
    ... Simplify the entries of A to polynomials. ... f is a multiple of p. ... the column swap negates it again so detremains unchanged. ... of the product of generalized diagonals. ...
    (sci.math)
  • Re: JSH: Fool all of the people, all of the time?
    ... > find easily works to provoke confusion. ... that is a multiple of 2. ... there's really any difference between talking about polynomials *as* ... here, and it only mentions algebraic integers very briefly, in the ...
    (sci.math)
Quantcast