From: Dan Kotlow Subject: Re: Irrational polynomial problem in Galois fields Date: Fri, 18 Aug 2000 14:03:23 GMT Newsgroups: sci.math Summary: [missing] On Thu, 17 Aug 2000 19:38:16 +0100, dasinclair2 wrote: >I am looking for the solution to an electronics problem for a friend of >mine. The problem is to find maximal shift register sequences for >pseudo-random number generators. > >Mathematically, the problem reduces to finding an easy way of working >out for which values of n and m the polynomial 1+x^n+x^m is prime and >irreducible over Z2, the binary Galois field. Some texts give a few >examples of solutions, but none give any method of generating solutions. > >FWIW, in the particular problem he's working with the value of m is >known. > >Can anyone better at maths than me help? > >Thanks in advance. Berlekamp's Algebraic Coding Theory has a section on this. It's not easy to derive them, but it is easy to generate them all and check them. He gives the following reference as containing all the primitive binary trinomials of degree up to 1,000: Brillhart, J. and N. Zierler, 1968 On Primitive Trinomials (mod 2) Inform. Control, 13:541-554 There is a "Handbook" of Coding Theory -- maybe it's in there too. I don't know. -Dan ============================================================================== From: "bubba" Subject: Re: Irrational polynomial problem in Galois fields Date: Thu, 17 Aug 2000 21:55:00 GMT Newsgroups: sci.math Summary: [missing] So how big is m? Do you need many different primitive polynomials for the same m? If you need only one, look here: http://www.et-online.fernuni-hagen.de/~rieke/primitiv/ [quote of previously-quoted message deleted --djr] ============================================================================== From: daw@blowfish.isaac.cs.berkeley.edu (David A. Wagner) Subject: Re: Irrational polynomial problem in Galois fields Date: 19 Aug 2000 14:03:15 -0700 Newsgroups: sci.math dasinclair2 wrote: > I am looking for the solution to an electronics problem for a friend of > mine. The problem is to find maximal shift register sequences for > pseudo-random number generators. > > Mathematically, the problem reduces to finding an easy way of working > out for which values of n and m the polynomial 1+x^n+x^m is prime and > irreducible over Z2, the binary Galois field. Some texts give a few > examples of solutions, but none give any method of generating solutions. There are known techniques for efficiently checking whether a given polynomial is primitive. So I think you should be able to merely pick trinomials at random and test them for primitivity until you find one. Here are some references: (algorithms) http://www.io.com/~ritter/GLOSSARY.HTM#PrimitivePolynomial (code) ftp://helsbreth.org/pub/helsbret/random/lfsr_s.c (code) http://www.ices.cmu.edu/koopman/lfsr/ ==============================================================================\ From: Dave Rusin Subject: Re: Irrational polynomial problem in Galois fields Date: Sun, 20 Aug 2000 03:21:14 -0500 (CDT) To: dasinclair2@netscapeonline.co.uk In article <399C3118.F86C476F@netscapeonline.co.uk> you write: >Mathematically, the problem reduces to finding an easy way of working >out for which values of n and m the polynomial 1+x^n+x^m is prime and >irreducible over Z2, the binary Galois field. Some texts give a few >examples of solutions, but none give any method of generating solutions. > >FWIW, in the particular problem he's working with the value of m is >known. Dunno. There are some papers about the irreducibility of these trinomials over Q ; possibly the techniques used in those cases can be adapted to study factorizations over other fields. In any case, it's easy to compute these things. I just fired up Maple and ran this code: for m from 2 do S:=[]:for n from 1 to m-1 do p:=1+X^n+X^m:q:=Factor(p) mod 2:r:=factors(q)[2]: if nops(r)=1 then S:=[op(S),n]: fi: od:lprint(m,S):od: It took just a couple of minutes to handle all cases with m,n less than a hundred. For example, 1+x^n+x^98 is irreducible for these n: [11, 18, 24, 27, 30, 44, 54, 68, 71, 74, 80, 87] while 1+x^n+x^100 is irreducible for these n: [12, 15, 19, 25, 28, 37, 49, 51, 63, 72, 75, 81, 85, 88] and 1+x^n+x^99 is reducible for all n < 99. I certainly don't claim that this code is optimal, either. I attach the data in case this is helpful; in each row, the first entry is m and the second are the positive n < m making the trinomial irreducible. Two observations: if n is on the list, m-n will be too. And if d=gcd(n,m) then n'=n/d must be on the list in row m'=m/d, though the converse is not true (e.g. 1+x^5+x^10 is not irreducible). I see no pattern to, for example, the set of m's for which every 1+x^n+x^m (with n