Another theoretical rambling

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 07/08/2021 at 11:530 Comments

I'm still looking for a link between the Pisano-carry space and existing mathematical frameworks. I can't rule this out because the probability of discovering an entirely new "field" is so low and if it looks like something I already know, it is not necessarily a coincidence.

In particular, it looks somehow reminiscent of Galois field behaviour, so how could it be related ? A Galois field has a size that is a prime number, but the Pisano-Carry space works with a power of two, so that's not going to work. But let's not forget that the "interesting behaviour" appears with the introduction of the carry, which sort of shrinks or expands (which ?) the space by one. If we take w16 for example, we know that 65537 is a prime, great ! But this doesn't fly far because it doesn't work for w10: 2¹⁰+1=1025 which is not prime. Damnit.

Maybe it has something to do with GF(2) but I fail to see how it could be related. So far my best idea is to look at the X and Y numbers as GF(2) polynomials "laterally", for example the LSB of X and Y make a single 2-bit LFSR and we have n copies of such a LFSR linked by the carry function. The end-around carry will then loop the carry back to prevent the entropy being stuck at the MSB and vanishing.

So the best approach so far is still the Mersenne perspective that I mentioned months ago in the project description page. The Pisano-Carry would be a "Mersenne twister" where the coupling function between all the parallel LFSRs happens to be addition, instead of another LFSR. This hypothesis could be verified by using another size such as 3 or 4, with not just X and Y but also Z and W... However the state space would literally explode so I'm not sure it's practical for even w16, and the "ideal sizes" will certainly be different. And it would not even help if finding which sizes are "good".