This is in the context of computer programming where a $b$-byte integer is $0\leq i < 2^{8b}-1$.
I have a list of objects indexed by $i=0,1,2,...$ and I want to assign to each object another unique integer $P(i)$ in the same range $0\leq P(i) < 2^{8b}-1$. That is to say, $P(i)$ selects from some permutation of the integers.
One algorithm to do this would be to create an array $a[0]=0, a[1]=1, ...$, randomly shuffle (permute) the elements of that array, and then define $P(i)=a[i]$ which is a constant-time lookup, but requires a prohibitive amount of storage as well as an up-front computational cost.
Is there an alternative way to calculate, without using storage, an alternative $P(i)$ in constant time? The particular values are not at all important. The three key requirements are:
$P(i)=P(j) \iff i=j$
The values of $P(i)$ appear to be statistically random when written in sequence, I don't have a precise definition, just "they look random" or "the $P(i)$ should be evenly-distributed, $|i-P(i)|$ is equally likely to be small as to be large, for all $i$". It doesn't have to be cryptographically strong or anything like that, I'm just trying to maximise the Hamming distance between successive values in an "unpredictable" way.
$P(i)$ to be computed in constant time and using constant storage with no inputs other than $i$ (e.g. no lookup tables).
Preferably, the algorithm would not require the use of any intermediate values outside the $2^{8b}$ range, but that's okay if necessary. Also, ideally the permutation would be keyed by some parameter $k$ giving $P_k(i)$.
The full range of $2^{8b}$ values does not have to be covered. It's fine to restrict $0\leq i<n$ for chosen, sufficiently large $n<2^{8b}$, and it's fine if $n<P(i)$ for some $i$.
How might I compute $P(i)$?
Let $\mathbb{K}=\mathbb{F}_{2^{8b}}=\mathbb{F}_2[x]/(q(x))$ where $q(x)$ is an irreducible polynomial over $\mathbb{F}_2$with degree $8b$.
This field has $2^{8b}$ elements, hence every integer in the range $[0,2^{8b}-2]$ can be associated in a bijective way with an invertible element of this field, and the inversion in $\mathbb{K}^*$ meets the wanted constraints. To compute the inverse in a finite field has the same complexity as the extended euclidean algorithm, so it just depends (polynomially) on $b$, that is fixed.