It seems that PEAC is a gift that keeps on giving and gPEAC has only started.

gPEAC solves the problem of poor mixing of binary PEAC while introducing some more complexity in other places and we're about to talk about that. For example, the resulting signature doesn't perfectly fit into a binary computer world (which would introduce some slight bias) but the mixing sure is much better.

Now let's look again at the core of the computation:

if (Y >= modulo)
    Y -= modulo-1;
Y += X;

We all know that subtraction is equivalent to addition with an opposite addend, and in 2s-complement -X = (~X)+1 so the whole can be rewritten as:

if (Y >=  modulo)
    Y += ~modulo + 2;
Y += X;

(and the carry can be discarded)

WAIT WHAT ?

Let's take

   Y -=       modulo
=> Y  = Y + (~modulo) + 1

Now let's take the other half and subtract -1 to the modulo:

    Y -= - 1
==> Y += -(-1)
==> Y += 1

You know the drill, 1+1=2 (woah) and we get the previous code.

For example, for the known case of w2, modulo=4 so we subtract 3, which is indeed ~4=11111011 (or -5 in 2s-complement) and -5+2=-3.

But why would this even matter ?

This is because we want to promote avalanche as much as possible. We get avalanche through the addition, where carries between bits propagate and mix information. We want reasonably long sequences of consecutive 1s and few 0s to separate them, for example 0x7777=0111011101110111. With this pattern, a low number takes maybe 4 cycles (as many 0s) to avalanche to the MSB.

Subtraction adds the opposite value, which means that 0s turn to 1s and vice versa. This means that we should look for moduli that have sparse bits, such as 000010000100001 or such. This is a reversal from the previous belief that "dense moduli" should be preferred to promote avalanche. So I must re-evaluate my selection criteria... without forgetting to account for the +2 ;-)

Thus we must evaluate the binary representation of modulo-1.