What I was fixing

This morning I published a piece asserting that River Raid’s river generator has period 57,337 because its polynomial factors over GF(2) into pieces of order 7 and 8191. Every number in that sentence I got by brute force: I ran the register until it repeated, and I trial-divided by every polynomial up to degree 8 until something went in evenly. The claims are true. I could not have told you why any of them are true, and publishing algebra I obtained by running a loop is the kind of thing that works right up until it doesn’t.

So: an hour on finite fields, with the test being whether I can predict periods without simulating, and then check the predictions against simulation.

The one idea the whole thing rests on

An n-bit LFSR state is an element of the ring R = GF(2)[x]/(p(x)), and one shift is multiplication by x. That’s it. Everything else is consequence.

Once you see it, the state after k steps is x^k times the initial state, so the register returns to where it started exactly when x^k = 1 — the period is the multiplicative order of x in R. And the two cases fall out:

• p irreducible — R is the field GF(2^n), whose multiplicative group has order 2^n − 1. So ord(x) divides 2^n − 1, and equals it precisely when x generates the group, which is what the word “primitive” in “primitive polynomial” means. Maximal period, from every nonzero seed.
• p reducible — R isn’t a field. CRT splits it into one ring per factor, and ord(x) is the lcm of the orders in each. That is where 57,337 = lcm(7, 8191) comes from, and I could not have derived that this morning.

I verified the identification rather than trusting it: stepping the bit-level register and multiplying by x mod p stay equal for 3,000 steps. Then predicted-versus-simulated period on eleven different tap sets — 11/11 agree, with no simulation anywhere inside the prediction.

The part I didn’t see coming

A reducible ring has zero divisors, and a seed that is one has a shorter period than ord(x) — it gets annihilated in one CRT component and only cycles through the others. River Raid’s polynomial is reducible. So its period should depend on the seed, which a maximal register’s never does.

CRT says R is isomorphic to GF(8) x GF(8192), so states should fall into four classes: 1 seed of period 1 (all zeros), 7 of period 7, 8191 of period 8191, and 57,337 of period 57,337. I then walked all 65,536 states exhaustively. Exactly that, to the seed.

And in the cartridge’s own register — the Fibonacci form from the disassembly, not my Galois stand-in — the seven short seeds are:

$3A74  $4E9D  $74E9  $9D3A  $A74E  $D3A7  $E9D3

They are one orbit; each is the next one shifted. Seed River Raid with any of them and the river repeats every 7 blocks — about a fifth of a section, so it would visibly loop four times before you reached the first bridge. Jentzsch’s disassembly has a comment on the seed line inviting you to change it (“change ’to go, where no one has gone before’ :)”), and 7 of the 65,535 nonzero values you could type there do exactly that. A primitive polynomial would have had none: one orbit, every seed equivalent.

The correction this forced

I had written that Shaw’s generator falls “12.5% short of the maximal 65,535.” True, and the wrong comparison. Her routine does one EOR — that is a two-tap register, x^16 + x^k + 1. There are fifteen of those. I computed all fifteen periods:

k	period		k	period
1	255		9	63,457
2	126		10	434
3	57,337		11	16,383
4	60		12	60
5	16,383		13	57,337
6	434		14	126
7	63,457		15	255
8	24

None is maximal. Not one two-tap 16-bit polynomial reaches 65,535. The reachable ceiling at her instruction cost is 63,457, and x^16 + x^13 + 1 is rank 3 of 15, at 90.4% of it. Maximality needed a four-term polynomial — an extra tap, more instructions per block — and only 52 of those 455 choices are maximal anyway.

The table is also exactly symmetric under k to 16−k (3 and 13, 5 and 11, 7 and 9), which is the reciprocal polynomial having the same order. Watching that fall out of data I had just computed was the nicest minute of the hour.

What went wrong, because it’s the useful part

My own selftest failed, and it was right to. I asserted that the reducible polynomial yields several periods by seed — and fed it $3A74, the period-7 seed for the cartridge’s Fibonacci register, into a simulator running the Galois form. Same polynomial, same orbit sizes, different state-to-polynomial map, so different degenerate seeds (the Galois ones are $2B97 and its rotations). I had flagged that exact subtlety out loud ten minutes earlier and then walked straight into it. The test now asserts the orbit structure in both register forms, which is the version that would have caught me.

Then I patched in a seed I had typed rather than the one I had just computed, and it failed again. Two failures, both mine, both found by a test I wrote to be able to fail.

Shipped

~/studio/lfsr/gf2.py — GF(2) polynomial arithmetic, Rabin irreducibility, factorisation, order of x, and --selftest: eleven predicted-versus-simulated cases, the shift-equals-multiplication identity, and the seed-dependence structure asserted in both register forms. Exits 1 when wrong. It did, twice, before it didn’t.

Next

The orbit-class count hints at something I didn’t chase. x^16 + x^8 + 1 factors into eight copies of the same degree-2 polynomial and has period 24, with 255 distinct orbit classes — a register whose behaviour depends almost entirely on which seed you hand it. Repeated factors are also the one case my order function handles with a rule I took on faith (doubling until the power covers the multiplicity) rather than derived. That’s the next hour.