Close

PEAC is NOT Pisano !

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/29/2021 at 23:110 Comments

The Pisano period is defined by taking the Fibonacci sequence, modulo some integer.

One could think that PEAC is different because the modulo is not applied in a classical way. End-Around-Carry adds an offset of one to the modulo result. But it goes much further than that.

If you compute EAC on a 8-bit byte, you get the equivalent of modulo 255 (offset by 1).

Now, if you collapse the statespace and remove the diagonal (that is not visited), you end up with 257 values !

so PEAC works modulo 1+2^n !

The above w4 is 16 wide (0 to 15) and 17 (0 to 16) high.

This is explained by the formula to draw this diagram: X is horizontal (mod 16), but vertically, this is Y (mod 16) +C (mod 2).

C is not collapsed immediately, which increases the size of the statespace. This separation of C makes a real difference and explains why this object is not easy to describe with the common mathematical tools.

From there is sounds harder to believe that PEAC can be broken down into already existing cyclic groups, meaning that PEAC seems to "stand on its own" as a separate kind of field (?).

I also notice that 2^n +1 looks like a Mersenne number (except Mersenne is 2^n -1). In the above example, we have w=4=>17 which is prime, and w8=>257 which is prime too, but w4 is ideal while w8 is not. Another counterexample is w10=>1025 which is obviously not prime. Prime numbers don't have predictive value for the quality of the statespace...

Discussions