From: Mike Stay <metaweta@gmail.com> Klimov and Shamir have a few papers on what they call "T-functions" and describe cheap ones with maximal period.

"In particular, we show that for any n the mapping x ? x + (x? ? C) (mod 2?) is a permutation with a single cycle of length 2? iff both the least significant bit and the third least significant bit in the constant C are 1."

http://www.wisdom.weizmann.ac.il/~ask/

A.Klimov+A.Shamir (their theorem 3): The mapping x --> x + ((x^2) OR C) using mod 2^w arithmetic, is a permutation of length 2^w, i.e. consisting of a single cycle, iff the least-significant and third-least-significant bit of the constant C both are 1. The foremost example would be C=5, and they tried that with W=64 bit long words, finding the top 32 bits of each word passed the NIST pseudorandomness test suite. Nice theorem. However, this function still features "unidirectional info flow" on its bits, hence is a poor psu-random number generator, despite whatever Klimov+Shamir say to the contrary. And the NIST suite has very basic tests only, it is not a serious hurdle like the TestU01 suite. But I do not need any suite at all to see this violates my own obvious randomness test since the lower-signif bits have lower periods. On the other hand the unidirectional info flow property makes it far easier to prove theorems like theirs -- their immense verbiage obscures this simple idea which lies behind all the proofs by both them and many others. (Furthermore, the same idea but thinking mixed-radix rather than binary, enables proving most of the other full-period theorems out there working mod M for other moduli M besides powers of 2.) Another paper by Klimov+Shamir remarks that x --> x + 1 + 4*x*x (mod 2^W) yields a single cycle and may be computed using only 2 machine instructions, one to compute y=x*x, the other to compute x+1+4*y using the x86 "lea" (load effective address) instruction. Bet your compiler won't realize that. The x + ((x^2) OR C) took 3 instructions, which your compiler probably will realize. They say a polynomial map x --> FixedPolynomial(x) (mod 2^W) for W>3 yields a single cycle iff it has a single cycle modulo 8, i.e. works for W=3. A lovely theorem. They claim a fraction 1/64 of random polynomials obey that. They then move on to iterations with vector state, i.e. not just one word. For example the map on 4-vectors of W-bit machine words [x0,x1,x2,x3] --> [x0 XOR s XOR (2*x1*x2), x1 XOR (s AND a0) XOR (2*x2*x3), x2 XOR (s AND a1) XOR (2*x3*x0), x3 XOR (s AND a2) XOR (2*x0*x1) ] they say will yield a single cycle of full length 16^W where a0=x0, a1=a0 AND x1, a2=a1 AND x2, a3=a2 AND x3, s=(a3+C) XOR a3, and C is any odd constant. They have several other examples and they can be implemented to run at very high speeds by using some SSE machine language tricks. It is possible to somewhat disguise the low-period poor behavior of low-signif bits produced by these and other such iterations, by not using their outputs X directly, but rather using f(X), for some appropriately-chosen bijective "clean up function" f(X). A disguise based on XORing various bits, for example, could be used, but good randomness tests such as bit-matrix rank tests should be able to see though such a disguise. A harder disguise to penetrate might be something like "reverse the order of X's bits to get Y, then output a bijective quadratic function of Y."