What are some of the simplest known bijections in $\mathbb{Z}/n\mathbb{Z}$?
Offhand, the following classes of primitive bijections come to mind:
- Addition/subtraction (+/–) of any constant
- Multiplication ($\times$) by an odd constant (and division of course by multiplicative inverse)
- Bitwise exclusive-or ($\oplus$) with any constant, or equivalently any inversion ($\lnot$) of specific bits
- Rotary bit-shifting ($\ll$, $\gg$ with wrap-around)
and the following slightly-more-complex bijections:
- Bit-reversal (reverse the ordering of bits in a number)
- In general, any permuted mapping of the base-2 digits (bits) of a number — for example swapping two bits
- Any maximal-length LFSR (Linear Feedback Shift Register) function
and of course the most general bijection:
- Any permutation in $\mathbb{Z}/n\mathbb{Z}$
But I'm really most interested in the simplest bijections — that is, functions generally involving a single integer rather than a set of integers (multiplication, addition, exclusive-or, etc. all fit this).
The reason I’m interested is because I want to devise pseudorandom permutations in $\mathbb{Z}/n\mathbb{Z}$ by composing simple arithmetic functions.
So far, I’ve determined that permuting values in $\{0, \ldots, 2^{64}-1\}$ via 4 rounds of multiplication, addition, and bit-reversal (of randomly chosen multipliers and addends) for the case of $n=2^{64}$ is sufficient to pass PractRand for a few trillions of values, which is good for my purposes — but I'm just wondering if there are simpler formulations that produce random-looking permutations.
A simple class of permutations (not yet listed) of the ring $R_\ell:=\Bbb{Z}/2^\ell\Bbb{Z}$ is the set of quadratic permutation polynomials.
Proposition. If $a$ is an odd integer, and $b$ is an even integer, then polynomial function $$ p(x)=ax+bx^2+c $$ is a permutation of $R_\ell$.
Proof. Because $R_\ell$ is finite it suffices to show that $p$ is injective. So let's assume that $p(x)\equiv p(y)\pmod{2^\ell}$ for some integers $x,y$. This means that $$ p(x)-p(y)=a(x-y)+b(x^2-y^2)+(c-c)=(x-y)\big(a+b(x+y)\big) $$ is divisible by $2^\ell$. By our assumptions $a$ is odd and $b(x+y)$ is even, so the factor $a+b(x+y)$ is necessarily odd. This means that $p(x)-p(y)$ can be divisible by $2^\ell$ if and only if $x-y$ is divisible by $2^\ell$. But then $x$ and $y$ represent the same coset in $R_\ell$. Q.E.D.
You can find "random enough" permutations within this class already. In 2008 (if memory serves) quadratic permutation polynomials were chosen to be used in the turbo codes of the then current release of the LTE cellular standard. In other words, if your cell operator subscribes to LTE, chances are that your smartphone is computing millions of values of such permutation polynomials per second.
Block lengths other than $n=2^\ell$ are also supported. In general you need $a$ to be coprime to $n$ and $b$ to be divisible by all the prime factors of $n$. The above proof goes through verbatim.
The theory for fine tuning the parameters of $p(x)$ for the purposes of turbo code interleavers was done by Oscar Takeshita and Jing Sun, at Ohio State at the time. The QPP-interleavers allow heavy duty parallelization in the decoding (at the receiving end) which was a major selling point.