# Is there a Pseudo Random Permutation Generator that can output all values of the length of N

Is there a pseudo random permutation generator that produces all permutation of any bit length of the plaintext (this may not be clear, please let me know and I will explain). It must be fast, and does not hold numbers in memory.

This is a permutation of (1) (1)

This is a permutation of (1,2) (2,1)

This is a permutation of (1,2,3) (1,3,2) (2,3,1) (2,1,3) (3,1,2) (3,2,1) n!

Note* the above is not in a pseudo random order and not a complete set that I am looking for.

This is a pseudo random permutation with replacements that I am looking to duplicate with a generator of any size.

PRP of (1,2,3) with replacements

(1,1,1)(3,3,3)(2,3,3)(1,1,3)(3,3,2)(2,3,1)(2,2,2)(1,3,3)(3,2,3)(2,1,2)(1,2,2)(3,1,3)(1,1,2)(3,3,1)(2,3,2)(2,2,1)(1,3,2)(3,2,1)(2,1,1)(1,2,3)(3,1,1)(2,2,3)(1,3,1)(3,2,2)(2,1,3)(1,2,1)(3,1,2) N^N

If one does exist could you please post its name, if possible.

If it does not exist could you expound as to the reason why, if it is against a known proof, or it has simply not been made, yet.

The question here is very similar but it needs to be with replacements.

https://math.stackexchange.com/questions/3521660/invertible-pseudo-random-permutation-function

What would it mean if it could be made. Meaning given the length of any plaintext if that order and length is your first permutation of group g than all permutation after that would be your subgroup permutations. Given that the key length that produces the permutation is not an issue (I would be glad to explain this as well).

Another way of writing this would be. What program would generate all permutations of a given string with replacement? The given string is the complete message source or file to encrypt of any size. It will probably be recursive. Once all permutations are calculated it should loop back to the original permutation which is the file.

• Do you mean like maximum length LFSR that output all except all-zero state? Of course, it is not PRP. – kelalaka May 30 '20 at 17:44
• I understand a LFSR function. I mean if your plain text is n, the output of the PRP generator would be all permutation of n^n including 0, the first permutation being your plaintext. Not a shuffle but one that will output repeating integers. If your plaintext is 4 bits (1,1,1,0) 14 , the generator will produce in a random order all 4 bit permutations using 14 as the group and the following subgroups the complete permutations of 4 bits. But it must also accommodate any file size. – Jonathan Hutton May 30 '20 at 18:16
• Meant to say "produce a pseudo random order of all permutation 4 bits in length. – Jonathan Hutton May 30 '20 at 18:35
• still unclear. what is file size? what the heck is 14 as a group? what is “permutations after that”? use mathematical notation to write a clear question. and why arent LFSRs enough for what you seem to want? – kodlu May 30 '20 at 22:38
• I think what you're asking for goes against the permutation being indistinguishable from a random one given that the expected order is way below the number of all possible permutations. – SEJPM May 31 '20 at 11:47

Use any true random permutation generator that relies on random input. Then replace the random input with the output of a PRNG primitive.

As N gets large, that approach is impractical - you can't hold an array of length N^N in memory. There's the standard trick to use the invertibility of a block cipher to iterate through 0...2^n in pseudorandom order using $$E_k(i)$$, so if N^N is close to 2^n you can use that.