00:52 <awygle> ZipCPU: you wrote a bunch of great articles about LFSRs - do you know if there's a derivation for a maximal length polynomial or is it just trial and error to find them?

00:54 <awygle> That is, I'm looking for a function which takes a shreg length and returns a maximal length polynomial of that size.

00:55 <sorear> awygle: there's no derivation, but the number of maximal length polynomials is fairly large (\phi(something))

00:55 <sorear> this is one of those riemann-hypothesis-tangential things

00:55 <sorear> are you familiar with the relationship between LFSRs and finite fields?

00:56 <awygle> sorear: ah cool... wonder if there's a cheap test, a la statistical primality testing or something

00:56 <awygle> sorear: I know there is one (they're polynomials on GF(n)) but my theoretical math background is weak.

00:57 <sorear> a LFSR, let's say binary with 32 bits of state, stores a number in GF(2^32) and repeatedly multiplies it by an element of the finite field

00:58 <sorear> a polynomial is maximal length if the x element is a generator of the multiplicative group of the finite field

00:59 <sorear> for *prime order* finite fields, the existance of small generators is a consequence of the generalized riemann hypothesis; i don't know what the situation in small characteristic (2^n, 3^n) is

00:59 <sorear> there's a fairly cheap test

00:59 <sorear> you can easily prove that the period of a LFSR is a divisor of 2^n-1

01:00 <sorear> a LFSR is linear, so you can represent it as a matrix over GF(2) with no real cleverness required, and take large powers

01:00 <sorear> if the Kth power is non-identity for all proper divisors of 2^n-1, then the period must be exactly 2^n-1

01:00 <sorear> this requires you to have a prime factorization of 2^n-1, which could be tricky if n is much more than 500

01:01 <sorear> you can optimize this by using field exponentiation instead of matrix exponentiation, but it's harder to explain that way

01:04 <awygle> I am struggling to keep up... but I think I get it. So for my hypothetical generator I'd need to factor 2^n-1, then pick a random polynomial represented as a matrix... Then.... Raise it to a big number and make sure it's not divisible by any of the prime factors?

01:04 <awygle> Is n the number of bits? The length I mean?

01:04 <sorear> yes

01:05 <awygle> Okay and if it's divisible just pick a new one

01:05 <sorear> the correspondence is easier to see for the "Galois form" of LFSRs; each step multiplies by x mod the generating polynomial

01:06 <sorear> so if you can implement finite field arithmetic mod an arbitrary polynomial, then you calculate x^K for K = all proper maximal divisors of 2^n-1

01:06 <sorear> if all x^K != 1, then your polynomial is maximal length

01:06 <awygle> Oh okay that makes more sense.

01:07 <sorear> galois form is state = (state << 1) ^ (state & HIGH ? poly : 0);

01:07 <awygle> And odds are good that I'll randomly pick a good one because of squinting at the riemann hypothesis

01:09 <sorear> x^(2^n-1) = 1 (closely related to Fermat's little theorem), but you may or may not have x^K=1 for a proper divisor

01:10 <awygle> This seems fairly amenable to a gperf style build time calculator. Except maybe the factoring, that could take a long time.

01:13 <awygle> I guess this isn't really a problem anyone has though, just look up a table

01:15 <sorear> https://en.wikipedia.org/wiki/Primitive_polynomial_(field_theory)

01:15 <sorear> remembered what these things are *actually* called

01:16 <awygle> lol yes

01:16 <sorear> under "properties" there's a closed expression for the fraction of all possible polynomials that are primitive

01:16 <sorear> i knew there was such an expression for irreducible polynomials but couldn't remember if there was one for primitive

01:56 <ZipCPU> awygle: There's an easier way ... just count how long it takes the polynomial to repeat.

01:56 <ZipCPU> You don't need a 500 tap shift register anyway

01:56 <ZipCPU> Worse, the 500 tap registers typically don't do what you want.

01:56 <ZipCPU> That pushes shift register lengths back into the region of what is (mostly) solvable.

01:57 <awygle> ZipCPU: I certainly don't need a 500 tap lfsr! I just like general solutions to problems

01:58 <awygle> Where available and not too expensive

01:58 <ZipCPU> There's another way as well: Lists of irreducible polynomials tend to be well published.

01:58 <ZipCPU> I've got Bruce Schneier's book behind me, and it has tables of polynomials within it.

02:13 <awygle> Yeah like I said this solves no one's problem.

02:14 <awygle> I wrote an LFSR clock divider today, but I can't make it generic because there's no way to parameterize over length

02:14 <awygle> That's what caused me to ask

02:17 <sorear> and then I just got excited because i know way too much about finite fields

02:17 <awygle> Which I enjoyed learning a small part of :-)

02:52 <emeb_mac> finite fields are the work of the devil :)

02:52 <emeb_mac> but then I'm a DSP guy and working on block codes made my brain hurt.

03:02 <sorear> there is a function in LLVM which calculates inverses over the p-adic integers.

03:10 <awygle> What do they use it for?

03:11 <sorear> `div exact`

03:13 <sorear> ex. https://gcc.godbolt.org/z/a7i0M1

03:14 <sorear> you statically know that there's no remainder, so the division by 3 can be replaced by a multiplication by the ring inverse in Z/(2^32)Z

03:15 <sorear> the procedure for calculating that is Newton's method over the 2-adic numbers; it's *exactly the same* as a Newton iteration to calculate a FP inverse

04:42 <awygle> shapr: any chance you're still awake?

07:36 <edmoore> [NARRATOR: He was asleep.]

15:04 <awygle> good morning!

15:04 <ZipCPU> awygle: Speak for yourself.

15:04 <ZipCPU> ;)

15:05 <awygle> ZipCPU: we wish you a ~merry Christmas~ good morning