Generating random non-repeating numbers from a small group I read this Q&amp;A which gave a clever solution: feed an incrementing index into a block key cipher as a way of producing non-repeating random numbers. The problem is the block size of all the good algorithms is often way too big. What if I just want to iterate through all 16-bit numbers, or all N-bit numbers where N is determined by the problem at hand? Nobody in their right mind would make a 16-bit block cipher, but that's what I would need.

One idea I had to iterate pseudo-randomly through all n-bit numbers was to use a binary field. Randomise the modulus polynomial, $Q$, ensuring it's irreducible. Then take a random starting point, $a$, and multiply repeatedly by a random primitive element, $r$, to generate the pseudorandom series.

$n_i = a r^i \pmod Q$

Something tells me this isn't good enough. Predicting the next elements can be interpreted as a discrete logarithm problem if $i$ is the plaintext which must be found from $n_i$. The discrete logarithm is difficult, but when $n_i$ are all given in order, can the problem of finding $r$ and $Q$ from the sequence still be interpreted as the discrete logarithm problem? Does the problem have a name? How hard is it?

If this method of iteration is no good, I had an idea to make it a lot harder: pad the index $i$ with some random bits before encryption, so if the index is a 16 bit number, encrypt it to 20 bits with four random bits. Would that be enough to ensure an unpredictable pattern? What method of iteration would ensure sufficient difficulty in finding a solution? One downside to this modification is that although the sequence generated is non-repeating, it doesn't cover the entire output domain. Is there a way to cover the entire output domain?
If you are going to generate ALL the numbers in the output domain, an attacker's job of guessing the next number becomes easier the more numbers you use, once you pass the halfway point. I would suggest with whatever method you choose, to never exceed $N/2$ values used, where $N$ is the total number of elements that can be generated using that method, $N=2^{16}$ in your example.

I actually see no problem with using a finite field, but you would need to make it difficult for the attacker to guess the values used to generate it, even if the method was known.

My solution would be to use the same finite field inversion method as was used to generate the AES S-box, but in $GF(2^{16})$ with the APA method. It is a highly nonlinear sequence, and there are simply too many combinations of generator values and reduction polynomials to brute force every option like there are in $GF(2^{8})$.

Essentially, you perform an affine transformation on the input, then find the inverse in the field, and then perform the affine transformation again, with an irreducible polynomial chosen at random from the list of possible polynomials. There are specific combinations of affine generators and vectors within each finite field that generate high quality results useful for S-boxes, but you would not be constrained by the same conditions, giving you more flexibility. The mathematical description of the algorithm would be very simple.

The format preserving option easily allows you to build a Feistel cipher of whatever block size you want since your domain size is an even power of 2, in your case 16-bit, by using another block cipher or PRF as the F-function. You can drop in AES, use the 8-bit block half plus a round counter as an input, and truncate the output to 8-bits. This would be very easy to code and very quick to generate numbers, at the expense of a complex description of the final algorithm. You can also generate 128-bit subkeys in CTR mode, then use these as independent AES keys for each round, at the expense of additional computation.