Comparing the entropy with LFSR

A project log for PEAC Pisano with End-Around Carry algorithm

Add X to Y and Y to X, says the song. And carry on.

Yann Guidon / YGDESYann Guidon / YGDES 08/17/2021 at 11:350 Comments

A strange consideration occurred to me: a LFSR is characterised by its (maximal) period of (2^n)-1, for n bits. The LFSR is meant to output one bit per cycle so it generates a stream of (2^n)-1 bits. So far, it's alright.

The PEAC algo uses 2n+1 bits to generate a sequence of 2^(2n-1)+ 2^(n-1)-1 numbers. Each number has n bits, so it generates n×(2^(2n-1)+ 2^(n-1)-1) bits, or 2^(2n)+ 2^(n)-n. That's a bit over 2^2n.

In practice,

Well, this is not fair because the 32-bit LFSR can also be used to generate a sequence of period 4294967296×32=137.438.953.472 bits by chunking them in packets of 32. However this sequence would simply be the basic sequence replicated 32 times with a different alignment. There is no extra data or entropy, it's simply a presentation trick, which can be useful in some very-uncritical cases.

PEAC behaves differently, as it does not seem to work in GF(2). The log 63. PEAC seen as a collection of 2-tap LFSRs has built a bridge with GF(2) but I suspect it works in GF(65535) even though 65535 is not prime. Can there be other useful applications for Galois Fields with non-prime modulus ?

Anyway, PEAC16x2 does not need a re-framing trick to generate 34.360.262.640 bits, though I have not looked yet if there are internal repetitions.

Another detail to remember is that PEAC16x2 does have 2 orbits, and the remaining states directly lead to one of them, so there is some untapped potential.