(A*x+B)*x+C (mod 2^wordsize) is a permutation polynomial (quadratic), iff A=even, B=odd. But it seems to me this remains true if either or both "+" operations are replaced by XORs. Proof sketch: First of all, if A=odd, B=odd, then (A*x+B)*x will map both odd x and even x to even, hence not a permutation. That argument also works if + is changed to XOR. If A=odd, B=even, then let B=2*Q and note A has a unique reciprocal modulo 2^wordsize, whereupon (A*x+B)*x/A =(A*x*x+B*x)/A =x*x+(B/A)*x =x*x+(2*Q/A)*x =(x+Q/A)^2+const which plainly is a 2-to-1 map (consider negating x+Q/A) not a permutation. But: can this argument be made to work when the + is changed to XOR? I think it can, because we can produce the "evil twin" x by working its bits out one at a time starting from the least-significant end. So A=even is necessary for permitude. Once A=even, then B=odd is forced (in both the + and XOR cases) otherwise we'd be multiplying x by an even number, clearly losing information since always yields even product. Now to see that if A=even, B=odd we always get a permutation: We merely need to show there is no "evil twin" x causing the quadratic to have the same value. This is true if the wordsize is small by simply exhaustively verifying it. Now work inductively upward one bit at a time, i.e. increasing the wordsize by 1. We inductively know the evil twin x must have (in binary form) the same suffix as the original x. If the next-up bit differs, we can see that is not going to yield the same quadratic value because only the linear term matters. OK, we have now sketched a proof this yields a permutation iff A=even and B=odd. ======= Now, what about the period when you iterate this map: (A*x+B)*x+C (mod 2^wordsize) Iterating this yields full period 2^wordsize (using + and + with wordsize>2 bits) if A=even, B=odd, C=odd, and 4 divides 3+B-A. (Proof in Knuth.) When do the XOR versions yield full period? ======= RotateLeft(x, F(x)) is a permutation among the 2^wordsize possible x's, where the number of hops F(x) is any rotation-invariant function. Two that spring to mind are the "PopCount" function and constants, and functions thereof. Of course these permutations have all cycles short (<=Wordsize). ======== x XOR RightShift(x,K) is a bijection for any K>0. It is self-inverse. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)