Here is how I would do it. Pick a prime p bigger than N. Pick a random permutation of Z/pZ. Pick an initial state. Advance to the next state, to cycle through a

Here is how I would do it. Pick a prime p bigger than N. Pick a random permutation of Z/pZ. Pick an initial state. Advance to the next state, to cycle through all the values exactly once. You use rejection sampling if the state is greater than N, so as long as you pick p close to N this should happen very rarely and be amortized O(1). If N is big this advance to the next state can be encoded easily as a multiplication by an element of Z/pZ (multiplication followed by modulo p), and you will cycle through all the values because Maths. If N is not so big you pick a few (m) elements of Z/pZ to represent your permutation, and you use the first number as a multiplier mod p the first time, then the second number as a multiplier mod p the second time, and so on..., and you will also cycle through all the value, because Maths as long as you don't get a 1 while multiplying sequentially your m elements. Don't forget to stamp it good enough(TM), if not use Dual-ECC.