Idea: Lazy/faster randperm from FPE

I was using randperm, but I didn't want to store the whole permutation all the time since I only accessed it rarely and the permutation was fairly large. I did some research into whether it would be possible to obtain a random permutation, but generate the indices lazily (or alternatively have a compact encoding for the random permutation so that it can be randomly queried). Turns out there's good solutions to this problem from the crypto community under the headline of "Format-preserving encryption" (FPE). Basically what an FPE scheme provides is a pseudorandom-permutation on message S^n where S is the alphabet and n is the message length. Now, this doesn't map exactly to what we need, but it's fairly easy to do so using cycle walking. Take S={0,1}, n=ceil(log2(N)) (where N is the input to randperm). Then repeatedly apply the fpe until you get something <N. By construction the probability of that happening is >50%, so one should get there fairly quickly (fancier implementations might chose a better radix to improve the probability). NIST is in the process of standardizing FPE schemes [1] and both current schemes are AES based, so they should be quite speedy on modern hardware with AES intrinsics in the hardware. Since the existing randperm needs to do a lot of memory chases to generate its permutations, I wouldn't be surprised if an FPE-based randperm was faster than the current implementation for large n (as well as allowing lazy and sparse accesses).

I'm not sure whether this belongs in Random or in a separate package and I don't have much time to play with it at the moment, but I don't think it'd be super hard to do and thought it would be a neat performance experiment at the very least.

[1] https://csrc.nist.gov/publications/detail/sp/800-38g/rev-1/draft