What is the most computationally efficient way of generating pseudo-random permutations? I have an application in which I need to create up to J randomly shuffled-copies of an array of length N. Then I will have millions or even billions of iterations such that, in each iteration, I will have to fetch the value of K &lt;&lt; N entries of the J permuted copies of the original array. The K entries that need to be accessed are the same for all the J shuffled-copies but that set of K entries changes from one iteration to another.

To give an approximate idea of the dimensions of the problem, assume J = 25000, N = 500000 and K = 50 even if those numbers are not fixed a priori.

The naive approach, which I've been following so far, is to use the Fisher-Yates algorithm (also known as Knuth shuffle) to create the permuted versions of the array, storing them as a NxJ matrix in memory. However, that matrix tends to be too large in many cases, which is problematic. Also, recomputing the entire matrix in each iteration would be painfully slow.

As an alternative, I have started to consider using pseudo-random permutations instead. Using a block-cipher for which the enciphering process had complexity O(1), I could ideally fetch the K entries I need with an extra complexity O(KJ) per iteration. Which appears to be acceptable empirically.

My question, as someone with an extremely rudimentary understanding of cryptography, is which scheme would you recommend me to perform such a task. The key point is that I would rather have a scheme for which enciphering is really fast, even if the security is very poor for cryptographic standards. As long as the set of distinct permutations which can be generated (and look random enough) is in the order of 2^32, it's perfectly fine. AES-like security levels would be a clear overkill.

As a reference, I am currently using a "handmade" 4-round Feistel network with ceil(log2(N)) bits and very simple round functions (16-bit round keys, 8-bits are XORed with one half of the plaintext and the result is passed through a S-box, the other 8-bits are used as an index for a set of 256 random bit shifts). I am also using a cycle-walking scheme to deal with the (common) cases for which N is not a power of 2.

I guess the scheme is a bad joke for cryptographic standards but, for my application (statistical hypothesis testing) it appears to be random enough. It would be great if I could reduce the complexity of the encryption scheme a bit.

I would be really thankful is any of you could provide some advice!

TL;DR I am looking for the fastest possible way to generate pseudorandom permutations of a set of size N. I care much more about the speed than the security of the scheme (about 2^32 "truly" random permutations is more enough).
Use format-preserving encryption. The current NIST standards-track mode FFX should be sufficiently fast for your purposes. For your domain size, you might also want to try the swap-or-not shuffle, a new construction that is also pretty fast and dead simple to implement. To get the absolute best speed form these schemes you should use a single AES call as your PRF, preferably with AES-NI instructions if you have them.
EDIT: Any PRP generator based on an oblivious card shuffle should work for your purposes. Here's another reference explaining what that is.