I ignored polynomials, implemented a "jump" function via bit-matrix exponentiation (unsupported by most BLAS-like libraries!), then did prime factorization via the Cunningham tables, and checked for partial periods of their inverses.
Some minor points I remember:
* there are several boolean choices in how you implement the LFSR. Left-vs-right, forward-vs-backward, xor-vs-xnor ... in particular you have a choice of "no all-zero state" or "no all-one state".
* when comparing that advancing by a given number is a period, it's much more efficient to advance both sides to minimize the number of 1 bits.
* an informative period failure is 15 = 6 + 6 + 3. Doesn't this conflict with something in the article?
* the info you need for 4096 bits is not in the Cunningham tables but is available elsewhere on the internet. But due to some of the simplification rules, some much-larger periods are easily derived from the Cunningham tables (assuming you can properly parse them, of course).
* tradition makes people produce LFSRs with very few taps but if you're doing it in software there's no real reason you have to do anything other than keep them even and use the end bits. I never collected statistics on how long it takes to guess a good one though.