Looking for a pseudo random number generation algorithm with specific properties

Question

I'm looking for a pseudo random number generator which has the following properties:

• Non-repeating: The returned numbers must be unique until all numbers from 0 to n have been returned once, only then it can repeat each number once more, etc.
• Deterministic: If I used the same seed twice it needs to result in the same sequence.
• Few allocations: It should not require to allocate a large memory area in order to then mix its data up like sequence permutations would.

My goal is that I could initialize the random number generator with some seed value and then continuously call its function to generate the next number in the sequence, possibly passing it the previous one.

Answer 1

One possible method is a block cypher. Encrypt the numbers 0, 1, 2, ... with a given key and the output is guaranteed unique, and will only repeat once the block size is passed. Each key will generate a different permutation. You just need to keep track of the key and the last number you encrypted.

DES uses a 64 bit block and AES uses a 128 bit block. If those sizes don't suit then you need to look at Format preserving encryption for an appropriately sized block.

One point to note, a non-repeating generator is not random. As more numbers are generated the pool of unused numbers shrinks, until the last number is fully determined. You need to consider if this is important in your application.